[Algorithm] 동적계획법 (Dynamic Programming) 개념 및 구현

 

 

동적계획법

Dynamic Programming

 

이번 포스팅에선 동적계획법 알고리즘을 살펴보겠다.

동적계획법은 "한 번 계산한 문제는 다시 계산하지 않는다"라는 신념을 가진 녀석이다.

메모리를 조금 써서 속도를 비약적으로 상승시키는 것이 핵심이다.

Let's Go

 

 

 

 

 

동적계획법이 아니라면? 보통은 단순 재귀.

---

동적계획법의 성능을 확인할 수 있는 문제가 있다.

바로 피보나치 수열이다. 

피보나치 수열을 동적계획법이 아닌 단순 재귀를 사용하여 구현하면 다음과 같다. 

 

 

def fibo(x):
  if x == 1 or x ==2:
    return 1
  else:
    return fibo(x-1) + fibo(x-2)

 

 

위의 코드로 피보나치 수열을 구한다고 생각해보자.

---

fibo(5)를 구하기 위해선, fibo(4)와 fibo(3)을 구해야 한다. 그리고 다시 fibo(4) -> fibo(2), fibo(3) / fibo(3) -> fibo(1), fibo(2). 그리고 또다시 fibo(2) -> fibo(0), fibo(1)/ fibo(3) -> fibo(2), fibo(1)/ fibo(2) -> fibo(0), fibo(1).

---

단순 재귀를 사용한다면 전에 구했던 fibo(2), fibo(1), fibo(3)을 다시 계산해야 한다. 계산 속도가 기하급수적으로 느려지는 것이다. 다음 코드를 보자. 

 

 

for i in [3, 25, 40]:
  start = time.time()
  fibo_i = fibo(i)
  print(f'{i}의 fibo : {fibo_i} / 걸린 시간: {round(time.time()-start, 2)}초')
  
  
3의 fibo : 2 / 걸린 시간: 0.0초
25의 fibo : 75025 / 걸린 시간: 0.03초
40의 fibo : 102334155 / 걸린 시간: 30.2초

 

 

계산 속도가 기하급수적으로 느려진다. 이런 문제를 해결하고자 나온 것이 바로 동적계획법이다. 

 

 

 

 

동적계획법 원리, 구현

---

동적계획법은 한 번 계산한 결과를 메모리에 저장해두었다가, 나중에 필요할 때 다시 사용하는 것이 포인트다. 이런 기법을 메모제이션(캐싱) 기법이라고 한다. 

코드로 구현하면 다음과 같다. 

 

 

d = [0] * 50

def fibo(x):
  if x == 1 or x == 2:
    return 1
  if d[x] != 0:
    return d[x]
  d[x] = fibo(x-1) + fibo(x-2)
  return d[x]

 

 

d라는 리스트를 생성하고, fibo(n)를 통해 값이 구해질 때마다 저장해둔다. 그러면 다음번에 fibo(n)을 사용해야 할 때, 만약 리스트에 저장되어있다면 끌어다 쓰면 된다. 속도가 얼마나 빨라졌는지 확인해보자. 

 

 

for i in [3, 25, 40]:
  start = time.time()
  fibo_i = fibo(i)
  print(f'{i}의 fibo : {fibo_i} / 걸린 시간: {round(time.time()-start, 2)}초')
  

3의 fibo : 2 / 걸린 시간: 0.0초
25의 fibo : 75025 / 걸린 시간: 0.0초
40의 fibo : 102334155 / 걸린 시간: 0.0초

 

 

눈에 띄게 빨라졌음을 확인할 수 있다. 위와 같은 방식을 Top-Down 방식이라고 한다. fibo(5)를 구하기 위해 fibo(3), fibo(4)로 내려가고, 또다시 fibo(3)을 구하기 위해 fibo(1), fibo(2)로 내려가기 때문이다. 동적계획법을 사용하지 않고 단순 반복문을 사용하는 방법도 있다. 

 

 

d = [0] * 50
d[1] = 1
d[2] = 1
n = 40
start = time.time()

for i in range(3, n+1):
  d[i] = d[i-1] + d[i-2]

print(f'{n}의 fibo : {d[n]} / 걸린 시간: {round(time.time()-start, 2)}초')



40의 fibo : 102334155 / 걸린 시간: 0.0초

 

 

위와 같은 방식을, 밑에서 위로 천천히 올라간다고 하여 Bottom-up 방식이라고 한다. Top-Down 방식은 제귀 횟수 제한 오류가 날 수 있기 때문에 Bottom-up 방식으로 해결할 것을 권장한다. 

그럼 문제를 풀러 가보자!

 

 

 

https://www.acmicpc.net/step/16

동적 계획법 1 단계