다이나믹 프로그래밍

드디어 중간고사가 끝났습니다!!!!!!!!!!!! 결과가 어땠든 모두 수고하셨습니당

세 번이나 이어진 자료구조 주제가 끝나고 더 알고리즘과 가까운 주제를 다룰 차례입니다.

이번 주제 역시 소수전공이나 여기저기서 접한 친구들도 있을 것 같습니다.

보통 다이나믹 프로그래밍에 익숙해지면서 대회 알고리즘에 재미를 붙이는 경우가 많은데요.

어렵지만 그만큼 재미있고, 대회에서뿐만 아니라 현실에서도 아주 유용하고 코테에도 자주 나오니 많이 공부해 보면 좋겠습니다!

 

※ 다이나믹 프로그래밍 == 동적 계획법 == 동적 프로그래밍 == DP(Dynamic Programming) 입니다.

메모이제이션은 약간 미묘하게 의미가 다릅니다

※ 이름이 "다이나믹" 프로그래밍 이라는 이유는 딱히 없습니다. 이름 지을 때 있어 보이는 단어를 가져왔다고 합니다

 

목차

• DP란?
• 예제1
• 예제2
• 코드로 어떻게 짜요
• DP 문제 판별법
• 연습 문제

 

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 부분 문제들의 답을 바탕으로 전체 문제를 해결하는 기법입니다.

위키백과에서도 비슷하게 설명하고 있습니다.

일단 첫 번째 문장만 봐요

다이나믹 프로그래밍은 정말 이게 끝입니다. 

정의를 머릿속에 잘 기억하고, 문제를 풀면 됩니다.

하지만 다이나믹 프로그래밍을 처음 접한다면 "그래서 어쩌라고" 같은 생각이 들 것 같아요.

예제를 풀며 다이나믹 프로그래밍을 어떻게 쓰는지, 어떻게 적용해서 문제를 푸는지 알아보겠습니다.

예제 중 안 풀어본 문제가 있다면 적어도 5~10분 정도는 혼자 고민해보고 풀이를 읽으면 더 도움이 될 거예요

 

예제1. 2×n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

DP 기초로 아주아주 유명한 이 문제를 풀어 보도록 하겠습니다.

앞서 말했지만 막히더라도 혼자 먼저 시도해 보아야 풀이도 쉽게 이해할 수 있습니다!!

 

일단 n = 1일 때는 답이 1, n = 2일 때는 답이 2라는 것은 쉽게 알 수 있습니다.

경우의 수를 구하는 문제이다 보니 일단 중학교, 고등학교 때 배운 수학으로 풀고 싶은데,, 쉽지 않아 보입니다. 접근법을 조금 바꿔서, 왼쪽에서부터 타일을 차근차근 채워간다고 생각하고 가장 왼쪽 위 칸부터 타일을 채우겠습니다. 이때 타일은 가로 또는 세로로 놓을 수 있을 것이고, 만약 해당 칸에 타일을 가로로 놓았다면 모든 칸을 채우기 위해 가장 왼쪽 아래 칸에도 타일을 가로로 놓아야 할 것입니다. 아래 그림은 n = 6일 때의 예시입니다.

 

풀이가... 보인다...

첫 타일을 가로로 놓는 모든 경우는 첫 타일을 세로로 놓는 모든 경우와 다릅니다. 두 경우가 겹치지 않으니 전체 경우의 수는 (첫 타일을 가로로 놓는 경우의 수) + (첫 타일을 세로로 놓는 경우의 수) 입니다.

 

첫 타일을 가로로 놓는 경우의 수는 어떻게 구할까요? 경우의 수는 위 이미지의 왼쪽 그림에서 흰 부분을 채우는 경우의 수와 같습니다. 흰 부분을 채우는 경우의 수는? 2×5 직사각형을 채우는 경우의 수와 같습니다. 그렇다면 첫 타일을 세로로 놓는 경우의 수는 어떨까요? 마찬가지로 2×4 직사각형을 채우는 경우의 수와 같습니다. 따라서 2×6 직사각형을 채우는 경우의 수는 2×5 직사각형을 채우는 경우의 수와 2×4 직사각형을 채우는 경우의 수를 더한 값과 같습니다.

 

그렇다면 2×5, 2×4 직사각형을 채우는 경우의 수는 어떻게 구할까요? 논리를 그대로 적용시키면 각각 2×4 경우의 수 + 2×3 경우의 수, 2×3 경우의 수 + 2×2 경우의 수와 같다는 것을 알 수 있습니다. 즉, 2×n 직사각형을 채우는 경우의 수를 $D(n)$이라고 하고 논리를 일반화하면 아래 식을 얻게 됩니다. 이러한 식을 점화식이라고 합니다.

 

$D(1) = 1, D(2) = 2, D(n) = D(n - 1) + D(n - 2)$

 

간단한 관계인데 굳이 식으로? 싶을 수 있지만 이런 습관을 들여야 대회 문제를 비롯한 문제를 풀기 쉽습니다.

 

위 식을 토대로 D값을 차례차례 구해주면 되는데, 코드를 짜는 건 한 문제만 더 알아보고 해 보도록 하겠습니다

 

예제2. 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

이 문제 역시 대표적인 DP 기초 문제 중 하나입니다.

 

2×n 타일링 문제와 비슷하게 시도해도 될까요?

$P(i)$를 아래에서부터 $i$번째 계단의 점수, $D(i)$를 아래에서부터 $i$번째 계단에서 출발하여 도착점까지 가며 얻을 수 있는 점수의 최댓값이라고 정의하겠습니다. 

계단이 N개라고 하면 $D(N) = P(N)$이고, 정답은 $D(1)$ 또는 $D(2)$가 되겠네요.

계단을 한 칸 또는 두 칸씩 올라갈 수 있으니 $D(i) = P(i) + max(D(i + 1), D(i + 2))$라고 정의하면 될까요? (max(a, b)는 a, b 중 작은 값을 의미합니다)

 

문제에서는 연속으로 세 칸을 오를 수는 없다고 했는데, $D(i)$는 연속으로 몇 칸 올랐는지에 대한 정보를 전혀 가지고 있지 않습니다!! 이 정보를 추가하려면 아무래도 D의 정의를 아예 수정해야 할 것 같습니다.

$D(i, j)$를 $i$번째 계단이고 $j$칸 연속으로 올라왔을 때 이제부터 얻을 수 있는 점수의 최댓값이라고 정의합시다.

세 칸 이상 연속으로 올라갈 수 없으니까 $j$는 1 또는 2라는 것을 알 수 있습니다. 만약 $j = 2$라면, 즉 지금까지 두 칸 연속으로 올라왔다면 다음에는 항상 두 칸을 올라가야 할 것이고, $j = 1$이라면 한 칸이나 두 칸 중 원하는 상황을 선택해도 됩니다. 식으로 정리하면 아래와 같습니다.

 

$D(i, 1) = max(D(i + 1, 2), D(i + 2, 1)) + P(i)$

$D(i, 2) = D(i + 2, 1) + P(i)$

 

이제 위 식을 따라 값을 차근차근 구하면 됩니다. 

 

그래서 코드로 어떻게 짜요

문제 풀이를 한다고 해 놓고 식만 구해놓으니 어떻게 풀라는 건지 알 방도가 없습니다. 

식을 바탕으로 문제를 풀기 위해서는 $D(1)$, $D(2)$, ... $D(N)$을 모두 구해야 합니다. 

구할 때 반복문으로 $D(1)$부터 $D(N)$까지 구하는 방법이 있고, 재귀함수로 $D(N)$부터 구하는 방법이 있습니다. 전자를 바텀-업(Bottom-up), 후자를 탑-다운(Top-down) 방식이라고 합니다.

 

아래는 2×n 타일링 문제를 바텀업 방식으로 푼 코드입니다.

#include <cstdio>
using namespace std;
 
int D[1005];
int main() {
    int n;
    scanf("%d", &n);
 
    D[1] = 1;
    D[2] = 2;
    for (int i = 3; i <= n; i++)
        D[i] = (D[i - 1] + D[i - 2]) % 10007;
 
    printf("%d", D[n]);
}

탑다운 방식으로 풀 때는 조금 복잡합니다. 식을 그대로 재귀함수로 구현하면 아래 코드처럼 됩니다.

#include <cstdio>
using namespace std;
 
int D(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return D(n - 1) + D(n - 2);
}
 
int main() {
    int n;
    scanf("%d", &n);
    printf("%d", D(n));
}

이렇게 짜면 문제를 풀 수 있을까요? 아쉽게도 이 코드를 제출하면 시간 초과를 받습니다.

그 이유는 중복되는 값을 너무 많이 계산하기 때문입니다. n = 10일 때, 위 코드는 D(8)을 2번, D(7)을 3번, D(6)을 5번 ... D(2)를 34번, D(1)을 55번 호출합니다. n이 100, 1000이 된다면 중복 호출이 훨씬 더 많아질 것입니다. D(6)은 몇천 번을 계산해도 13인데 굳이 D(6)이 호출될 때마다 매번 D(5)와 D(4)를 호출할 필요가 있을까요? D(6)을 계산하고 그 값을 저장해두고, 나중에 D(6)을 또 호출한다면 그냥 저장한 값을 돌려주면 되지 않을까요?

이렇게 계산한 값을 저장해 두고 계속 재사용하는 기법을 '메모'한다는 의미의 메모이제이션이라고 부릅니다. 아래는 메모이제이션을 적용한 탑다운 코드이며, 이 코드에서는 모든 D값을 한 번만 계산하기 때문에 시간 초과가 나지 않습니다.

#include <cstdio>
using namespace std;
 
int memo[1005];
int D(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (memo[n] != 0) return memo[n];
    memo[n] = (D(n - 1) + D(n - 2)) % 10007;
    return memo[n];
}
 
int main() {
    int n;
    scanf("%d", &n);
    printf("%d", D(n));
}

계단 오르기 문제도 비슷하게 풀 수 있습니다. 

이 문제에서 우리는 D(1)을 시작으로, D(N)을 도착으로 정의했기 때문에 탑다운 방식은 D(1)부터, 바텀업 방식은 D(N)부터 계산합니다. 아래는 각각 바텀업, 탑다운 코드입니다.

+ min, max 함수는 <algorithm> 헤더에 정의되어 있습니다

#include <cstdio>
#include <algorithm>
using namespace std;
 
int D[305][3], P[305];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &P[i]);
    
    D[n][1] = D[n][2] = P[n];
    D[n - 1][1] = P[n] + P[n - 1];
    D[n - 1][2] = 0;
    for (int i = n - 2; i >= 1; i--) {
        D[i][1] = max(D[i + 1][2], D[i + 2][1]) + P[i];
        D[i][2] = D[i + 2][1] + P[i];
    }
 
    printf("%d", max(D[1][1], D[2][1]));
}

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
int memo[305][3], P[305], n;
int D(int i, int j) {
    if (i == n) return P[n];
    if (i == n - 1 and j == 1) return P[n] + P[n - 1];
    if (i == n - 1 and j == 2) return 0;
    if (memo[i][j] != -1) return memo[i][j];
 
    if (j == 1)
        memo[i][j] = max(D(i + 1, 2), D(i + 2, 1)) + P[i];
    else
        memo[i][j] = D(i + 2, 1) + P[i];
    return memo[i][j];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &P[i]);
    
    memset(memo, -1, sizeof memo);
    printf("%d", max(D(1, 1), D(2, 1)));
}

 

어떤 문제가 다이나믹 프로그래밍 문제인가요?

우리가 풀었던 문제들을 찬찬히 되짚어봅시다. 

2×n 타일링 문제에서는 D(n)을 구하기 위해 D(n - 1)과 D(n - 2)라는 부분문제의 답이 필요했습니다. 그런데 이 부분문제들은 전체 문제인 D(n)과 정확히 같은 문제였습니다. 계단 오르기 문제는 인수가 두 개라서 헷갈리지만, 결국 부분 문제와 전체 문제가 같다는 점은 동일합니다.

이렇게 문제가 재귀적인 구조를 가지고 있으면 다이나믹 프로그래밍으로 풀 수 있을 확률이 높습니다.

 

이건 약간 야매긴 한데,, 경우의 수를 구하는 문제나 "답을 1000000007로 나눈 나머지를 출력하라" 같은 말이 있으면 다이나믹 프로그래밍 문제일 확률이 큽니다 물론 아닐 수도 있고.. 이런 말 없어도 다이나믹 프로그래밍일 수도 있고.. 문제를 많이 풀어보면 감이 생깁니다.

 

연습 문제

점화식과 코드 정도만 간략하게 쓰겠습니다.

연습 문제는 많이 추천하지 않았는데,, 여기 문제들 하나씩 차례차례 풀어보면 좋을 것 같습니다

한 2~30분 생각해도 모르겠으면 풀이 검색해보는 걸 추천해요

 

https://www.acmicpc.net/problem/11727 😿

11727번: 2×n 타일링 2

2×n 타일링 문제를 이해했다면 풀 수 있습니다. 풀이는 비슷하니까 생략하겠습니다.

---

https://www.acmicpc.net/problem/1463 😿😿

1463번: 1로 만들기

D(X)를 X를 1로 만들기 위해 필요한 연산의 횟수라고 정의하겠습니다.

D(X) = min(D(X / 3), D(X / 2), D(X - 1)) + 1

물론 X가 3의 배수 / 2의 배수가 아니라면 D(X / 3), D(X / 2)는 쓸 수 없습니다

http://boj.kr/ca6b2db0ec774974b2bc26d729141583

---

https://www.acmicpc.net/problem/11048 😿😿

11048번: 이동하기

D(i, j) = i행 j열에서 출발할 때 먹을 수 있는 사탕 개수의 최대, P(i, j) = i행 j열의 사탕 개수라고 할 때

D(i, j) = max(D(i + 1, j), D(i, j + 1), D(i + 1, j + 1)) + P(i, j) 입니다.

이렇게 이차원 격자에서 한쪽 방향으로만 움직일 수 있는 상황에서의 DP는 정말 자주 나오는 유형입니다.

http://boj.kr/5dc82a5cca704880afac7df53cd2f4f7