반응형 dp 썸네일형 리스트형 Platinum DP 문제들 풀이 (1) 요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다. 많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다. [BOJ 1126] 같은 탑 (Platinum III) N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다. 이때, 만들 수 있는 탑의 높이의 최댓값을 구.. [BOJ 7812] 중앙 트리 [문제] www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net [난이도] - Platinum III (20.12.14 기준) [필요 개념] - Tree DP - DFS [풀이] 설명에서 나오는 S(u)는 'u를 루트로 하는 서브트리'를 뜻한다. 한 점에 대해서 다른 모든 점까지의 거리의 합을 구한다면 단순 Tree DP를 이용하여 노드의 개수만큼 탐색하면 된다. 하지만, 이 문제는 모든 정점에 대해서 고려를 해야하기 때문에 $O(n^2)$이고.. [BOJ 12920] 평범한 배낭 2 [문제] : https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 � www.acmicpc.net [필요 개념] - DP , 배낭 문제 (Knap-sack) - 비트마스크 [풀이] 전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데.. 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 다음
