정수삼각형 문제

프로그래머스 '동적계획법(DP)' 카테고리에 포함된 정수 삼각형 문제. 위에서부터 1층, 2층 ... 이라고 정의했을 때, 1층부터 마지막 층 까지 이동경로상의 숫자의 합의 최댓값을 구해야 한다.
DP카테고리에 있으니 당연히 DP로 풀었지만, 어디선가 이 문제를 다익스트라 알고리즘으로 풀 수 있다는 말을 들어서 한 번 시도해 보았다.

How?

Dijkstra's Algorithm 이란?
: Weighted Graph의 하나의 정점에서 다른 모든 정점까지의 최단/최장경로를 구하는 알고리즘
출처: https://hsp1116.tistory.com/42

1) 주어진 정수삼각형이 Weighted Graph로 표현될 수 있음
2) 구하고자 하는 값 = max(마지막 층 node까지 최장경로)

node(0,0)을 시작으로 node(마지막층, n)까지의 최장경로 중 가장 큰 값을 선택하면 된다!!

소스 코드

//Dijkstra
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
#define min -987654321
using namespace std;

int dist[501][501]; 
int solution(vector<vector<int>> data) {
    for (int i=0; i<data.size(); i++) {
        for (int k=0; k<data[i].size(); k++) {
            dist[i][k] = min;
        }
    }
    
    priority_queue<pair<int,pair<int,int>>> q;
    priority_queue<int> ans;
    dist[0][0] = data[0][0];
    q.push({dist[0][0], {0, 0}});
    
    while (!q.empty()) {
        int cost = q.top().first;
        int hX = q.top().second.first;
        int hY = q.top().second.second;
        q.pop();
        
        if (hX == data.size()-1) {
            ans.push(cost);
            continue;
        }
        
        //왼쪽 아래
        int nX = hX+1;
        int nY = hY;
        int nCost = data[nX][nY];
        if (dist[nX][nY] < dist[hX][hY] + nCost) {
            dist[nX][nY] = dist[hX][hY] + nCost;
            q.push({dist[nX][nY], {nX, nY}});
        }
        //오른쪽 아래
        nY = hY+1;
        nCost = data[nX][nY];
        if (dist[nX][nY] < dist[hX][hY] + nCost) {
            dist[nX][nY] = dist[hX][hY] + nCost;
            q.push({dist[nX][nY], {nX, nY}});
        }
    }
    
    
    return ans.top();
}

그 결과,

인생..

이런 결과가 나왔다.

그니깐, 결과는 잘 나왔지만 시간 복잡도가 형편없다는 말인데...

시간복잡도

시간복잡도 비교해보기전에 내가 짠 dp소스코드도 함 보자..

// DP
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int d[501][501];

int solution(vector<vector<int>> data) {
    vector<int> answer;
    
    d[0][0] = data[0][0];
    for (int i=1; i<data.size(); i++) {
        for (int j=0; j<data[i].size(); j++) {
            if (j==0) {
                d[i][j] = d[i-1][j] + data[i][j];
            } else if (j==data[i].size()-1) {
                d[i][j] = d[i-1][j-1] + data[i][j];
            } else {
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + data[i][j] ;
            }
            
            if (i==data.size()-1) {
                answer.push_back(d[i][j]);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return *(answer.end()-1);
}

DP 알고리즘은 더도말고 덜도말고 1층부터 모든 층을 방문하며, 한 번씩계산한다. 즉 시간복잡도는 O(N) 이 된다는 의미.

다익스트라 알고리즘의 시간 복잡도는 그래프의 간선의 개수(E)와 정점의 개수(V)를 이용해 O(ElogV) 로 표현한다 (우선순위 큐를 사용한 경우.)
이를 정수삼각형 Data의 개수인 'N'으로 표현해보면
1. E = N-1
2. V = N
즉 최종 시간복잡도는 O(NlogN) 이 되겠다.
( ElogV => (N-1)logN => NlogN )

결론

DP와 다익스트라로 모두 풀 수 있을때는 (아마) 대부분의 상황에서 DP가 훨씬 좋은 선택이 될 듯 하다.