[Algorithm] Dynamic Programming에 관해
소마 13기 코테를 준비하며, dp문제를 많이 풀 기회를 접하였다.
그래봤자 난이도가 실버급에 있는 문제들이긴 하지만, 그래도 일단 내가 풀면서 느낀 점들을 정리하려 한다.
먼저 DP, Dynamic Programming은 문제풀이 알고리즘의 한 종류로, DFS나 그리디, 백트래킹과는 또다른 성격의 문제풀이법이다.
풀면서 수학적 귀납법과 비슷하다는 느낌을 받았다.
먼저, 속도에 관해 말해 보자면 DFS는 시간이 엄청 걸리고, 백트래킹은 그걸 조금 줄여주지만 DP는 확실히 줄여 주는 것을 느꼈다.
여기서 한 가지 느낀 점은
"DP는 시간과 공간을 trade해서 효율성을 올린 알고리즘"
이다.
DP문제를 풀다 보면 점화식 형태의 풀이법이 많다. 대부분 배열이나 리스트를 이용하여 점화식을 세워 문제를 푸는데, 이때 다른 알고리즘과의 차이점은
DFS는 풀이한 결과를 따로 저장하진 않는다.
백트래킹은 풀이 결과가 맞지 않으면 중간에 다른 길로 돌아간다.
그런데 DP는 풀이 결과를 저장하며, 이를 다음 연산에 활용한다.
여기서 일단 차이가 있는 것 같다.
예시로 counting sort를 생각해 보면 좋을 것 같다.
counting sort는 O(n)으로 효율적이고 안정적인 알고리즘인데 대신 공간을 잡아먹는다.
이런 느낌 아닐까?
예로 백준 1463 1로 만들기나 9095 1, 2, 3 더하기, 11726 2*n타일링 문제들이 대표적인 DP 문제들이다.
이런 문제를 풀 때 정말 공통적으로 나오는 것이
1. 비용, 경우의 수 등을 저장하기 위한 추가 배열
2. 문제 상황에서 도출되는 점화식
이 두 가지다.
# 1463 DP 풀이
x = int(input())
lst = [0] * (x+1)
for i in range(2, x+1):
lst[i] = lst[i-1] + 1
if i % 2 == 0:
lst[i] = min(lst[i//2]+1, lst[i])
if i % 3 == 0:
lst[i] = min(lst[i//3]+1, lst[i])
print(lst[x])< 백준 1463 >
여기서도 보면 lst라는 추가적인 배열을 만들어 저장한다.
그리고 min등의 점화식을 통해 리스트의 이전 식의 값에서 얼마만큼 추가하는 방식으로 진행한다.
그리고 전체적인 문제 풀이법을 생각할 때, 처음이나 마지막 부분이 아닌, 중간 부분에서 어떻게 연결할지를 생각하는 것이 핵심인 것 같다.
# 11726 2*n 타일링
n = int(input())
lst = [0] * n
lst[0] = 1
if n > 1:
lst[1] = 2
for i in range(2, n):
lst[i] = lst[i-1] + lst[i-2]
print(lst[-1] % 10007)< 백준 11726 >
이 문제에서는 결국 현재 칸에서 세로로 세우냐, 가로로 눕히냐를 선택하는 문제이다. 세로로 세우면 이전 한칸까지만 블럭이 위치할 수 있지만, 가로로 눕히면 이전 두칸까지만 위치할 수 있다. 그래서 현재 있는 칸에서의 경우의 수는 한칸을 차지할 때 + 두칸을 차지할 때 경우의 수를 합친 것과 같아진다.
이를 표현한게 위 점화식이다.
그리고 나서 초기 조건만 조금 세팅해 주면 점화식은 완료가 된다.
어느 글에서 그랬는데, DP문제를 푸는 방법(DP문제풀이에 들어가는 요소)은 다음과 같다.
1) DP문제 구분
2) 상태 저장하는 방법 선택
3) 상태들끼리 관계 수식화
4) 상태에 저장된 값을 꺼내 쓰는 부분 추가
# 1149 - RGB거리
import sys
n = int(input())
cost = []
for i in range(n):
cost.append(list(map(int, sys.stdin.readline().split())))
#print(cost)
red = [0] * n
green = [0] * n
blue = [0] * n
red[0] = cost[0][0]
green[0] = cost[0][1]
blue[0] = cost[0][2]
for i in range(1, n):
red[i] = cost[i][0] + min(green[i-1], blue[i-1])
green[i] = cost[i][1] + min(red[i-1], blue[i-1])
blue[i] = cost[i][2] + min(green[i-1], red[i-1])
print(min(min(red[n-1], green[n-1]), blue[n-1]))< 백준 1149 RGB거리 >
이 문제는 조금 특이했던게 저장하는 리스트를 3개를 사용해야 했다.
현재 상태가 3개의 다른 경우로 저장되므로 이렇게 표현한 것 같다.
만약 현재 칸이 red로 가정하면, 이전 칸은 green 또는 blue가 와야 하므로 최소 비용을 구하려면 이 둘 중 작은 것을 더한다.
그리고 최종 출력때는 세 리스트 중 가장 작은 값을 출력한다.
세 값을 비교할 때는 2개를 먼저 비교하고, 도출된 1개를 나머지 1개와 비교하면 된다.
처음 DP문제를 접했을 때는, 수학적인 공식이 따로 있는 줄 알았다.
그런데 풀이법을 접하고 처음 보는 풀이법에 충격에 빠졌었다.
하지만 여러 문제를 풀다 보니 어느 정도는 정형화되어있다는 것을 새삼 느끼기도 했다.
처음 보는 풀이라고 너무 쫄 필요는 없다. 언젠가는 내 것이 되어 있을 테니.