00. 작성 배경

Dynamic Programming(동적 계획법)에 대한
이해를 제고시킬 알고리즘 문제를 풀어보며
독자들에게 조금이나마 도움이 되길 기원한다.

01. 문제 기술

조건) m개 행과 n개 열의 셀(cell)들로 이루어진 m*n 격자가 있다. 여기서 가장 아래 행은 ‘행 0’이고 가장 위의 행은 ‘행 m-1’이며, 가장 왼쪽 열은 ‘열 0’이고 가장 오른쪽 열은 ‘열 n-1’이다. 셀 (i-1, j-1)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (k-1, g-1)에는 비용 C(k-1, g-1)가 주어진다.

Q1) 셀(0, 0)에서 ‘오른쪽 방향’ 혹은 ‘위쪽 방향’으로만 가면서 셀(m-1, n-1)까지 가는 경로의 최소 비용을 구하는 프로그램을 동적계획법을 이용해 구하라. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 입력은 첫 번째 줄에 m과 n이 주어지고, 다음 각 줄에 각 행(위로부터 아래로)의 셀의 비용이 주어진다. 출력은 경로의 최소 비용을 출력한다.
! 조건: 부분문제의 해의 값을 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고 이 배열의 크기는 O(min(m, n))이어야 한다.
Q2) 가장 아래 행의 셀로부터 오른쪽 위쪽 대각선 방향 혹은 위쪽 방향 혹은 왼쪽 위쪽 대각선 방향으로만 가면서 ‘가장 위의 행의 셀까지’ 가는 경로의 최소 비용을 구하는 프로그램을 동적계획법을 이용하여 작성하라. 경로의 비용은 지나가는 셀의 비용의 총합이다. 입력은 첫 번째 줄에 m과 n이 주어지고, 다음 각 줄에 각 행(위로부터 아래로)의 셀의 비용이 주어진다. 출력은 경로의 최소 비용을 출력한다.
! 조건: 부분문제의 해의 값을 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고, 이 배열의 크기는 O(n)이어야 한다.

입력 예시)
4 5
2 8 9 5 8
4 9 6 5 3
6 7 5 2 1
3 2 5 4 8

02. 알고리즘 및 자료구조 설명

Q1)

1차원 배열을 테이블로 해야 하며, 그 크기는 O(min(m, n))이다. 아래 그림을 예시로 들어 설명하자면

맨 왼쪽이면서 맨 아래쪽을 셀 (0,0)이라 하고, 맨 오른쪽이면서 맨 위쪽을 셀 (m-1, n-1)이라고 하겠다.

위가 각 셀의 비용을 나타낸 것인데, 이 경우는 m < n인 경우다. 이 경우 테이블의 크기는 O(m)이다. 즉 4칸을 차지하는 배열을 이용하면 된다. 초기의 테이블은

로 해준다. 첫 번째 열을 기준으로 위로 올라가면서 비용이 합해진 것이다. 이제 오른쪽 두 번째 열로 향할 때의 최소 경로 비용을 테이블에 갱신해주자.

위를 구하는 방법은 다음과 같다. 5는 테이블의 0번째에 있던 3 값에 셀(0, 1)을 더해줘 5가 된 것이고, 12는 새로 구한 테이블의 0번째 값 5와 기존의 테이블의 1번째 값 9 중 작은 것을 선택하여 셀(1,1)의 비용과 더해줘 12(=5+7)가 된 것이다. ...

두 번째 열의 테이블을 구할 때를 간단하게 정리하면 아래와 같다.

table[0] = C[0][1] + table[0]

table[1] = C[1][1] + min(table[0], table[1])

table[2] = C[2][1] + min(table[1], table[2])

...

table[m-1] = C[m-1][1] + min(table[m-2], table[m-1])

실제 코드에서는 for 문으로 간단하게 해준다.

이렇게 오른쪽 열로 계속 향하면서 1차원 배열의 테이블 값을 계속 갱신해주고, 맨 오른쪽 열에 다다르며 최종 테이블을 구한 후 원하는 출력값을 출력하면 된다. 앞의 경우처럼 n > m일 때를 열이 하나인 세로 표를 연상하면서 풀었다면 m > n인 경우는 행이 하나인 가로 표를 연상하면서 풀면 되겠다. 풀이 방법엔 큰 차이가 없다. 가장 위의 행에 다다를 때까지 테이블을 갱신해주며 최종적인 출력 값을 출력하면 된다.

Q2)

이 문제의 경우는 맨 오른쪽이면서 맨 위쪽에 다다를 때의 최소 비용이 아니라 가장 위의 행의 셀에 다다를 때의 경로 최소 비용을 구하면 되는 것이다.

테이블은 O(n) 크기의 1차원 배열을 사용해야 한다. 가로줄을 연상하면서 위의 열로 향하면서 테이블을 갱신시키며 문제를 해결하면 되겠다.

Q1의 예시를 다시 한 번 이용하겠다.

초기 테이블은 위와 같이 둔다.
그 위의 행으로 향하여 테이블을 갱신시키면 위와 같다. table[0]은 밑에 3과 2중 2를 선택해 6과 더해주고,

table[1]은 밑에 3과 2와 5 중 2를 선택해 7과 더해준다.

...

table[4]는 밑에 4와 8 중 4를 선택해 1과 더해준다.

아래에서 두 번째 행에 대한 테이블을 정리하면 다음과 같다.

temp[0] = table[0]

table[0] = C[1][0] + min(table[0] + table[1])

temp[1] = table[1]

table[1] = C[1][1] + min(temp[0], table[1], table[2])

temp[2] = table[2]

table[2] = C[1][2] + min(temp[1], table[2], table[3])

temp[3] = table[3]

table[3] = C[1][3] + min(temp[2], table[3], table[4])

table[4] = C[1][4] + min(temp[3], table[4])

위를 살펴보면 temp 리스트를 이용해주는 것이 눈에 보인다. 왜 temp 리스트를 사용하는지는 다음과 같다.

테이블을 갱신시켜 주고 나면 왼쪽 아래쪽 대각선에 있는 걸 참조하지 못할 수 있기 때문에 왼쪽 아래쪽 대각선에 있는 걸 따로 temp 리스트에 저장해준다.

예를 들어 table[2]를 갱신해주려면 table[1], table[2], table[3]을 고려하면 안 되는 것이다. 왜냐하면 table[1]이 이미 갱신되어 왼쪽 아래 값을 제대로 참조할 수 없기 때문이다.

그래서 table[1]을 갱신해주기 전에 temp[1]에 table[1] 값을 저장해준다. 그리고 나서 table[2]를 갱신할 때 temp[1], table[2], table[3]에서 작은 것을 고른 후 그 자리의 비용과 더해준다. 이와 같은 원리다.

보통 table의 값을 갱신해줄 때는 왼쪽 아래 대각선 혹은 바로 아래 혹은 오른쪽 아래 대각선 중 최솟값을 선택해 바로 그 자리의 비용과 더해주면 되는데, 주의해야할 것은 맨 왼쪽 열의 테이블을 갱신할 때는 바로 아래와 오른쪽 아래 대각선 중에서만 최소를 고려하게 설계한다.

또한 맨 오른쪽 열의 테이블을 갱신할 때는 바로 아래와 왼쪽 아래 대각선 중에서만 최소를 고려하게 설계해야 한다.

03. 시간복잡도 분석

Q1)

1차원 배열의 테이블을 사용하고 배열의 크기는 O(min(m, n))이지만 테이블 갱신 자체는 계속 해주는 것이므로 시간복잡도는 O(m*n)만큼 걸릴 것이다. 보통 테이블 크기가 n일 때는 그 크기의 배열에 대해 m번 갱신해줄 테고, 테이블 크기가 m일 때는 그 크기의 배열에 대해 n번 갱신해줄 것이기 때문이다.

Q2)

1차원 배열의 테이블의 크기가 O(n)인데, 이것을 m개의 행을 거슬러 올라가면서 m번 갱신해주므로 시간복잡도는 O(m*n)이 될 것이다.

04. 구현 코드

해당 알고리즘 문제를 풀이한 코드는 필자의 repository를 참고하기 바란다.
독자의 편의를 위해 작성한 코드를 캡처하여 아래와 같이 올려두겠다.

05. 느낀 점

입력을 2차원 배열로 받을 때 맨 위의 행부터 한 줄씩 입력을 받아 리스트 맨 앞에 추가시키고, 그 다음 행을 입력 받아 다시 리스트의 맨 앞에 추가시키면서 배열을 구성한다.
그런데 이때 단순히 파이썬의 리스트를 이용하여 insert(0, val)을 통해 입력하기보다 deque을 import하여 deque의 함수인 appendleft를 이용한다면 더 빠르게 2차원 배열을 입력받을 수 있다.
Runtime이 중요한 상황이라면 어떤 자료구조를 사용할 것인지를 필히 신경써야 할 것이다.