[동적계획법(Dynamic Programming)] 프로그래머스 level 3 정수 삼각형 (Python 파이썬)

💡문제 링크

프로그래머스

 

 

💡문제 분석 요약

전형적인 DP 문제

정수 삼각형이고, 대각선 아래 왼쪽 혹은 오른쪽 숫자를 더해나가서 만들 수 있는 총합의 최댓값을 구하면 된다.

작은 문제를 가지고 큰 문제를 해결하는 문제

 

💡알고리즘 설계

처음에 문제를 읽었을 때, 위에서 아래로 더해나가는 것처럼 보이지만 사실상 DP를 이용해서 해결하려면 작은 문제를 가지고 큰 문제를 해결해야 하므로, 아래에서 위로 올라가야 한다.

1. 맨 아랫줄 그 위부터 탐색한다.

2. 대각선 아래 왼쪽 오른쪽 중 더 큰 값을 자기 자신에 더한다.

3. 맨 아랫줄 그 위가 탐색이 끝나면 그 위의 줄을 탐색한다.

4. 맨 윗줄까지 올 때까지 반복한다.

5. 맨 위의 숫자를 반환한다.

💡코드

def solution(triangle):
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(i+1):
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
    return triangle[0][0]

 

💡 오답 풀이

def solution(triangle):
    def dp(x, y):
        if x < len(triangle) - 1:
            return max(dp(x+1, y), dp(x+1, y+1)) + triangle[x][y]
        else:
            return triangle[x][y]
    return dp(0, 0)

처음에는 재귀함수를 이용해서 풀었다. 테스트케이스는 통과했지만 시간초과가 나왔다. 역시 재귀함수는 시간이 오래걸린다는 말이 맞나보다. 이전에 '이것이 코딩테스트다' 책으로 공부할 때 재귀함수가 반복문보다 간단하지만 데이터의 크기가 클 경우 시간이 오래걸린다는 내용을 배웠다.

def solution(triangle):
    def dp(x, y):
        if x < len(triangle) - 1:
            triangle[x][y] += max(dp(x+1, y), dp(x+1, y+1))
        print(x, y, triangle[x][y])
        return triangle[x][y]
    return dp(0, 0)​

또 다른 내가 쓴 오답. 방문했던 곳을 다시 방문하면서 숫자가 불필요하게 커지는 문제 발생.

이 문제를 해결하기 위해 아래서부터 위로 차근차근 올라가도록 for문을 사용하는 방식으로 바꿈.

for문을 사용할 때, 아래서부터 위로 올라가기 때문에 range를 거꾸로 가져가야 했는데 range(a, b, -1)에서 -1을 까먹어서 헤맸다.

💡 다른 풀이

solution = lambda t, l = []: max(l) if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])

 

해석:

1. solution = lambda t, l = []:
   • 이 람다는 두 개의 인자를 받습니다.
     • t: 삼각형 배열을 나타내는 리스트입니다. 각 행은 삼각형의 한 층을 나타냅니다.
     • l: 현재까지 계산된 각 층의 최대 경로 합을 저장하는 리스트입니다. 기본값은 빈 리스트([])입니다.
2. max(l) if not t
   • t가 빈 리스트가 될 때까지 재귀적으로 함수를 호출하는데, 삼각형 배열의 모든 층을 처리한 후(t가 비어 있을 때), l 리스트에 있는 값 중 최대값을 반환합니다.
   • 즉, 삼각형의 최상단까지 도달하면 최대 경로 합을 반환하는 부분입니다.
3. else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])
   • t가 비어있지 않을 경우에 실행되는 부분입니다.
   • t[1:]: 현재 층(t[0])을 제외한 나머지 삼각형 층을 의미합니다. 이것으로 삼각형의 나머지 층에 대해 재귀적으로 함수를 호출합니다.
   • [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])]: 삼각형 배열의 한 층(t[0])을 처리하는 부분입니다.
     • zip([0]+l, l+[0], t[0]): 현재 층의 각 요소에 대해, 이전 계산에서 나온 l의 값과 비교하기 위해 양 옆에 0을 추가한 리스트들과 현재 층의 요소들을 묶어줍니다.
     • [max(x,y)+z for x,y,z in ...]: 각 자리에서 양 옆의 경로 중 더 큰 값을 고른 후, 현재 층의 요소(z)를 더해 업데이트합니다.

💡 느낀점 or 기억할정보

for문을 사용할 때, 아래서부터 위로 올라가기 때문에 range를 거꾸로 가져가야 하므로 range(a, b, -1)에서 -1을 넣어준다.