[프로그래머스] 정수 삼각형 / 파이썬 / python / 다이나믹 프로그래밍

 

오늘 파이썬을 정말 오랜만에 쓰는 거라 어색했다. 동빈나님 알고리즘 강의 중 다이나믹 프로그래밍을 공부했고, 이와 관련된 간단한 문제를 풀어보았다.

 

다이나믹 프로그래밍(Dynamic Programming)이란?

완전 탐색으로 시간이 오래 걸리는 프로그램의 수행 시간을, 메모리를 적절히 사용하여 효율화하는 방법이다. 이미 계산한 결과(작은 문제)를 별도 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이다.

다음을 만족하는 경우 다이나믹 프로그래밍으로 해결한다.

• 최적 부분 구조 -> 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 중복되는 부분 문제 -> 동일한 작은 문제를 반복적으로 해결해야 한다.

다이나믹 프로그래밍의 두 가지 유형

• 탑다운(메모이제이션) 방식 -> 하향식이라고 하고, 재귀를 사용한다.
• 보텀업 방식 -> 상향식이라고 하고, 반복문을 사용한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 

메모이제이션💾

다이나믹 프로그래밍을 구현하는 방법 중 하나다. 한번 계산한 결과를 메모리 공간에 저장하여, 같은 문제를 다시 호출하면 저장했던 결과를 그대로 가져와 사용한다. 값을 기록해 놓는다는 점에서 '캐싱'이라고도 부른다.

 

💡solutions 

💬 다이나믹 프로그래밍(동적 계획법) 문제이다. 주어진 삼각형 이차원 배열을 한층씩 내려가며(꼭대기 제외하고 그 다음 층부터) 최대가 될 수 있는 값으로 갱신해주면 된다.

💬 아래 코드에서 값을 비교하는 조건문을 보면, 각 층의 맨 처음값과 끝값은 -> 바로 윗층의 처음값 또는 끝값과만 더해지기 때문에 max 함수로 값을 비교할 필요 없이 더해주기만 한다.

💬 맨 처음값 또는 마지막값을 제외한 나머지들은 대각선 왼쪽에서 내려오는 경우와 대각선 오른쪽에서 내려오는 경우 둘 중에 큰 값을 더해주면서 갱신해주면 된다.

 

💻code 

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

    return max(triangle[-1])

 

📌description 

코딩테스트 연습 - 정수 삼각형

---

 

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

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

제한사항

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