종만북(프로그래밍 대회에서 배우는 알고리즘 문제해결 전략) 을 공부하면서 대표적인 dynamic programming인 정수 삼각형 문제를 풀어보았다.

문제

프로그래머스에서 같은 문제가 있길래 가져왔다. 문제에서 다음과 같이 주어졌을 때는 greedy 알고리즘으로는 오답이 나온다는 것을 알 수 있다.

빨간색은 dp를 활용한 것이고 파란색은 greedy 알고리즘을 이용한 경우의 수이다.

문제를 푸는 첫번째 방법

모든 경우의 수를 살펴서 찾아본다.

int dp(int y, int x, vector<vector<int>>& triangle){
   //기저 사례
   if(y == triangle.size() - 1) return triangle[y][x];
   return max(dp(y + 1, x, triangle), 
              dp(y + 1, x + 1, triangle)) + triangle[y][x];
	}

재귀를 이용하여 모든 경로의 수를 탐색하는 수이다.

테스트는 통과되었으니 제출을 해보자.

효율성 부분도 있지만 역시 전부 실패로 뜨고 있어서 생략한다.
이것을 해결을 하기 위해 dp 를 활용해보자.

문제를 푸는 두번째 방법

int cache[500][500][500];

int dp(int y, int x, int sum, vector<vector<int>>& triangle){
   //기저 사례
   if(y == triangle.size() - 1) return sum + triangle[y][x];
   //메모이제이션
   int& ret = cache[y][x][sum];
   if(ret != 0) return ret;
   //재귀
   sum+=triangle[y][x];
   return ret = max(dp(y + 1, x, sum, triangle), dp(y + 1, x + 1, sum, triangle));
}

dp를 활용하여 다시 문제를 풀어보았고 제출을 해보았다.

안된다.

해결법

입력 걸러내기

dp(int y, int x, int sum, vector<vector<int>>& triangle)

1. y와 x는 재귀 호출이 풀어야 할 부분문제를 지정함. 두 입력으로 경로가 정해짐
2. sum은 지금까지 어떤 경로로 이 부분 문제에 도달 했는지 나타낸다. 여태까지 풀었던
   조각들에 대한 정보를 주는 입력

여기서 최대경로는 sum이 얼마건 상관없이 똑같다.
재귀함수에 sum을 아예 입력으로 받지 않도록 알고리즘을 작성하면 훨씬 빨라진다.

결론

int cache[500][500];

int dp(int y, int x, vector<vector<int>>& triangle){
   //기저 사례
   if(y == triangle.size() - 1) return triangle[y][x];
   //메모이제이션
   int& ret = cache[y][x];
   if(ret != 0) return ret;
   //재귀
   ret = max(dp(y + 1, x, triangle), 
              dp(y + 1, x + 1, triangle)) + triangle[y][x];
   return ret;
}

최대경로와 상관없는 sum을 생략하여 코드를 수정하였다.

결과는 모두 통과다. 처음 모든 경로를 탐색하는 재귀보다는 시간이 매우 단축되었다는걸 알 수 있다.
그러나 이러한 알고리즘을 짜는 이론적 배경은 무엇일까?

최적 부분 구조

sum 이라는 정보가 맨 아래줄까지 내려가는 문제를 해결하는데 아무 상관이 없다는 사실이다.

어떤 경로를 갔든 남은 부분문제는 최적으로 풀어도 상관 없다는 뜻이다. 이것은 효율적인 동적 알고리즘에 중요한 조건이다. 삼각형 문제에서는 어느쪽으로 내려갈지의 선택에 따라 두 개의 부분 문제로 문제를 분할 가능하다. 이 때 지금까지의 선택과 상관없이 최적으로 풀기만하면 전체 문제의 최적해도 알 수 있다. 따라서 최적 부분 구조가 성립한다.