티스토리 뷰
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
다이나믹 프로그래밍 문제라고 써있다.
DP 문제는 언제 봐도 어렵다. 저번에 Knapsack 문제를 예시로 DP에 대해서 나름 설명을 한 포스팅도 썼었고, 더 예전에는 프로그래밍 과외를 하면서 학생한테 DP를 가르친 적도 있긴 했지만, 어디까지나 설명을 차근차근 보면서 겨우 이해하는 수준이지 문제 휙 던져주고 DP로 풀어보라고 하면 여전히 손도 대기 힘들어하는게 내 수준이다.
그래도 이번 문제는 그 예전 기억들을 조금씩 되살려보면서 어떻게든 풀이를 안 보고 풀어보려고 노력했다.
- 처음 짰던 코드
아이디어는 두 가지였다.
1) 삼각형이 딱 보면 트리처럼 생겼다. 트리 탐색할 때 루트 노드부터 시작해서 아래로 재귀호출을 하면서 내려갔던 걸 떠올렸다. 그러니까 재귀호출을 하면서 아래로 내려가는데 한번에 두 개 (왼쪽 아래, 오른쪽 아래) 씩 호출하고, 위쪽 노드에서는 왼쪽이랑 오른쪽 중에 큰 값을 취하도록 한다. 재귀호출이 무한히 반복되면 안되니 탈출조건을 설정해줘야 하는데, 트리의 맨 아래층에 도달하면 탈출하면 될 것 같다. 아래 그림처럼 이걸 반복하면 맨 윗칸에 거쳐간 숫자의 max 값이 저장될 것이다.
2) DP하면 가장 먼저 생각나는건 배열을 만들어서 저장한다는 개념! 메모이제이션이라 했던가? 그러니까 2차원 배열을 하나 더 만들어서, 각 칸에서의 max 값을 배열에 저장하도록 하자.
이 두 가지 아이디어를 적용해서 짜본 코드다.
def tri_dig(triangle, d, p, sum_arr):
if d == len(triangle)-1: # 탈출조건. 맨 아래층에 도달하면 재귀호출 더이상 X
return triangle[d][p];
# 왼쪽, 오른쪽 아래로 재귀호출을 하고 max 값을 취한다
sum_arr[d][p] = max(triangle[d][p] + tri_dig(triangle, d+1, p, sum_arr), triangle[d][p] + tri_dig(triangle, d+1, p+1, sum_arr));
return sum_arr[d][p];
def solution(triangle):
#triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]; # 예시 데이터
sum_arr = [[0 for x in range(y)] for y in range(1, len(triangle))]; # DP 배열??
sum_arr[0][0] = triangle[0][0];
tri_dig(triangle, 0, 0, sum_arr);
return sum_arr[0][0];
처음 몇 개는 맞는 것 같다가, 결국 시간초과가 떴다. 스스로도 이 코드를 짜면서 뭔가 나사빠진 것 같다는 생각을 했는데, 뭐가 잘못된 거였을까?
- 수정한 코드
재귀함수 tri_dig() 를 보면 탈출 조건이랑 재귀호출을 하는 부분으로 이루어져 있다. 뭔가 부족한 것 같지 않나... 잠깐 고민하다가 아! 배열에 저장만 해놓고 그걸 정작 써먹는걸 까먹었구나라는 걸 깨달았다.
단순히 배열에 값을 저장만 한다고 DP가 되는 것이 아니라, 저장한 값을 써먹어서 재귀호출의 횟수를 줄이자는 것이 DP의 핵심 아이디어다. 저장만 해놓고 꺼내쓰질 않았으니 재귀호출 횟수는 전혀 줄지 않은, DP를 제대로 적용한 코드가 아닌 것이다.
그래서 코드를 아래와 같이 수정했다. 재귀호출할 예정인 아래 칸에 해당하는 DP 배열의 원소를 체크해서, 값이 이미 있으면 재귀호출을 하지 않고 그 값을 쓰는 것이다. 재귀호출을 한번에 두 개씩 (왼쪽, 오른쪽) 하기 때문에 체크하는 if-else문을 두 개 넣었다.
def tri_dig(triangle, d, p, sum_arr):
if d == len(triangle)-1:
return triangle[d][p];
if sum_arr[d+1][p] != 0:
next1 = sum_arr[d+1][p];
else:
next1 = tri_dig(triangle, d+1, p, sum_arr);
if sum_arr[d+1][p+1] != 0:
next2 = sum_arr[d+1][p+1];
else:
next2 = tri_dig(triangle, d+1, p+1, sum_arr);
sum_arr[d][p] = max(triangle[d][p] + next1, triangle[d][p] + next2);
return sum_arr[d][p];
def solution(triangle):
#triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]];
sum_arr = [[0 for x in range(y)] for y in range(1, len(triangle)+1)];
sum_arr[0][0] = triangle[0][0];
tri_dig(triangle, 0, 0, sum_arr);
return sum_arr[0][0];
결과는 성공! 다른 코드나 힌트를 보지 않고 자력으로 DP 문제를 해결해본게 너무 오랜만이라 좀 뿌듯했다.
- 다른 사람의 코드
문제를 풀긴 했지만 더 좋은 해답이 있을 것 같아서 다른 사람의 코드도 찾아봤다.
사실 문제를 보고 처음 생각했던 건 위에서부터 숫자를 더해가면서 내려가는 거였다. 근데 재귀호출을 생각하다보니 재귀호출은 맨 끝에서부터 값을 리턴해나가는 거니까, 어쩌다보니 밑에서부터 값을 더해가는 코드가 되었다.
처음 생각했던 것처럼 위에서부터 더해가면서 내려가는 방법도 있었다. 재귀함수를 쓸 필요도 없고 훨씬 간단해서 역시, 라는 생각이 들었다...
def solution(triangle):
for i in range(1, len(triangle)):
for j in range(i+1):
if j==0: # 왼쪽 끝인 경우
triangle[i][j] += triangle[i-1][j]
elif i==j: # 오른쪽 끝인 경우
triangle[i][j] += triangle[i-1][j-1]
else: # 가운데 부분인 경우
triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
return max(triangle[-1])
다만 두 가지 생각해야 할 점이 있는데,
1) 삼각형의 양쪽 끝부분이랑 가운데 부분 2가지의 케이스를 따로 생각해야 한다. 양쪽 끝부분은 위에 숫자가 하나뿐이니 그냥 더하면 되고, 가운데 부분은 왼쪽 위랑 오른쪽 위 (재귀를 이용한 방법이랑 반대가 되겠다) 중에서 큰 값을 취해야 한다.
2) 맨 아랫줄의 값들 중에 max값을 가져간다.
이걸 돌려봤더니 내 코드보다 실행시간도 더 짧게 나왔다. 역시 재귀호출은 느리다.