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