DP 정복 - 4.1 세 방법을 차례대로 적용하며 문제 풀기

다이내믹 프로그래밍도 결국 문제를 푸는 기술.

이 기술을 잘 활용하려면 많은 문제를 풀어 봐야 함.

 

다이내믹 프로그래밍을 사용해 문제를 푸는 기본적인 순서

1. 재귀 호출을 사용해 풀이법 작성

2. 문제의 난이도와 문제를 해결하는데 주어진 시간에 따라 다이내믹 프로그램이나 메모 전략을 사용해 풀이법을 개선

 

이번 절에서는 재귀, 메모 전략, 다이내믹 프로그래밍의 세 가지 접근 방법을 이용해서 문제를 풀어본다.

예제는 '행렬에서 최소 이동 비용 구하기'다.

0,0에서 n, m에 도달하는데 드는 최소 비용을 구하면 된다.

단, 아래쪽 혹은 오른쪽으로 한 칸씩만 이동 가능하다.

 

- 재귀로 풀어보자(0,0에서 2,3으로 갈 때)

1. 큰 문제와 작은 문제로 분할.

 = 큰 문제 : 셀(2,3)에 도달하는 최소 이동 비용 구하기

 = 작은 문제 1 : 셀(2,2)에 도달하는 최소 이동 비용 구하기

 = 작은 문제 2 : 셀(1,3)에 도달하는 최소 이동 비용 구하기

2. 수식으로 정의

 = 셀(2,3)까지의 최소 이동 비용 : MIN(x, y) + cost [2][3]

3. 종료 조건 정의

 = m과 n 모두 0인 경우 : 출발지가 목적지인 경우. cost [0][0]

 = m은 0이고 n은 0이 아닌 경우 : 목적지가 최상단 행에 있지만 셀(0, 0)은 아닌 경우. 오른쪽으로만 이동해야 도달 가능. 바로 왼쪽 셀의 최소 이동 비용에 현재 셀의 비용의 더해서 반환

 = m은 0이 아니고 n은 0인 경우 : 위에 상태의 반대. 목적지가 최하단 왼쪽 열에 있으나 셀(0, 0)은 아닌 경우. 아래쪽으로만 이동해야 도달 가능. 바로 위쪽 셀의 최소 이동 비용에 현재 셀의 비용을 더해서 반환.

 

상기의 조건을 이용해서 재귀 함수로 구현했다면 이제 메모 전략을 적용한다.

(재귀 함수로 구현 시, 이미 호출했던 호출이 자주 호출됨)

 

- 메모 전략

 = 각 셀(i, j)의 minPathCost를 처음 계산할 때 이를 일종의 캐시(2차원 배열)에 저장해둔 후 셀(i, j)의 minPathCost 값이 다시 필요하게 되면 계산을 반복하지 않고 캐시에서 가져오는 방법. 각 셀의 최소 이동 비용을 저장해야 하므로 2차원 배열을 캐시에 사용.

 = 전역 변수를 이용하면 행렬이 여러 개 있거나 다른 함수들에서 minPathCost를 호출하는 경우가 있다면 전역 변수를 초기화해야 하는 불편함이 있음을 유의. 그러나 보통 PS를 위해서는 전역 변수가 용이함.

 

- 다이내믹 프로그래밍 적용(상향식)

 = 핵심은 0, 0 기준으로 가로로만 진행하는 값(누적 값)을 구하고, 또 세로로만 진행하는 값(누적 값)을 구해서 저장해놓고 계산하는 방법을 따르면 된다.

 

막상 조각조각 내면서 따져보니 생각보다 그렇게 막연하지는 않은 듯하다.

다음에 문제를 풀 때는 상기의 3개의 순서를 따라가면서 풀면 괜찮을 것 같다.