[프로그래머스 Lv.3] 정수 삼각형: 다이나믹 프로그래밍

 

문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

제한 사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

입출력 예

 

---

 

바로 내일 카테부에서 첫 모의코딩테스트를 한다. 그래서 여태껏 공부 안 하다가 부랴부랴 프로그래머스를 켰다. 

브론즈 정도는 지금도 잘할 자신이 있어서, 하루 전에 무엇을 공부하면 좋을까 고민하다가, 기출 확률이 높은 DP 알고리즘을 공부해 보기로 했다. 이 알고리즘에 해당하는 문제 중 가장 쉬운 문제가 프로그래머스 레벨 3에 해당한다 ... 레벨 2도 겨우 푸는 나인데 ... ㅜㅜ 

 

그래도 강의 듣고 푸니까 원리는 단번에 이해해서 구현에는 크게 문제가 없었다.

따라서 요번 글에는 DP 알고리즘에 대한 설명과 원리가 대다수, 그리고 정수 삼각형 문제에 대한 풀이를 진행해보겠다.

 

강의는 어김없이 나동빈 씨를 봤는데, 6년 전 강의라 그런지 자료가 부족하고 예시 코드도 C++ 밖에 없어서, 그다음으로 조회수 높은 강의를 보았다. [링크]에서 보았는데 되게 이해하기 쉽게 잘 설명해 주어서 10분 만에 공부 가능 ㅎㅎ

---

 

프로그래머스의 정수 삼각형 문제를 예시로 DP를 설명한다.

 

아래와 같이, DP 테이블을 추가적으로 만들어서, 각 위치에 올 수 있는 최댓값을 저장한다. 

 

7의 자리는 아래의 3과 8에 각각 더해진다. 그래서 아래와 같이 각각 10과 15가 채워진 걸 볼 수 있다.

오른쪽 테이블을 보면, (2,1)의 자리의 경우 원본 삼각형의 7+3+1과 7+8+1이 올 수 있고, 이때 최댓값을 저장하면 되기 때문에 7+8+1인 16이 들어가게 된다.

이런 식으로 쭉쭉 내려가다 보면 마지막 줄에서의 최댓값이 이 문제에서 요구하는 정답이 된다. 

 

아주 간단한 알고리즘이고, 이걸 쓰는 목적은 단순히 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 실행 속도를 개선하는 게 포인트다.

이 알고리즘을 써야 하는 경우라고 한다면, 일반적으로 DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많을 때 라고 한다.

 

자 그럼, 풀이를 해보자 !

def solution(triangle):
    answer = [row[:] for row in triangle] # DP 테이블 초기화
    for i in range(len(triangle)-1):
        for j in range(i+1):
            answer[i+1][j] = max(answer[i+1][j], triangle[i+1][j]+answer[i][j])
            answer[i+1][j+1] = max(answer[i+1][j+1], triangle[i+1][j+1]+answer[i][j])
    return max(answer[-1])

 

위의 코드를 간단히 설명하자면, answer라는 변수에 DP 테이블을 초기화한다. 처음에 .copy()로 사용했는데, 이게 옅은 복사 .. 그 개념이 적용되어서 triangle이 바뀌면 answer도 바뀌게 되었다. 그래서 지피티한테 물어보니, import copy로 deepcopy()를 하면 깊은 복사가 된다고 하는데, 솔직히 이거 사용하는 거 많이 못 봐서 패스했다.

 

그래서 적용한 방법이 위와 같이 [row[:] for row in triangle] 이다. triangle의 각 행을 그대로 가져오는 것이다. 

 

그리고 triangle의 행의 개수보다 1만큼 적게 (마지막 줄은 안 해도 되니까) for문을 적용하고, 이중 for문으로 각 행의 수만큼 열의 수가 생기니까 행의 수만큼 반복하였다.

 

answer[i][j] 입장에서 왼쪽 아래 수와 오른쪽 아래 수에 각각 합을 넣는다. 이때, 기존 합이 더 크다면 적용이 안되도록, max()를 활용하였다. 

 

마지막 return으로 asnwer의 마지막 줄에서 최댓값을 반환한다. 

 

---

 

잠이 쏟아져서 그냥 손가락이 움직이는 대로 쓰긴 했지만 .. 나를 포함한 모두가 이해할 거라 믿는다. 그럼 DP 안녕 ..~