Problem Solving

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12907 풀이 DP 문제다. 순열인지 조합인지 조심하면 쉽게 풀 수 있다. 문제에서 예시로 든 1, 2, 5원이 있을 때를 생각해보자. (5도 마찬가지지만) 2는 1의 배수이다. 따라서 순열로 하면 ‘3’을 만드는 경우에 1+1+1, 1+2, 2+1 이라는 세 가지 방법이 나오게 된다. 하지만 이 문제는 조합 문제이므로 중복을 제거해야한다. 그러면 중복을 어떻게 제거해야 할까? 작은 동전부터 순서대로 만들면 된다. 이 방법이 조합 DP의 가장 기본적인 방법이다. 가장 작은 동전을 써서 만들 수 있는 조합을 다 만든 다음 DP 테이블에 저장한다. 작은 순서대로 (오름차순으로) 조합을 더한다. 이런 식으로 하면 중복을 방지할 수 있다. 위 예제로 따지면 1원짜리 동전을 먼저 써서 1+1+1을 우선 만들고, 다음에 2원을 써서 1+2를 만든다. 작은 순서대로 하므로 알고리즘 상에서 2+1 같은 방법을 만들지 않는다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 풀이 우선 순위대로 문제를 처리하므로 힙을 써야하는 것은 명확하다. 하지만, 이 힙을 어떻게 다루느냐가 더 중요한 문제이기 때문에 사실상 힙보다는 단순 구현 문제에 가깝다. 코드 import heapq def solution(jobs): jobs.sort(key = lambda x: x[0]) waitQueue = [] finished = 0 currentTime = 0 jobIdx = 0 totalReturnTime = 0 while finished < len(jobs): while jobIdx < len(jobs) and jobs[jobIdx][0] <= currentTime: requestTime, duration = jobs[jobIdx] heapq.heappush(waitQueue, (duration, requestTime)) jobIdx += 1 if waitQueue: duration, requestTime = heapq.heappop(waitQueue) currentTime += duration returnTime = currentTime - requestTime totalReturnTime += returnTime finished += 1 else: currentTime = jobs[jobIdx][0] return totalReturnTime // len(jobs)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64062 풀이 처음 문제를 읽어보고 바이너리 서치를 이용해야겠다고 생각했다. 결정해야 할 값을 건널 수 있는 최대 인원수로 맞춰놓고 바이너리 서치를 이용하여 찾으면 되기 때문이다. 바이너리 서치를 이용한 알고리즘은 다음과 같다. 바이너리 서치를 통해 찾고 싶은 값은 징검다리를 건널 수 있는 최대 인원 수이다. 징검다리 하나의 내구도가 최대 2억이므로 1에서 2억까지의 범위 내에서 인원 수의 최대값을 찾는다 값이 유효한지 체크하는 방법은 징검다리에서 현재 인원 수가 밟은 수를 뺀 다음 0 이하의 징검다리 돌들이 연속되는 경우가 k개 이하면 통과, 초과면 통과시키지 않는다. 바이너리 서치 결과를 리턴한다. 이 코드의 시간 복잡도는 $N$이 stones 배열의 크기, $M$이 돌 내구도의 최대값이라 했을 때 $O(N \log M)$이다. 돌 내구도의 최대값은 2억이고, 2의 30제곱이 약 10억이므로 30번 이내에 찾을 수 있다. 최대 20만 크기의 배열을 30번 정도 반복한다고 생각하면 충분히 시간 복잡도가 나온다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 풀이 일정 크기의 배열(혹은 컬렉션)을 만들어서 매칭되는지 확인해야 하는 문제다. DFS를 사용해서 모든 경우의 수를 만들기는 쉽지만, 그 경우의 수가 문제에서 제시하는 조건에 맞는지 확인하는 것은 어렵다. 따라서 알고리즘을 약간 수정해서 좀 더 효율적이고 만들기 쉬운 알고리즘을 만들어야 한다. 알고리즘은 다음과 같다: 주어진 banned_id 배열 원소 하나하나에 대응가능한 id를 user_id에서 뽑아서 후보 set에 넣는다. 1번을 재귀적으로 진행한다. set에 담는 이유는 id가 중복되면 안되기 때문이다. 후보 set이 완성되면, 정답 set에 저장한다. set은 set에 담을 수 없으므로 frozenset을 이용한다. 정답 set의 개수를 리턴한다. 코드 def compare(strA, strB): if len(strA) != len(strB): return False for char in zip(strA, strB): if char[0] != char[1] and char[1] != '*': return False return True def dfs(user_id, banned_id, index, candidateSet, idSet): if index == len(banned_id): idSet.add(frozenset(candidateSet)) return for id in user_id: if id in candidateSet: continue if compare(id, banned_id[index]): dfs(user_id, banned_id, index + 1, candidateSet + [id], idSet) def solution(user_id, banned_id): idSet = set() dfs(user_id, banned_id, 0, [], idSet) return len(idSet)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 그리디 문제다. 그리디는 따로 정석 구현이 있는 알고리즘이 아니라 일종의 컨셉이지만, 배열 + 그리디면 잘 알다시피 정렬이 중요한 경우가 많다. 단순하게 생각해보자, 문제에서 주어지는 것은 시작 위치와 종료 위치다. 그냥 종료하는 위치를 기준으로 오름차순 정렬한 후에 앞에서부터 탐색을 한다. 현재 자동차의 종료 위치에 카메라를 설치하고, 다음 자동차를 살펴본다. 다음 자동차의 시작 위치가 이전 자동차의 종료 위치(즉 카메라가 설치된 위치)보다 앞에 있으면 다음 자동차도 설치된 카메라를 만나게 된다. 그렇지 않다면 또 그 자동차의 종료 위치에 카메라를 설치하면 된다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12987 풀이 n의 값이 최대 10000, s의 값이 최대 1000000의 값을 가질 수 있으므로 모든 경우의 수를 DFS로 탐색하는 것은 매우 비효율적이다. 하지만 수학적 직관을 이용해 생각해보자. 예시로 주어진 s = 9, n = 2인 경우에서도 {4, 5}가 최고의 집합이다. 만약 s = 5, n = 2인 경우에는? {2, 3}이다. s = 10, n = 2인 경우는 {5, 5} 이다. 집합 원소들이 최대한 고르게 되어있을 때 원소들의 곱이 최대가 된다는 것(= 최고의 집합이라는 것)을 알 수 있다. 그러면 이 직관을 증명해보자. ...

문제 https://www.acmicpc.net/problem/2193 풀이 문제에서 명시적으로 두 가지 조건을 제공해준다. 0으로 시작하지 않는다. 1이 연속되지 않는다. 이진수라는 조건도 있으므로, 3가지 조건이 있다고 볼 수 있다. 케이스를 몇개 써보면 쉽게 DP로 풀 수 있는걸 알 수 있다. dp[1] = 1 // 1 dp[2] = 1 // 10 dp[3] = 2 // 100, 101 dp[4] = 3 // 1000, 1001, 1010 2번째 조건 때문에, 0으로 끝나는 경우에는 1을 붙일 수 있지만, 1로 끝나는 경우에는 0으로 붙일 수 없는 것을 알 수 있다. DP 테이블을 다음과 같이 정의하자. ...

문제 https://www.acmicpc.net/problem/12852 풀이 DP를 사용해서 해결했다. 문제를 거꾸로 뒤집어보자. n에서 1을 가는 최단거리가 아니라, 1에서 n으로 가는 최단거리로 바꾸는 편이 편하다. 이렇게 뒤집으면 개별 숫자에서 다른 숫자로 갈 수 있는 방법은 3가지가 주어진다. 1 더하기 2 곱하기 3 곱하기 쉽게 점화식을 만들 수 있다. dp[i] = max(dp[i - 1], dp[i / 2], dp[i / 3]) + 1 하지만 경로도 트래킹 해야 하는데, 이건 각 개별 숫자에 도달하기 전에 어떤 수에서 왔는지를 저장하는 배열 하나를 만들고, 최종적으로 이 배열을 루프로 순회하거나, 재귀를 통해서 경로를 얻어낼 수 있다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 풀이 많이 해맨 문제다. 처음에는 다음과 같이 알고리즘을 생각했다. 일단 쿼리의 개수와 info 배열의 크기를 생각해보면 filter를 사용하는 문제는 아님 바이너리 서치, Upper bound와 Lower bound의 차이가 해당하는 원소의 개수가 같음 info 배열을 잘 정렬해서 바이너리 서치만 하면 쉽게 해결될 문제 하지만 조금만 생각해보면 이러한 방식의 알고리즘은 문제를 절대로 해결할 수 없다. 우선 쿼리의 조건들이 독립적이다. 정렬 기준에 따라서 포함되어야 할 값이 포함되지 않게 된다. 그렇다고 바이너리 서치 -> 다시 정렬을 반복하기엔 차라리 filter를 쓰는게 더 시간 복잡도가 더 좋다. 다음에 생각한 방식은 트리를 이용하는 방식이었다. ...

문제 https://www.acmicpc.net/problem/13144 풀이 매우 특이한 유형의 투 포인터 문제다. start, end가 증가만 해서는 모든 경우의 수를 나타낼 수 없으며, 모든 경우의 수를 탐색하려면 O(n^2)이 된다. 1 2 3 1 2 라는 수열이 있을 때를 생각해보자 겹치는 원소가 나오지 않도록 작성한 일반적인 투 포인터는 1, 12, 123, 231, 312 이렇게 5번 탐색을 하고 종료한다. 하지만 1 2 3 1 2의 정답은 5가 아니라 15이다. 하지만 이 5번의 탐색만으로도 15라는 결과를 얻을 수 있는데, 우리는 정확한 부분 수열의 형태보다 경우의 수만 알면 되기 때문이다. ...