[Algorithm] 동적계획법(Dynamic Programming)

Dynamic Programming

동적 계획법은 문제를 해결할 때 하나의 문제를 여러개의 작은 문제로 나누어서 작은 문제의 결과를 기억해두었다가 이를 사용하여 큰 문제를 해결하는 것이다. 재귀처럼 반복적으로 작은 문제들에 접근할 경우 이를 구하기 위해서 오랜 시간이 걸리기 때문에 비효율적이다. 따라서 이러한 반복적인 접근을 피하기 위해 메모리제이션, 기억해두는 방법을 사용하게 되는 것이다. 대표적인 예로 피보나치 수열이 있다.

int fibo(n):
    if n <= 2:
      return 1
    else:
      return fibo(n-1) + fibo(n-2)

 

 DP를 사용할 수 있는 조건은 두가지가 있다.

• 작은 문제들이 반복적으로 나타나는 경우
• 부분 문제의 결과를 통해 전체문제의 결과를 해결할 수 있는 경우 

 

DP 구현 방식

피보나치 수열 예제

 

Top-Down

재귀를 사용하여 큰문제에서 작은 문제로 접근하여 큰문제를 해결한다.

data = [0]*101;

int fibo(n):
  if n <= 2: 
    return 1
  if data[n]==0:
    data[n] = fibo(n-1) + fibo(n-2)
  return data[n]
}

 

Bottom-Up

반복문을 사용하여 작은 문제에서 큰 문제로 접근하여 큰문제를 해결한다. 

int fibo(n):
  data[0] = 0
  data[1] = 1
  for i in range(2, n+1):
    data[i] = data[i - 1] + data[i - 2]
  return data[n]