https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명 그대로 풀면 된다. 따로 어떤 알고리즘을 사용하지 않았다.수익을 추천인 방향으로 10%씩 올리면서 1보다 작을 때까지 반복한다.판매량 집계 데이터인 amount의 값이 최대 100,000인데, 이를 각각 추천인 방향으로 10%씩 올린다고 하자.10% 올리게 되면 최대 5명 정도만 타고 올라가기 때문에 100,000 x 5 해서 최대 500,000번의 빠른 처리를 하게 된다.#include #include #include using namesp..
전체 글
Ungroup으로 그룹을 해제하여 마무리
https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 전형적인 백트래킹 문제이다.완전탐색하면서 방문과 피로도 검사만 진행해 주면 된다.#include #include using namespace std;void DFS(const vector>& dungeons, vector& Visit, int k, int Cleared, int& answer){ answer = max(answer, Cleared); if (answer == dungeons.size()) return; for (int i = 0; i >..
https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 시소 좌석 거리가 2, 3, 4라서, 두 사람의 무게 a, b가 다음 중 하나의 비율이면 짝꿍이 된다.1 : 12 : 31 : 2 // 2 : 4를 약분3 : 4 몸무게별로 카운팅을 하고, 해당 몸무게에서 위와 같은 비율로 계산했을 때 맞아떨어지는 비율의 다른 수가 있다면, 두 무게의 카운팅을 서로 곱하면 된다.예를 들어 w = 180이면 가능한 상대는 다음과 같다.180270 // 180 * 3 / 2360 // 180 * 22..
https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 물건 1개를 배달/수거하더라도 반드시 그 거리를 가야 하기 때문에, 가장 먼 집부터 처리하고, 한 번 갈 때 배달/수거를 각각 최대한 처리하는 그리디로 푸는 문제이다.배달/수거 인덱스를 동일한 인덱스로 두고 풀어도 되지만, 그러면 배달은 모두 완료되었지만 수거만 남은 경우에도 계속 매 번 배달 왕복도 순회하기 때문에, 배달/수거 인덱스를 따로 두고, 한 턴에 각각 순회를 하되 최종적으로 더해지는 거리는 최대 거리를 더하는 방식으로 최적화할 ..
https://school.programmers.co.kr/learn/courses/30/lessons/131704 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명을 읽었을 때, 스택 느낌이 난다. 그리고 그대로 스택을 사용해서 풀면 된다.핵심은 보조 컨베이어 벨트에서 물건을 꺼냈을 때에는 기존 컨베이어 벨트와는 무관해야 한다는 점이다.그래서 다음 코드와 같이, 그냥 기존 컨베이어 벨트와 보조 컨베이어 벨트를 번갈아가며 검사할 필요 없이, 모조리 보조 컨베이어 벨트에 넣고 검사하면 된다.#include #include #include using namespace std;int solution(vecto..
https://school.programmers.co.kr/learn/courses/30/lessons/468377 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제의 핵심은 각 스테이지의 힌트 번들을 살지 / 안 살지 선택하는 완전 탐색 / 백트레킹 계열의 로직을 구축하는 것이다.힌트 번들을 산다 / 안 산다, 그리고 현재까지 가진 힌트권 개수에 따라 현재 스테이지 비용을 더한다.이 값이 최소가 되는 경우의 비용을 반환하면 된다.1. n = cost.size()2. Best를 초기화한다. - 충분히 큰 값3. HaveHints 배열을 만든다. - 크기 n + 전부 0으로 초기화4. DFS(0, 0..
https://school.programmers.co.kr/learn/courses/30/lessons/118667 이 문제의 설명 자체는 queue를 사용해서 푸는 방식과 똑같이 설명하고 있다.하지만 이 문제는 queue로 풀어도 되지만, 실제 구조는 투 포인터 문제로도 볼 수 있다.문제의 핵심은 연속 구간의 합을 target으로 맞추는 문제이다. 먼저, 가장 직관적으로 queue 2개를 사용하여 풀어보자.queue를 사용하여 풀 때의 중요한 점은 무한 루프 방지이다.넉넉잡아 queue 사이즈의 7배 정도면 300,000 x 7 = 2,100,000번 정도의 계산이면 안전하게 동작한다.1. queue1, queue2의 합을 구한다.2. total = sum1 + sum2를 구한다.3. total이 홀수..