동적계획법 (Dynamic Programming)

동적계획법 (Dynamic Programming)

동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 분할 정복과 다른 점은 문제들이 서로 영향을 미치고 있다는 점이다. 동적 계획법의 경우 한 번 해결한 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 가져다 쓰는 것이다.

동적 계획법은 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

동적 계획법을 구현하는 방식에는 2가지가 있는데 탑 다운 방식과 바텀 업 방식이다.

탑다운 방식은 재귀 함수를 이용한다. 큰 문제를 해결하기 위해 작은 문제를 호출한다. 피보나치 수열을 예로 코드를 생각해보자.

d = [0] * 100
def fibo(x):
  if x == 1 or x == 2:
    return 1
  if d[x] != 0:
    return d[x]
  d[x] = fibo(n - 1) + fibo(n - 2)
  return d[x]
​
print(fibo(6))

바텀업 방식은 피보나치 수열을 아래에서 위로 올라가는 방식으로 반복문을 이용하여 문제를 해결한다.

d = [0] * 100
​
d[1] = 1
d[2] = 1
n = 99
​
for i in range(3, n + 1):
  d[i] = d[i - 1] + d[i - 2]
  
print(d[n])

특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자