문제
양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.
한 지점에서 우측이나 아래로만 이동할 수 있습니다.
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
설명: 1→3→1→1→1 의 합이 제일 작음
나의 풀이
def min_path_sum(grid):
# 여기에 코드를 작성해주세요.
m = len(grid[0])
n = len(grid)
result = {}
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
result[(i,j)] = grid[0][0]
elif i == 0 and j > 0:
result[(i,j)] = result[(i,j-1)] + grid[0][j]
elif j == 0 and i > 0:
result[(i,j)] = result[(i-1,j)] + grid[i][0]
else:
result[(i,j)] = min(result[(i-1,j)],result[i,j-1])+grid[i][j]
return result[(m-1,n-1)]- m = 첫번째 element의 길이, n = 그리드 전체의 길이
- if문
첫번째 : 좌표 [0,0] 값 설정
두번째 : 좌표 [0,j]은 우측으로 가는 값만 더할 수 있으므로 [0,j]의 값 설정
세번째 : 좌표 [i,0]은 하단으로 가는 값만 더할 수 있으므로 [i,0]의 값 설정
네번째 : 위 1,2,3번째 상황이 아닌 경우에는, 어떤 좌표든 우측 아니면 하단으로만 진행할 수 있으므로, 그 좌표까지의 최소값은 위 아니면 왼쪽의 값 중 최소값일 것이다.
따라서 위 아니면 왼쪽 좌표를 min 함수를 써서 비교하고 해당 값을 더한다. - 이중 for문을 전부 완료하면 m x n 인자의 마지막까지 계산할 수 있으므로 그 값을 return해준다.
풀이에 대해 접근조차 하지 못해서, 구글 검색을 통해 동적 계획법이라는 알고리즘을 알게 되었다.
동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법인데, 부분적으로 문제가 반복되는 유형과 최적 부분 구조를 가지고 있는 알고리즘을 해결하는데 사용된다. 부분적으로 문제를 해결해서 답을 구하면 그 답을 다음 문제에 적용할 수 있으므로, 하위 문제가 기하급수적으로 많을 때 유용하다.
위 문제도 각 좌표의 최단 거리값이 다음 좌표의 최단 거리값을 구하는 데 사용되므로 동적 계획법이 적용되었다고 볼 수 있다.
