다이나믹 프로그래밍

다이나믹 프로그래밍

 

다이나믹 프로그래밍이란 무엇일까?

나는 다이나믹 관련 문제를 계속해서 풀고 있지만, 처음부터 풀지못하고 계속 답지를 보고 풀고있다.

이게 과연 실력이 늘긴 하는걸까? 바닥공사 문제를 풀다가 도저히 이해가 가지 않아 블로그에 처음 개념부터 다시 정리해 보려고 한다.

 

 

다이나믹 프로그래밍은 보통 연산속도를 빠르게하거나 메모리공간을 최대한으로 활용하기 위해 사용하는 알고리즘이다.

 

흔히 이를 '점화식'이라고도 부른다. 

 

대표적인 예시는 '피보나치 수열'이다.

 

피보나치 수열은 n번째 숫자를 알고 싶어할 때 n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이되고 이러한 규칙을 따르는 수열이다.

 

다음은 피보나치 수열의 재귀적인 소스코드이다.

 

def fibo(n) :
  if n ==1 or n==2:
    return 1
  else :
    return fibo(n-1)+fibo(n-2)
    
print(fibo(4))

 

하지만 재귀함수는 시간복잡도로 2^n을 가지기 때문에 n이 조금만 커져도 수행속도가 급격하게 증가한다.

 

이러한 문제는 다이나믹 프로그래밍을 사용함으로써 해결할 수 있다.

 

우선 다이나믹 프로그래밍을 쓰기위해서 두가지 상황이 필요하다.

 

1.큰 것을 작은 것으로 나눌 수 있어야 한다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 피보나치 문제를 '메모리 제이션'을 통해서 풀어보자.

'메모리 제이션' : 한번 구한 값을 메모리에 저장해두고 다시 그값을 호출한다면 메모한 결과를 그대로 가져오는 기법

이를 '캐싱'이라고도 칭한다.

 

다음 코드는 캐싱을 이용한 재귀함수이다.

d = [0]*100

def fibo(x):
  if x==1 or x==2:
    return 1   #종료조건 : 1혹은 2일 때 1반환
  if d[x]!=0 :
    return d[x] #계산한적이 있다면 바로 반환
  d[x] = fibo(x-1) + fibo(x-2) #계산한적이 없다면 fibo재귀이용
  return d[x]
  
print(fibo(4))
 
  

 

이러한 큰 문제를 작은 문제로 나누는 기법은 '퀵 정렬'도 있다.

하지만 퀵 정렬은 다이나믹 프로그래밍과 다르게 한번 처리한 값을 다시 처리하지 않는다. 반면에 다이나믹 프로그래밍은 한번 처리했던 것을 캐싱해서 가져오기 때문에 이러한 점이 차이점이라고 볼 수 있다.

 

위의 방법은 '탑다운 방식'이다. 큰 문제 해결을 위해 작은 문제부터 차근차근 답을 도출하기 때문이다.

반면에 작은 문제부터 큰 문제로 향하는 방식을 '보텀업 방식'이라고 한다.

 

보텀업 방식을 이용한 소스 코드

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])

 

다이나믹 프로그래밍에서 전형적인방식은 보톰업 방식이다. 

 

다이나믹 프로그래밍 노하우

- 특정한 문제를 완전 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍으로 해결 가능한지 확인

-웬만하면 보텀업방식으로