프로그래머스 레벨3 문제 처음으로 혼자 풀어서 기쁘다.
다이나믹 프로그래밍 실전 문제를 통해 이해해보기
정수 삼각형
출처: https://school.programmers.co.kr/learn/courses/30/lessons/43105
문제 설명
- 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
- 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
삼각형의 높이가 높지 않으면 DFS/BFS 방식으로도 풀 수 있다.
하지만 문제 조건에서 최악의 상황에서 삼각형의 높이가 500이고, 이때, 의 경우의 수를 갖기 때문에 불가능하다.
이렇게 경우의 수가 많이 발생하는 이유는 중복되는 연산을 계속 수행하기 때문이다. 이런 경우에 이전 연산을 저장해서 중복 연산을 없애는 DP를 사용한다.
DP 사용 조건
- 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결
- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬
이 문제에서는 전체 연산(큰 문제)을 각각의 연산(작은 문제)로 나눌 수 있고, 각각의 연산이 전체 연산을 해결할 수 있으며, 중복되는 연산이 존재하므로 DP를 사용한다.
크게 위에서 아래로 내려오는 Top-Down 방식과 아래에서 위로 올라오는 Bottom-Up 방식이 있다.
나는 Top-Down 방식을 사용해서 해결했음
DP 풀이
def solution(triangle):
d = [ [0] * (i+1) for i in range(len(triangle))]
d[0][0] = triangle[0][0]
for i in range(len(triangle)):
for j in range(len(triangle[i])):
if i == 0:
continue
# 왼쪽 위 체크 (현재 왼쪽 끝이 아니면 가능)
if j-1 >= 0:
d[i][j] = max(d[i][j], d[i-1][j-1] + triangle[i][j])
# 바로 위에 체크 (바로 위 길이보다 작으면 가능)
if j < len(triangle[i-1]):
d[i][j] = max(d[i][j], d[i-1][j] + triangle[i][j])
# 오른쪽 위 체크 (바로 위 길이보다 2이상 작으면 가능)
if j + 1 < len(triangle[i-1]):
d[i][j] = max(d[i][j], d[i-1][j] + triangle[i][j])
return max(d[-1])- d라는 리스트에 첫 번째 층의 값은 미리 저장하고, 나머지는 0으로 초기화한다.
- 두 번째 층부터는 각 조건에 맞으면 현재 위치에 d에 저장된 값과 윗층까지 누적된 연산 값 + 현재 위치에 triangle에 저장된 값 중 더 큰 값을 현재 위치의 d값을 업데이트 한다.
- 연산이 끝나면 마지막 층의 값 중 최댓값을 반환한다.
이렇게 연산을 누적하면, 중복되는 연산을 줄여서 시간 복잡도를 낮출 수 있다.
재귀를 사용한 DP는 내가 생각하기에 너무 어렵다.. 더 많이 풀어보기
- DP를 어떤 상황에 사용할 것인가?
- DP를 어떻게 사용할 것인가?
Statistics & Data Science