반응형 Dynamic Programming 썸네일형 리스트형 Platinum DP 문제들 풀이 (1) 요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다. 많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다. [BOJ 1126] 같은 탑 (Platinum III) N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다. 이때, 만들 수 있는 탑의 높이의 최댓값을 구.. LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이.. [BOJ 11066] 파일 합치기 (https://www.acmicpc.net/problem/11066) 이 문제는 Dynamic Programming을 이용하는 문제이며, Knuth's Optimization을 이용하여 최적화를 한다. Knuth's Optimization 게시글 (https://wogud6792.tistory.com/20) 위 문제는 파일을 합치는 모든 경우 중에서, 합이 최소가 되는 경우를 찾는 문제이다. 만약 C1~C4를 합친다면, C1 + C2~C4 또는, C1~C2 + C3~C4 또는, C1~C3 + C4와 같이 부분문제가 만들어질 수 있다. 이 때, C2 ~ C4, C1 ~ C3의 경우도 또 다시 부분문제로 나뉘어 질 수 있다. ex) C2 + C3~C4 또는 C2~C3 + C4 / C1 + C2~C3 또는 .. Knuth's Optimization Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다. i) DP 점화식 형태 $ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $ $ (i\le k 이전 1 다음
