동적 계획과 최적화 문제, Triangle Path(알고스팟)

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

동적 계획법으로 최적해 찾기

동적 계획법은 일반적으로 최적화 문제의 해결을 위해 사용된다. 최적화 문제는 가능한 여러 답 중 가장 좋은 답을 찾는 문제로, 최적화 문제의 동적 계획 역시 완전 탐색에서 시작하지만 어떤 조건이 만족하면 좀 더 효율적으로 구현 가능하다.

최적 부분 구조

완전 탐색의 어떤 부분 문제에 대해 어떤 경로로 해당 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없는 문제를 최적 부분 구조를 가진다고 말한다. 이런 문제는 각 부분 문제의 최적해를 통해 전체 문제의 최적해를 쉽게 얻어낼 수 있다.

 

예를 들어, 서울에서 부산까지의 최단 경로를 구할 때 최단 경로가 대전을 지난다면, 서울-대전과 대전-부산의 각 최단 경로를 이어 항상 서울-부산의 최단 경로를 구할 수 있다. 

Triangle Path(링크)

순수한 완전 탐색으로 작성한 trianglePath 함수에서는 각 지점에서 바로 아래 혹은 오른쪽 아래의 경로를 택하고 해당 경로의 값을 모두 더한 sum 변수를 가진 채로 계속 재귀에 진입한다. 즉, 지나온 모든 경로에 대한 정보를 항상 전달해야 한다.

 

그런데, 각 위치에 대해 앞으로 밟아 나가야 할 최적의 경로가 일정하게 존재하므로 어떤 위치에 있건 지나온 경로와 관계 없이 최적의 결과를 위한 경로가 정해져 있다. (각 부분 문제의 최적해의 합은 전체 문제의 최적해.)

 

따라서, 이 문제는 최적 부분 구조를 가진다고 할 수 있으며 각 지점에 대한 최적해만을 캐싱하면 쉽게 memoization 을 활용할 수 있다. 각 지점에서 지나온 경로의 값들을 가질 필요가 없이, 각 지점에서 시작하는 부분 경로의 최대치를 반환하면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> triangle;

void printTriangle(const vector<vector<int>>& triangle) {
    cout << endl;
    for (const auto& row: triangle) {
        for (const auto& e: row) 
            cout << e << " ";
        cout << endl;
    }
}

// Maximum input is 100.
int cache[100][100];

int trianglePathMemoization(int y, int x) {
    // Base case
    if (y == triangle.size() - 1) return triangle[y][x];

    int& ret = cache[y][x];
    if (ret != -1) return ret;

    return ret = triangle[y][x] + max(trianglePathMemoization(y + 1, x), trianglePathMemoization(y + 1, x + 1));
}

int trianglePath(int y, int x, int sum) {
    // Base case: When you get the the lowest row, return sum.
    if (y == triangle.size() - 1) return sum += triangle[y][x];

    // Add current value.
    sum += triangle[y][x];

    // Task piece: Take each path and get the maximum sum.
    return sum = max(trianglePath(y + 1, x, sum), trianglePath(y + 1, x + 1, sum));
}

int main() { 
    int C; cin >> C;
    vector<int> answers;

    while (C-- > 0) {
        int len; cin >> len;
        memset(cache, -1, sizeof(cache));

        vector<int> row;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < i + 1; ++j) {
                int num; cin >> num;
                row.push_back(num);
            }
            triangle.push_back(row);
            row.clear();
        }
        
        answers.push_back(trianglePathMemoization(0, 0));
        //answers.push_back(trianglePath(0, 0, 0));
        triangle.clear();
    }

    for (const auto& e: answers) cout << e << endl;

    return 0;
}