소프티어

안녕하세요, Softeer 개발 인턴 김해울 입니다.

이번 글에서는 다이나믹 프로그래밍 (DP)에 대해 얘기해 보자 합니다.

코딩 테스트 빈출 알고리즘이면서 개념적으로는 단순해 보이지만 문제마다 해야 하는 것이 다양해선 제가 처음 공부할 때 굉장히 많은 어려움을 겪은 알고리즘인데요 이번 글에서는 제가 DP 문제를 접근하는 법에 대해 설명해 보자 합니다.

**주의 : 어느정도 독자가 DP를 접해본 경험이 있음을 가정합니다!**

선행지식

• 다양한 유형의 기초적인 DP 문제들을 풀어본 경험
• 그래프 이론 (위상 정렬, 깊이 우선 탐색)

DP를 처음 배울 때 가장 어렵게 다가오는 요소는 점화식을 세우는 과정이라고 생각됩니다. 실제로 저는 DP를 처음 접할 때 대부분의 자료들은 초항, 부분 문제, 탑 다운, 바텀 업, 메모이제이션 등에 집중해서 설명하는 자료들이 대부분이라고 느꼈습니다. 처음 DP를 배울 때도 "그래서 이거 점화식은 어떻게 세우나요?"라는 질문을 자주 했고 이런 질문을 하시는 분들도 종종 접하게 되는 것 같습니다.

물론 위에 언급한 개념들은 DP로 문제를 모델링 할 때 필수적인 요소들이고 중요하지만 저 요소들에만 집중하는 것이 DP에 대한 이해를 다양한 유형의 DP로 확장 시키거나 적용하는 데 어려움을 유발하는 하나의 요소라고 생각합니다.

조금 더 부연 설명을 해보자면 피보나치 수를 구하는 점화식은 배열과 반복문 정도만 알아도 쉽게 점화식으로 표현하고 코드로 구현하는 것이 가능합니다.

$$f(i) = f(i-1) + f(i-2)$$

하지만 트리에서의 DP, 격자 그래프에서의 DP, 구간을 이용한 DP 등의 유형을 처음 공부하는 경우에 부모 정점과 자식 정점 사이 관계, 배열 내 특정 구간의 합 등을 정확하게 수학적으로 표현하고 점화식으로 풀어내는 것은 어려울 수 있습니다. 오히려 이걸 무조건 점화식으로 표현할 필요가 없을 수도 있습니다.

결국 저히 목적은 문제를 푸는 코드를 작성하는 것이지 점화식을 정확하게 쓰는 건 아니니까요. 이 글에서는 이렇듯 DP와 굉장히 밀접해 있고 문제를 풀 때 도움이 될 수 있는 요소와 연관 지어 소프티어에 있는 DP 연습 문제들을 몇 개 다뤄보려고 합니다.

방향 비순환 그래프/Directed Acylic Graph (DAG)

제 경험상 저의 DP에 대한 이해는 DP를 방향 비순환 그래프 (이하 DAG)로 보기 전과 후로 극명하게 갈립니다. DAG는 거의 모든 유형의 DP의 모든 요소를 단 한 종류의 그래프로 나타낼 수 있기 때문입니다.

먼저 이름에서 유추 가능하듯이 DAG는

1. 간선들이 방향을 가지며
2. 사이클이 존재하지 않는 그래프 입니다.

아래는 DAG의 예시입니다.

위상 정렬

DP와 DAG의 연관성을 알기 위해서는 위상 정렬을 이해해야 합니다. 위상 정렬이란 DAG에서 모든 방향 간선 $u \rightarrow v$에 대해 $u$가 $v$보다 먼저 오게끔 선형으로 나열/정렬하는 알고리즘입니다. 앞서 보여드린 예시 DAG를 위상 정렬하면 $0 3 1 2 4 5$ 또는 $0 1 3 2 4 5$ 등이 결과로 나올 수 있게 됩니다. (연결된 정점들 사이 순서만 중요함으로 결과가 여러 개 나올 수 있습니다.)

위상 정렬의 대표적인 활용은 의존성 해결에 있습니다. 그래프의 각 정점이 어떤 작업을 의미하고 간선 $u \rightarrow v$는 $v$를 시작하기 전에 $u$가 완료돼야 함을 의미한다고 생각해 봅시다. 이는 작업 $v$가 작업 $u$에 의존한다고 볼 수 있습니다. 그리고 이 그래프를 위상 정렬해서 나오는 결과는 의존성이 해결된 유효한 작업 처리 순서가 됩니다.

그런데 여기서 의존성이 사이클을 이룬다면 어떨까요? 아쉽게도 위상 정렬이 불가능합니다. 조건에 위배되지 않게 작업들에 순서를 매길 수 없기 때문이죠. 따라서 위상 정렬을 하기 위해서는 그래프가 방향 비순환 그래프 여야 합니다.

위상 정렬을 하는 방법 자체는 이 글의 주된 주제와 연관은 없으니 따로 다루지 않고 넘어가도록 하겠습니다.

DP와 DAG의 연관성

여기까지 왔다면 DP와 DAG 사이 관계를 이해할 준비가 다 되었는데 이는 바로 "DP 문제의 점화식은 DAG로 표현 가능하다"입니다. 예시를 보며 이해해 보도록 합시다.

아래 그래프를 봅시다.

DAG라는 점을 제외하면 단순 평범한 그래프처럼 보입니다. 하지만 이는 피보나치 수를 5번째 항까지 계산하는 점화식을 그래프로 나타낸 것입니다.

피보나치 수의 $i$ 번째 항은 $i-1$ 번째 항과 $i-2$ 번째 항의 합으로 계산됩니다. 이를 다르게 말하면 피보나치 수의 $i$ 번째 항을 계산하기 위해서는 $i-1$ 번째 항과 $i-2$ 번째 항이 필요하며 두 값을 모르는 상태로 $i$ 번째 항은 계산할 수 없습니다. 이는 결국 $i$ 번째 항은 $i-1$ 번째 항과 $i-2$ 번째 항에 의존한다는 의미인 것을 알 수 있습니다.

의존성이 존재함으로 각 항을 정점에 저장된 값으로 나타내고 의존성을 간선으로 나타내면 방향 그래프를 만들 수 있습니다. 동시에 사이클이 존재하지 않기 때문에 DAG입니다.

정점들에 값을 적어보면 좀 더 확실하게 이것이 피보나치 수에 해당하는 점화식과 동일함을 알 수 있습니다.

이 내용을 일반화 시켜 봅시다. 결국 DP에서 해결하고자 하는 "문제"는 어떤 주어진 정점에 저장된 값 등을 구하는 것이고 "부분 문제"를 해결하는 것은 "문제"가 의존하고 있는 정점들의 값을 구하는 것이며 점화식으로 표현되는 "부분 문제들 사이 관계"가 결국 의존성을 정의하는 방향 간선이 됩니다.

DP를 DAG로 해석할 때 장점은 저는 크게 3가지가 있다고 생각합니다.

1. 상태 공간이 복잡해져도 쉽게 적용/확장 가능하다는 점
2. 실제 구현 때 값들을 계산해야 하는 순서를 쉽게 보일 수 있다는 점
3. 바텀 업과 탑 다운을 동시에 잡을 수 있다는 점

위 장점들을 아래에서 소프티어 연습문제들을 풀어보며 이해해 보도록 합시다.

상태와 전이

정점이라는 것이 꼭 정수 하나를 나타낼 필요는 없습니다. 그래프 문제를 많이 풀어보셨다면 아시겠지만 정점은 결국 어떠한 상태를 나타내는 수단이고 간선은 이 상태들 사이 관계, 즉 상태 전이를 나타내는 수단입니다. 

정점과 간선이 DAG의 형태를 그리게 잘 정의해 줬다면 그다음으로 해야 할 것은 실제로 값들이 계산되는 순서가 지금 답을 계산하고자 하는 상태에 대해 그 상태가 의존하는 모든 상태들이 먼저 계산되어 있음을 보장하는 것입니다.

몇 가지 방법 및 유형을 소개하겠습니다.

**풀이는 문제에 대해 충분히 고민해 본 후 보시면 더 좋습니다!**

• [21년 재직자 대회 예선] 로드 밸런서 트래픽 예측

실제로 그래프 상에서 DP를 돌리는 문제입니다. 

지문이 복잡하게 쓰여 있지만 결국 $r_i$는 어떤 정점에서 나가는 간선의 개수 즉 진출 차수이며 $x_i$값을 $(x_i \mod r_i) + 1$로 바꾼다는 건 나가는 간선이 주어진 순서대로 트래픽을 돌아가며 전달한다는 의미입니다.

구성된 그래프에서 사이클이 존재하지 않는다는 조건에서 그래프가 DAG 임을 유추할 수 있습니다. 따라서 이 문제 같은 경우 정점과 간선 자체는 이미 정의가 되어 있으니 값을 어떻게 계산할지에만 집중해 보도록 합시다.

입력 예시 1의 그림을 봅시다.

앞서 DAG에서 의존성 해결을 위해 위상 정렬을 사용한다고 언급했습니다. 따라서 이 문제의 경우 위상 정렬을 통해 DP 값을 계산하는 순서를 보장해야 합니다. 위 그래프를 위상 정렬해서 나올 수 있는 결과로는 $1, 5, 8, 2, 4, 3, 6, 7$이 있습니다. 그리고 실제로 이 순서대로 문제에 주어진 규칙에 따라 연결된 정점들에 트래픽을 보내주면 문제가 해결됩니다.

$dp[i]$를 $i$번 서버에 들어온 요청 수로 정의합시다. 모든 요청이 처음은 $1$번 서버로 들어오기 때문에 $dp[1] = K$입니다. 그 후 위상 정렬된 순서대로 연결된 서버들에 트래픽을 넘겨줍니다. 

이때 $K$값이 굉장히 클 수 있기 때문에 실제로 돌아가면서 한 개씩 전달하면 시간 초과가 발생하게 되고 $dp[i]$를 $i$번 정점의 진출 차수로 나눈 몫만큼을 한 번에 전달한 후 남은 나머지만큼만 한 개씩 전달해야 충분히 빠르게 값을 계산할 수 있습니다.

여기서 눈치채면 좋은 것은 $1$번 정점은 의존하고 있는 정점이 없다는 것입니다. 따라서 이 정점이 점화식의 초항에 해당하는 정점이 되기 때문에 답이 독립적으로 계산돼야 합니다. (이 문제의 경우 입력에 주어진 $K$값이었죠.)

코드(C++):

#include <bits/stdc++.h>
using namespace std;


using ll = long long;


ll n, k;
vector<int>edges[100005]; // 인접리스트
ll outdegree[100005]; // 진출 차수
ll indegree[100005]; // 진입차수
ll dp[100005]; // dp값을 저장할 배열 : dp[i] = i번 정점에 들어온 요청 개수


vector<int>topologic; //위상 정렬 결과


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> outdegree[i];
        for(int j=0; j<outdegree[i]; j++){
            int dest; cin >> dest;
            indegree[dest]++;
            edges[i].push_back(dest);
        }
    }
    // 위상 정렬 과정 (궁금하면 위상 정렬 관련 자료를 추가로 찾아보시면 좋습니다!)
    queue<int>q; q.push(1);
    topologic.push_back(1);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int &nxt:edges[cur]){
            indegree[nxt]--;
            if(!indegree[nxt]){
                q.push(nxt);
                topologic.push_back(nxt);
            }
        }
    }
    
    dp[1] = k; // 1번 정점의 답 설정
    for(int &cur:topologic){ // 위상 정렬된 순서대로 앞에서 부터 계산
        for(int &nxt:edges[cur]){
            dp[nxt] += dp[cur]/outdegree[cur]; // 몫만큼 전달
        }
        int cnt = 0;
        for(int &nxt:edges[cur]){
            if(cnt==dp[cur]%outdegree[cur]) break; 
            dp[nxt] += 1; // 나머지만큼만 1개씩 전달
            cnt++;
        }
    }
    for(int i=1; i<=n; i++) cout << dp[i] << ' ';
}

코드에서 위상 정렬 과정이 궁금하다면 위상 정렬에 대해서 따로 찾아 보시는 것을 추천 드립니다!

• 나무 수확

격자에서 DP를 돌리는 문제입니다.

인접한 오른쪽 혹은 아래쪽 중 한곳을 선택하여 이동한다는 조건이 주어져 있는데 이 조건이 바로 이 격자를 DAG로 만들어 줍니다. (위나 왼쪽으로 돌아갈 수 없기 때문)

여기서 잠깐 문제에서 벗어난 얘기를 하자면 격자 그래프 하면 떠오르는 대표적인 알고리즘으로는 BFS가 있는데요 이렇게 격자임에도 DAG의 형태를 이룬다면 BFS보다는 DP 일 확률이 경험상 조금 더 높은 거 같습니다.

어떤 문제가 BFS 인지 DP 인지 알아차리기가 저도 처음엔 어려웠습니다. 하지만 이 문제와 같이 "인접한 오른쪽 혹은 아래쪽 중 한곳을 선택한다" 또는 "인접한 칸 중 값이 더 큰 값만 방문 가능하다" 등 방문 가능한 칸들에 어떠한 단조성을 부여하는 조건이 있을 경우 그래프를 DAG로 만들어주기 위한 조건일 가능성이 높아 DP를 한번 의심해 봐도 좋습니다. (DP로 만 풀리거나 BFS로 풀리더라도 DP 풀이가 훨씬 간단한 경우가 많습니다.)

문제로 돌아와 봅시다. 스프링클러를 무시하고 문제를 일단 풀어봅시다. $i$행 $j$열에 있는 칸을 $(i, j)$라고 합시다. 

어떤 $(i, j)$로 들어올 수 있는 칸은 위나 왼쪽 칸, 즉 $(i-1, j)$ 또는 $(i, j-1)$ 밖에 없습니다. 따라서 $dp[i][j]$를 $i$행 $j$열까지 움직였을 때 최대 열매 수확량이라고 정의하면 그 칸의 열매 수확량이 $v[i][j]$라 했을 때 $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + v[i][j]$임은 자명합니다.

그러면 이제 어떤 어떤 $(i, j)$에 대한 값을 계산하기 전에 $(i-1, j)$와 $(i, j-1)$에 대한 답이 계산되어 있음을 어떻게 보장할까요? 정답은 간단합니다. 이중 반복문을 통해 행의 번호를 증가시키며 각 행마다 열의 번호가 증가하는 순으로 답을 계산해 나가면 됩니다. 이런 식으로 dp 값의 계산 순서를 자연스럽게 보장해 주는 문제의 어떠한 특징이나 성질을 저는 보통 DP의 단조성이라고 부릅니다. (공식 명칭은 아닙니다.)

다시 원본 문제로 돌아와서 스프링클러를 고려하면 문제를 어떻게 풀까요? 몇 가지 방법이 있지만 제가 생각했을 때 알아두면 다양한 문제들에 확장 가능한 풀이를 소개해드리고 자 합니다.

경로의 시작점과 끝점이 각각 $(1, 1)$과 $(N, N)$으로 고정되어 있습니다. 

따라서 답이 되는 경로상의 $(i, j)$를 기준으로 경로를 $(1, 1)$에서 $(i, j)$로 가는 경로 그리고 $(i, j)$에서 $(N, N)$으로 가는 경로로 분리해서 생각해 볼 수 있습니다. 

그리고 $(i, j)$에서 $(N, N)$으로 가는 경로는 $(N, N)$에서 $(i, j)$로 가는 역방향 경로(왼쪽과 위로만 가는)와 동일합니다. 

$(N, N)$에서 시작해서 $(i, j)$까지 역방향으로 갈 때 최대 수확량을 $rdp[i][j]$라고 합시다. 정의는 $dp[i][j]$와 같지만 이 경우 행과 열의 번호가 감소하는 순서로 계산을 해줘야 합니다. 

$dp$와 $rdp$를 모두 계산했다면 저희는 모든 $(i, j)$에 대해 각각 $(1, 1)$에서 $(i, j)$로 갈 때 최대 열매 수확량과 $(N, N)$에서 $(i, j)$에 역방향으로 갈 때 최대 열매 수확량을 모두 가지고 있습니다.

이제 $dp[i][j] + rdp[i][j]$는 $(i, j)$를 무조건 지나고 두 번 포함 시키는 (각각 $dp[i][j]$와 $rdp[i][j]$에 한 번씩 포함되었기에) $(1, 1)$에서 $(N, N)$까지 경로의 최대 수확량임을 알 수 있습니다. 이는 $(i, j)$에 스프링클러를 설치했다고 가정하는 것과 동치입니다.

따라서 답은 $dp[i][j] + rdp[i][j]$ 중 가장 큰 값이 됩니다. $dp$ 계산에 $N^2$, $rdp$ 계산에 $N^2$, 그리고 답이 최대가 되는 $(i, j)$를 찾는데 $N^2$ 시간이 필요함으로 총 시간 복잡도는 $\mathcal{O}(N^2)$입니다. $N$이 최대 $1000$이니 이는 충분히 빠릅니다.

이렇듯이 어떤 상태를 두 번 포함해야 하거나 포함해야 하지 않는 경우 그 상태까지 답을 정방향과 역방향으로 따로 계산한 값을 이용해서 합치거나 분리하는 방법으로 풀 수 있는 경우가 자주 나오니 알아두시면 좋을 것 같습니다.

코드(C++):

#include <bits/stdc++.h>
using namespace std;

int n;
int v[1005][1005];
int dp[1005][1005];
int rdp[1005][1005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> v[i][j];
        }
    }

    // 정방향 계산
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dp[i][j] = max(dp[i][j], max(dp[i-1][j]+v[i][j], dp[i][j-1]+v[i][j]));
        }
    }

    // 역방향 계산
    for(int i=n; i>=1; i--){
        for(int j=n; j>=1; j--){
            rdp[i][j] = max(rdp[i][j], max(rdp[i+1][j]+v[i][j], rdp[i][j+1]+v[i][j]));
        }
    }

    int ans = 0; // 최종 답 계산
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ans = max(ans, dp[i][j] + rdp[i][j]);
        }
    }
    cout << ans;
}

탑 다운? 바텀 업?

DP를 DAG로 접근하면 좋은 이유로 탑 다운과 바텀 업을 동일 선상에서 이해 가능하다는 점을 언급했습니다. 다시 한번 앞서 DAG에서 의존성을 해결하기 위해 위상 정렬을 사용한다 했고 바텀 업이 더 작은 부분 문제를 계산한 후 그 결과를 통해 더 큰 문제를 해결하는 과정임을 생각해 보면 이는 결국 DAG가 위상 정렬된 순서대로 문제를 해결하는 과정임을 알 수 있습니다.

그러면 탑 다운은 뭘까요? 탑 다운은 큰 문제에서 시작해서 그 문제를 해결하기 위해 필요한 부분 문제들을 재귀적으로 해결한 후 전부 호출이 완료되면 돌아와서 큰 문제를 해결하는 방식입니다. 이름이 조금 직관적이지 않은 감은 있지만 결국 위에서 아래로 내려간 후 다시 쌓아 올리는 형태인 것입니다. 이를 DAG에 대입해서 생각해 보면 간선들의 방향을 뒤집은 후 답을 계산하고자 하는 정점에서 시작하는 DFS와 동일함을 알 수 있습니다. 일반적인 DFS의 방문 체크가 "그 정점에 대해서 이미 답을 구했는가?"라는 형태로 바뀌는 정도의 차이가 있겠죠. (이게 결국 메모이제이션 입니다.)

어떤 정점에서 재귀적으로 부분 문제들을 호출하며 깊게 들어가다 보면 다른 문제에 의존하고 있지 않은 부분 문제가 나오게 되는데 이것이 결국 재귀 호출의 base case 이자 탑 다운 DP에서의 초항임을 알 수 있으며 이러한 호출 방식이 DFS와 동일한 형태임을 알 수 있습니다.

정리

이제 글의 맨 위에서 언급한 DP의 기초 요소들을 DAG에 대입해서 생각해 보자면 : 

• 초항 : 진입 차수가 0인 (의존성이 없는) 정점
• 부분 문제 : 어떤 정점으로 들어오는 (그 정점이 의존하고 있는) 정점들
• 점화식 : 정점들 사이 연결 관계(간선/의존성)에 대한 정의
• 탑 다운 : DFS
• 바텀 업 : 위상 정렬
• 메모이제이션 : 정점(상태)에 해당하는 답을 기록해두는 행위

정도로 생각해 볼 수 있겠네요!

물론 이러한 이해에도 한계가 없는 것은 아닙니다.

• 일반적으로 문제를 해결할 때 명시적으로 흔히 생각하는 '그래프'를 만드는 것은 아니기 때문에 실제 구현과의 괴리가 있을 수 있다.
• 무조건 그래프로만 표현하는 것도... 비효율적이다. (점화식이 단순하거나 점화식을 통해 이해하는 것이 간편한 경우)

따라서 결국 다양한 문제들을 풀어보며 내가 편한 접근 방법을 찾아가는 과정이 중요합니다.

그럼에도 불구하고 이 글을 써본 이유는 저도 처음에 DP 자체에 대해 이해하는데 큰 어려움을 겪었고 이러한 해석을 알게 된 후에야 DP를 비로소 이해했다고 느꼈던 경험이 있어서 저와 비슷한 어려움을 겪으시는 분들에게 "DP는 DAG다"와 같은 해석도 가능함을 알려드리기 위해서입니다.

도움이 되셨으면 좋겠습니다! 아래에 추천 연습 문제를 몇 개 드렸으니 풀어보시면 감사하겠습니다!

연습 문제

몇 가지 연습문제를 이제 스스로 풀어봅시다!

• 징검다리 : LIS라는 유명한 유형의 DP 문제입니다.
• 효도 여행 : 트리는 방향이 없는 단순 사이클이 없는 그래프입니다. 루트를 고정함으로써 DAG와 비슷한 형태를 만들 수 있을지도...?
• 복잡한 조립라인 2 : 개인적으로 위 문제보다 더 쉽다고 생각합니다. 정방향 역방향을 잘 이용해 봅시다.
• [한양대 HCPC 2023] Pay2Win : 실제로 필요한 값들에 대한 정보만 저장해 메모리와 시간을 아끼는 방안을 생각해 봅시다.
• [한양대 HCPC 2023] Hanyang Cherry Picking Contest : 게임 이론이 접목된 문제. 상태 정의 자체를 어떻게 할지 고민해 봅시다.

읽어주셔서 감사합니다!