요즘 유행하는 드라마 DP아닙니다..!
동적 계획법이란 큰 문제를 작은문제로 나누어 푸는 문제를 말한다. 동적 계획법이란 말 때문에 동적으로 프로그램이 진행 되는지는 몰라도 된다. 왜냐하면.. 동적프로그래밍이란 말을 창조한 사람이 그냥 멋있어서 이름을 부여했기 때문이다.
어딘가의 목적지로 향하는데 있어 통과 해야 할 톨게이트가 있다고 가정해보자.
이때 어떠한 경로를 거쳐서 가야 비용이 가장 적게 부과가 되는지 찾는 방법을 찾아보자.
위의 문제를 해결 하기 위해 DP를 사용해야 하며, 비슷한 예제를 아래에서 확인해보자.
위의 문제는
1 3 1
1 5 1
4 2 1
이렇게 되어있는 3*3에의 좌측 상단에서 시작하여 우하단까지 가는 최소비용을 구하는 문제이다.
이 문제를 풀기위해 나는 다음과 같은 코드를 작성 하였다.
def min_path_sum(grid):
m_len = len(grid)
n_len = len(grid[0])
for m in range(1, m_len):
grid[0][m] += grid[0][m-1]
#row의 값을 초기화 시켜주는 과정이다
for n in range(1, n_len):
grid[n][0] += grid[n-1][0]
#column의 값을 초기화 시켜주는 과정이다
#위의 과정을 거치고 나면(x는 신경쓰지 말 것)
#1 4 5
#2 x x
#6 x x
#이렇게 완성이 된다.
for m in range(1, m_len):
for n in range(1, n_len):
grid[n][m] += min(grid[n-1][m], grid[n][m-1])
#위의 작업은 x로 오기 전의 비용들 중 적은 값을 x와 더하여 저장 해주는 과정이다.
return grid[n_len-1][m_len-1]
#결과
#1 4 5
#2 7 12
#4 6 7
#이렇게 결과가 작성이 된다
드라마 DP인줄 알고 들어왔는데 아니네요 수고하세여