Code Kata | day13 min_path_sum
Q. 양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.
☑️ code
리스트를 아래로 쌓는다. m은 가로길이, n은 세로길이가 된다. 아래 보이는 그림과 같이 우측 혹은 아래쪽에 있는 값을 더한 누적값 그대로 이동한다고 생각하면 쉽다. (4 = 1 + 3, 5 = 4 + 1 이때 4는 동일한 4이다. )
def min_path_sum(grid):
m = len(grid[0])
n = len(grid)
for i in range(1, m):
grid[0][i] += grid[0][i-1]
for i in range(1, n):
grid[i][0] += grid[i-1][0]
for i in range(1, n):
for j in range(1, m):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]
Review
이런 알고리즘 문제는 새로운 함수나 메소드를 사용하는 것보다 답을 찾는 방법을 생각해내는게 어렵다. 최대한 많이 접하고 새로운 방법을 생각하는 방식 자체를 훈련하는 게 중요하다.
Author And Source
이 문제에 관하여(Code Kata | day13 min_path_sum), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e2joo418/Code-Kata-day12-minpathsum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)