[실전 알고리즘] 0x09강 - 다이나믹 프로그래밍_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

이번 시간에는 다이나믹 프로그래밍을 다뤄보겠습니다. 지금까지 백트래킹, 시뮬레이션, 재귀, 분할정복 등으로 너무 고통받으셨다면 이번 시간엔 조금 더 나을겁니다. 다이나믹 프로그래밍의 개념은 그다지 어렵지않아요.

 

 

 

다이나믹 프로그래밍(=Dynamic Programming, DP라고 줄여서 부르기도 함. 이번 강의에서는 글자수를 줄이기 위해 DP라고 계속 부를 예정입니다.)은 여러 개의 하위 문제들을 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘입니다. 되게 뜬구름잡는 이야기같죠? 쉽게 설명하면, 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가 답을 알아내는 형태입니다.

 

예를 들어 피보나치 문제를 생각해봅시다. 0x06강에서 재귀함수로 구현했을 경우 $N$번째 항을 구하는데 $O(1.618^N)$이 필요했지만 DP로 구현하면 $O(N)$에 구할 수 있습니다. 중간 결과를 저장하는지 그렇지 않은지에 따라 이렇게 극적인 효율 차이가 만들어집니다.

 

코딩테스트에 나올 수준의 DP 문제는 일단 점화식만 이끌어놓고 나면 그 뒤는 반복문을 돌면서 배열을 채워나가면 되기 때문에 구현이 굉장히 간단한 편에 속합니다. 그러나 다양한 DP 문제를 풀어봤거나 뛰어난 수학적 직관력을 가지고 있지 않은 이상 문제에서 점화식을 이끌어내는 과정이 쉽지 않고, 무엇보다 초보 단계에서는 주어진 문제가 DP로 푸는 문제임을 알아차리지 못할 수도 있습니다.

 

DP는 쉬운 문제는 쉽지만 작정하고 어렵게 내면 저세상 난이도의 문제를 만들어낼 수 있습니다. 예를 들어 UCPC 2018 본선의 경우 모든 참가팀이 푼 A번 문제도 DP, 모든 참가팀이 풀어내지 못한 F번 문제도 DP였습니다. (대회 당시 A번문제 second solver가 저였습니다 ^o^)

 

그래서 DP에 대해 깊게 파고들어가면 끝도 없지만, 이번 강의에서는 쉬운 문제를 최대한 많이 다뤄보는데 주력할 것입니다. 여러분들도 그룹 내의 문제집에 올려둔 적당한 난이도의 DP 문제들을 풀고 머릿속으로 고민하면서 많은 유형을 학습하고 숙달하는 것이 중요합니다. 그래야 코딩테스트에서 DP문제를 빠르게 쓱싹할 수 있어요.

 

BOJ 1463번 : 1로 만들기를 풀어봅시다. 이 문제를 보고 BFS로 해결할 수 있겠다는 생각을 했다면 스스로에 대해 대견하게 생각하셔도 됩니다! 구현도 한번 해보세요. 그런데 DP로 해결하면 코드가 정말 짧아집니다. DP로 해결하기 위해서는 일단 배열에 어떤 값을 넣어야 할지, 또 관계식은 어떻게 될지를 잘 생각해야 합니다. $D[i] = i$를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값이라고 합시다. $D[1] = 0$입니다. 이제 $k = 2 to N$에 대해 $D[k]$를 어떻게 계산할 수 있을까요?

 

구체적으로 $D[12]$를 계산한다고 쳐봅시다. 할 수 있는 연산은 3가지인데, 3으로 나누면 12가 4가 되니 4에서 1로 만드는 과정의 최소 횟수는 내가 직접 계산할 필요 없이 $D[4]$를 가져다 쓰면 됩니다. 즉 $D[4]+1$이죠. 마찬가지 논리로 보면 2로 나누는건 $D[6]+1$, 1을 빼는건 $D[11]+1$이므로 $D[12] = min(D[4]+1, D[6]+1, D[11])$입니다.

 

비슷한 방식으로 생각해보면 일반적인 $k$에 대해 $D[k]$는 일단 $D[k-1]+1$이고, $k$가 2로 나누어진다면 $D[k/2]+1$을, 3으로 나누어진다면 $D[k/3]+1$을 추가로 고려해 이들 중에서 최솟값을 택하면 됩니다. 정답 코드를 참고하세요.

 

두 번째 문제는 BOJ 2579번 : 계단 오르기입니다. 초등부 4번이네요. 요새 초등학생들은 많이 똑똑한가봅니다. 만약 계단의 갯수가 그다지 많지 않았으면 백트래킹으로 해결이 가능할텐데 계단의 갯수가 300개니 불가능합니다. 이 문제의 정해는 DP입니다. 배열에 어떤 값을 넣어야 할지, 또 관계식은 어떻게 될지를 알아맞춰보세요.

 

우선 서술의 편의를 위해 $i$번째 계단에 적힌 점수를 $S[i]$이라고 하겠습니다. 뭔가 $D[i] = i$번째 계단까지 올라섰을 때의 점수 합의 최댓값이라고 두는게 그럴싸해보입니다. 이 때 $D[1] = S[1]$입니다. 그러면 $k = 2 to N$에 대해 $D[k]$를 어떻게 계산할 수 있을까요?

 

문제에서 주어진 예시 (10, 20, 15, 25, 10, 20)을 생각해봅시다.

 

$D[2]$는 1번째, 2번째 계단을 다 밟으면 되니 30일 것입니다.

 

$D[3]$은 어떤 식으로 구해야할까요? $D[3]$은 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건으로 인해 20+15=35가 답이 됩니다. 그런데 $D[i]$의 값을 가지고는 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 수가 없습니다.

 

그렇기에 슬프지만 현재의 $D[i]$는 문제룰 풀기에 적절하지 못합니다.

 

$D[i][j] = $현재까지 $j$개의 계단을 연속해서 밟고 $i$번째 계단까지 올라섰을 때의 점수 합의 최댓값, 단 $i$번째 계단은 반드시 밟아야 함 이라고 합시다. 정의가 잘 이해가 가나요? $D[1][1]$은 자명하게 $S[1]$이고 $D[1][2]$는 0입니다. 그리고 $j$는 1 혹은 2입니다. 3 이상이면 연속된 세 개의 계단을 못밟는다는 조건에 위배되기 때문입니다.

 

$k = 2 to N$에 대해 $D[k][1], D[k][2]$를 어떻게 계산할 수 있을까요? 문제의 예시 (10, 20, 15, 25, 10, 20)에서 직접 D 테이블을 채워넣는 과정을 손으로 해보세요.

 

$D[2][1]$은 1번째 계단을 밟지 않았다는 의미이니 20이고 $D[2][2]$는 1번째, 2번째 계단을 다 밟으면 되니 30일 것입니다.

 

$D[3][1]$은 2번째 계단을 밟지 않았다는 의미이고 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있다는 조건으로 인해 1번째 계단은 반드시 밟아야 합니다. 1번째 계단을 밟을 당시에 점수의 최댓값에 $S[3]$을 더하면 됩니다. 즉 $D[3][1] = max(D[1][1], D[1][2])+S[3] = 25$입니다.

 

$D[3][2]$는 2번째 계단을 밟았다는 의미입니다. 그리고 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건으로 인해 $D[3][2] = D[2][1]+S[3] = 30$입니다.

 

이제 점화식이 느낌이 오나요? $D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k]$, $D[k][2] = D[k-1][1] + S[k]$입니다. 그리고 답은 $max(D[N][1], D[N][2])$입니다. 정답 코드를 확인해보세요.

 

이렇게 계단 오르기 문제를 해결했지만 이대로 끝내지말고 이 문제를 해결하는 또 다른 DP 테이블을 생각해봅시다. 생각해보면 $N$번째 계단까지 점수의 최댓값은 곧 밟지 않는 계단의 점수 합의 최솟값을 구하는 문제와 동일합니다. 즉 관점을 달리해 밟지 않을 계단을 선택하도록 DP를 짜봅시다.

 

$D[i] = i$번째 계단까지 올라가면서 밟지 않을 계단의 합의 최솟값, 단 $i$번째 계단은 반드시 밟지 않을 계단으로 선택해야 함 이라고 합시다. $D[1]$은 자명하게 $S[1]$입니다.

 

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다는 조건으로 인해 $k$번째 계단을 밟지 않을 계단으로 선택했으면 $k+1$번째 계단을 연달아 선택할 수는 없습니다. 또한 연속한 세 계단을 모두 밟을 수는 없다는 조건으로 인해 $k$번째 계단을 밟지 않을 계단으로 선택했으면 $k+2, k+3$번째 계단 중 어느 하나는 밟지 않을 계단으로 선택해야 합니다.

 

예시 (10, 20, 15, 25, 10, 20)에서 DP 테이블을 채워봅시다. $D[2] = 20, D[3] = 15$입니다. 그리고 $D[4] = min(D[1],D[2])+S[4])$라는거 아시겠나요? 4번째 계단을 제외하고 나머지 계단 중에서 가장 최근에 밟지 않을 계단으로 선택한게 1번째 계단이거나 2번째 계단일테니까요. 왜 3번째 계단일 수는 없는지는 조건을 다시 생각해보세요.

 

마찬가지 논리로 생각하면 $D[k] = min(D[k-2], D[k-3])+S[k]$입니다. 그리고 답은 전체 계단의 합 - $min(D[N-1],D[N-2])$입니다. 마지막 도착 계단은 반드시 밟아야한다는 조건 때문입니다. 정답 코드를 확인해보세요. 두 번째 방법이 메모리를 2배 적게 쓴다는 장점이 있긴 하지만 두 방법 모두 괜찮은 방법이니 본인에게 맞는 방법으로 숙달시키면 됩니다.

 

세 번째 문제는 BOJ 1149번 : RGB거리 문제입니다. 풀만한 난이도이니 한번 직접 시도해보시고 막히면 다음 장으로 넘어와주세요.

 

$D[i] = i$번째 집까지 칠할 때 비용의 최솟값으로 두면 딱히 이끌어낼 수 있는 식이 없습니다. 뭔가 색깔에 대한 정보도 같이 가지고 있어야 할 것 같네요. 그렇기에 $D[i][0], D[i][1], D[i][2]$를 $i$번째 집이 빨강/초록/파랑일 때의 최솟값으로 각각 두어서 식을 생각해보세요.

 

식은 이렇게 간단하게 만들 수 있습니다. 초기값에 무엇을 담을지에 주의해 직접 짜보세요.(정답 코드)

 

네 번째 문제는 BOJ 11726번 : 2×n 타일링 입니다. 지금 DP를 배우고 있으니 저 문제가 DP 문제이겠구나 싶긴 하겠지만, 아무 정보 없이 문제를 접했다면 아마 DP 문제라는 것을 눈치채지 못했을 것입니다. 조금 어렵지만 한 번 시도해보세요.

 

지금까지 늘 그랬듯 D 테이블을 잘 정해야 합니다. 가장 원초적인 형태로 $D[i] = 2×i$를 타일링하는 경우의 수라고 하고 이제 점화식을 찾아내봅시다.

 

다른건 생각하지말고 저 O 쳐진 칸을 어떤 타일로 덮을지 생각해보세요.

 

첫 번째로 2×1 타일로 해당 칸을 덮는다면 남은 2×8을 타일링하는 경우의 수만 세면 되겠네요. 즉 $D[8]$입니다.

 

첫 번째로 1×2 타일로 해당 칸을 덮는다면 밑에 있는 x 쳐진 칸도 자동으로 1×2 타일을 덮을 수 밖에 없게 됩니다. 남은 2×7을 타일링하는 경우의 수만 세면 되겠네요. 즉 $D[7]$입니다.

 

그러므로 $D[k] = D[k-1]+D[k-2]$입니다. 참 쉽죠. 정답 코드도 간단합니다. 다른 타일링 문제들을 풀 때도 이런 식으로 특정 칸 하나를 각 타일로 덮었을 때의 경우의 수를 세서 식을 이끌어내면 됩니다.

 

5번째 문제는 BOJ 1912번 : 연속합 입니다. 이 문제는 학부 수업시간에서 자주 다루게 되는 문제 중 하나입니다. 우선 지금까지 코딩을 한 짬이 있는데 $O(N^3)$ 풀이는 바로 떠올릴 수 있죠? 그냥 시작점, 끝점을 잡고 그 구간내의 원소를 다 더하면 되니까요.

 

여기서 더 나아가 Prefix sum이라는 기법을 사용하면 $O(N^2)$까지는 그럭저럭 무난하게 할 수 있습니다. Prefix sum을 사용하기 위해서는 1-indexed인게 편합니다. Prefix sum을 처음 본다면 이번 기회에 익혀두세요.

 

$O(N^3)$에서 $O(N^2)$으로 줄인 것만 해도 엄청난 발전이지만 $N \le 100,000$인 이 문제를 풀기엔 아직 부족합니다. DP로 무려 $O(N)$에 풀 수 있는 방법을 고민해봅시다.

 

배열에 어떤 값을 넣어야 할지, 또 관계식은 어떻게 될지를 알아맞춰보세요. 조금 어렵지만 스스로 알아맞추면 정말 기쁠테니 해답을 보기 전에 고민을 충분히 많이 해보세요.

 

$D[i] = i$번째 항을 마지막으로 사용하는 수열의 합 중 최댓값으로 두면 딱 느낌이 오나요? 사실 안오는게 정상입니다.

 

$D[k] = max(0, D[k-1]) + A[k]$입니다. $k-1$번째 항을 마지막으로 하는 수열의 합 중 최댓값이 0보다 크면 그 수열에 $A[k]$를 붙이면 되고, 0 이하이면 그냥 $A[k-1]$을 쓰지말고 $A[k]$만으로 수열을 만들면 되기 때문입니다. 정답 코드를 확인하세요.

 

6번째 문제 BOJ 11053번 : 가장 긴 증가하는 부분 수열입니다. $D[i] = i$번째 항을 마지막으로 사용하는 수열 중 최대 길이로 두면 $O(N^2)$ 풀이가 딱 떠오르지 않나요? 더 이상의 자세한 설명은 생략합니다! 정답 코드를 확인해보세요.

 

참고로 이 문제는 Segment Tree나 Binary Search를 이용해 $O(NlgN)$로도 해결할 수 있습니다. 먼 훗날에 공부해보세요!

 

마지막 문제 BOJ 2293번 : 동전 1입니다. 마지막 문제 답게 꼬아놓은 요소가 군데군데 있습니다. 일단 $N$이 작다면 $O(2^N)$에 전수조사를 할 수 있을텐데 여의치가 않네요. 일단 $D[i][j] = i$번째 동전까지를 사용해 합이 $j$가 되게끔하는 경우의 수로 D 테이블을 잡으면 되긴 하는데, 식을 잡는게 쉽지 않을겁니다. 한 번 고민해보세요. 예를 들어 현재 3번째 동전을 보고 있고 3번째 동전의 가치가 10일 때 $D[3][25]$는 얼마일까요?

 

3번째 동전을 몇 개 사용할 것인지를 가지고 차근차근 구해보면 됩니다. 3번째 동전을 0개 사용하는 경우에는 $D[2][25]$, 1개 사용하는 경우에는 $D[2][15]$, 2개 사용하는 경우에는 $D[2][5]$입니다. 즉 $D[3][25] = D[2][25]+D[2][15]+D[2][5]$ 입니다. 그런데 이렇게 구현하면 $D[i][j]$를 채우기 위해 $j/A[i]$개의 항의 합이 필요하고 모든 동전의 가치가 1일 때를 생각해보면 $O(NK^2)$에 동작해서 시간초과가 발생합니다.

 

관점을 조금 바꿔, 동전을 0개/1개/2개/... 사용했는지를 가지고 DP식을 만드는게 아니라 $i$번째 동전을 사용했다/안했다로 DP식을 만들어야 합니다.

 

3번째 동전을 사용하지 않았으면 $D[2][25]$, 3번째 동전을 사용했으면 $D[3][15]$입니다. 즉 $D[i][j] = D[i-1][j] + D[i][j-A[i]]$입니다.($A[i]$는 $i$번째 동전의 무게이고 $j < A[i]$일 경우 $i$번째까지의 동전으로 $j-A[i]$원을 만드는 것이 불가능하므로 뒤의 항은 무시하도록 해야 합니다.) 이렇게 하고 나면 각 테이블을 $O(1)$에 채울 수 있으므로 $O(NK)$에 동작합니다.

 

그런데 생각할 점이 한 가지 더 있습니다. 메모리 제한이 4MB이기 때문에 $D[100][10001]$을 잡으면 메모리 초과가 발생합니다.

 

다시 DP식을 봅시다. $D[i][j]$는 $D[i+1][...]$을 구할 때에만 필요할지 $D[i+2][...], D[i+3][...] ... $을 구할 때에는 더 이상 쓸모가 없습니다. 그러므로 굳이 $D[100][10001]$을 들고다닐 필요 없이 $D1[k+1], D2[k+1]$ 만 가지고 처리를 해줄 수 있습니다. 정답 코드를 참고하세요.

 

동전 관련 문제는 코딩 테스트에서 자주 나오는 문제입니다. 이 문제에서는 억지로 메모리를 4MB로 줄여놨기 떄문에 메모리를 아끼는 기법이 추가로 쓰였지만 코딩테스트에서 이정도 수준까지를 요구하지는 않습니다. 그러나 알아둬서 나쁠건 없습니다.

 

이번 시간에는 DP의 개념을 배우고 다양한 DP 문제들에 대해 풀어봤습니다. 7문제를 같이 다루긴 했지만 7문제로는 부족합니다. 정말 수많은 DP 문제들이 있고 많이 풀면 풀수록 문제해결능력을 올릴 수 있으니 계속 풀어보세요.