1. 문제
설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
| triangle | result |
|---|---|
| [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] | 30 |
2. 풀이
대표적인 동적 계획법 문제중 하나가 아닐까 싶습니다.
알고리즘 사이트에 한 문제씩은 이 문제가 개시되어 있고
종만북에도 이 문제가 실려있습니다.
일단 이 문제를 풀기 위해서는 주먹구구식으로 접근해야 합니다.
꼭대기부터 바닥까지 이어지는 경로를 모두 탐색한다.
모든 경로 중에서 합이 최댓값이 되는 경우를 찾으면 되겠죠?
코드는 이렇게 짜여집니다.
// 완전 탐색 코드
// 깊이, 인덱스, 현재 경로까지 모은 합
static int f(int depth, int index, int sum) {
if (depth == N) return sum; // 기저 사례
// 왼쪽으로 간 경우 vs 오른쪽으로 간 경우
return Math.max(f(depth + 1, index, sum + tri[depth][index]), f(depth + 1, index + 1, sum + tri[depth][index]));
}이러면 정답은 나오긴 합니다만,
각 노드에 대해 왼쪽으로 간다, 오른쪽으로 간다의 선택을 반복하니
시간 복잡도는 2^N, 지수 시간이 걸리기 때문에 효율성 통과를 할 수 없습니다.
이 때 등장하는 개념이 메모이제이션입니다.
잘 생각해보면 위에서 짠 완전 탐색 코드는 동일한 함수를 반복해서 호출하고 있습니다.
예를 들어서
f(2, 0)은 f(3, 0)과 f(3, 1)을 재귀적으로 호출합니다.
마찬가지로 f(2, 1)은 f(3, 1)과 f(3, 2)를 재귀적으로 호출합니다.
이 때, f(3, 1)은 중복해서 호출되고 있음을 알 수 있습니다.
(sum 인자는 무시하셔도 됩니다. 지금까지 모은 sum이 무슨 값이든 간에 f함수 동작에는 아무런 영향을 미치지 않습니다.)
f(3, 1)에 대한 값을 어딘가에 저장해놓고 다시 호출할 땐 그 값을 재활용하는 기법을
메모이제이션 기법이라고 합니다.
// 메모이제이션을 적용한 코드
// 깊이, 인덱스
// memo[depth][index] = 현재 depth의 index위치에서 얻을 수 있는 최댓값
static int f(int depth, int index) {
if (depth == N) return 0; // 기저 사례
// 메모이제이션 됐다면 값을 재활용
if (memo[depth][index] != -1) return memo[depth][index];
// 재귀호출한 다음 그 값을 memo 배열에 메모이제이션합니다.
return memo[depth][index] = tri[depth][index] + Math.max(f(depth + 1, index), f(depth + 1, index + 1));
}
완전 탐색에서 메모이제이션 기법을 적용하는 방법은 간단합니다.
인자로 받던 sum변수를 없애고 함수 f가 현재 위치에서 반환할 수 있는 최댓값을 리턴하도록 합니다.
재귀적인 흐름을 이해한다면 위 뜻이 무슨 말인지 충분히 이해하시리라 믿습니다.
전체 시간복잡도는 이차원 배열인 memo배열을 채우는 시간에 비례하므로 N^2이 됩니다.
지수 시간에서 다항 시간으로 바뀌었으므로 엄청난 최적화가 이뤄졌음을 알 수 있죠.
3. 전체 코드
class Solution {
static int N;
static int[][] memo, tri;
public int solution(int[][] triangle) {
N = triangle.length;
tri = triangle;
memo = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
memo[i][j] = -1;
return f(0, 0);
}
static int f(int depth, int index) {
if (depth == N) return 0;
if (memo[depth][index] != -1) return memo[depth][index];
return memo[depth][index] = tri[depth][index] + Math.max(f(depth + 1, index), f(depth + 1, index + 1));
}
}