다이나믹 프로그래밍

외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다. 어떻게 해결할까?1. 완전 탐색 - $O(N!)$외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^22^N)$완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게..

LIS(최장 증가 부분 수열)이란?LIS란 말 그대로 어떤 수열의 부분 수열 중, 가장 긴 증가하는 부분 수열을 의미한다.예를 들어, {10, 20, 10, 30, 20, 50} 인 수열의 LIS는 {10, 20, 30, 50} 이고, 길이는 4이다. 어떻게 구할까?1. 완전 탐색 - $O(2^N)$모든 부분 수열을 구한 후, 증가하는 부분 수열 중 가장 긴 수열을 구하는 방법이다.말 그래도 모든 부분 수열을 구해야 하므로, $O(2^N)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^2)$$A_i$을 마지막으로 가지는 가장 긴 증가하는 부분 수열의 길이를 $DP[i]$라고 해보자.각 원소별로, 해당 원소($i$)보다 앞선 원소들($j$)을 탐색한다.$A_i > A_j$인 원소들 중 $DP[j..

최장 공통 부분 수열이란?최장 공통 부분 수열이란 두 수열이 주어졌을 때, 둘 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다. 예를 들어,MANGOJUICEAGODATRIP위 두 문자열의 LCS는 AGOI이다. LCS 길이 구하기LCS는 DP를 이용해 구할 수 있다.두 수열 $a_n, b_n$이 있을 때, $a_n$의 $i$번째 원소와 $b_n$의 $j$번째 원소까지 봤을 때의 최장 공통 부분 수열의 길이를 $dp[i][j]$라고 하자. 아래와 같은 점화식을 세울 수 있다.$i = 0$ 또는 $j = 0$일 때, $dp[i][j] = 0$$a_i = b_j$일 때, $dp[i][j] = dp[i - 1][j - 1] + 1$$a_i \neq b_j$일 때, $dp[i][j] = MAX(dp[i..

배낭 문제 배낭 문제란 버틸 수 있는 무게가 정해져 있는 배낭이 있고, 일정한 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 하는 방법을 찾는 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우(Fractional)와 없는 경우(0-1)로 구분된다. 쪼갤 수 있는 경우는 무게당 가치가 높은 물건부터 그리디하게 넣으면 $O(N)$만에 해결할 수 있다. 쪼갤 수 없는 경우는 다항 시간에 해결이 불가능하며, 다이나믹 프로그래밍이나 백트래킹과 같은 방법을 적용해야 한다. 이 글에서는 다이나믹 프로그래밍을 이용해 0-1 배낭 문제를 해결해보려고 한다. 점화식 세우기 $i$번째 짐까지 고려했을 때, 무게 제한이 $j$인 배낭에 담을 수 있는 최대 가치를 $f(i, j)$라고 하자. 각 짐을 고..