동적 프로그래밍(DP,dynamic programming) - 1분 개념 정리

다이나믹 프로그래밍,즉 동적계획법은 하나의 큰 문제를 여러 작은 문제로 나누어서 그 결과를 저장을 하고 작은 문제읙 ㅕㄹ과를 모아 큰 문제를 만드는 해결방식을 말한다.

 

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

 

1. 최적 부분 구조

큰 문제를 작은 문제로 쪼개수있는 문제인가? 작은 문제를 합쳐 큰 문제로 만들 수 있는 문제인가?

 

2. 중복되는 부분 문제

동일한 작은 문제를 반복해서 푸는 경우 즉 문제를 풀기위해서 작은 문제를 계속해서 풀게 되는 경우 

 

 

그럼 왜 동적 프로그래밍을 사용하는 것인데... 다양한 장점이 존재한다. 먼저 비효율적인 계산을 방지할 수 있다는 장점이 있다!

 

피보나치 수열을 살펴보자!

 

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 ....

 

첫번째와 두번째 항은 1로 시작을 하며 세번째 항 부터 전항과 전전항을 더한 값이 자신의 값이 된다. 즉 점화식으로 표현을 하게 되면 an = an-1+an-2 의 점화식을 세울 수 있다.

 

+점화식이란 인접한 항들의 관계식을 말한다. 즉 항들의 패턴을 수학적으로 표현을 한 것이다. 

 

다음은 동적 계획법을 사용하지 않은 파이썬 코드이다

 

n = int(input())

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

print(fibo(n))

 

 

만약에 우리가 100번째 피보나치 수열을 구하고자 한다고 가정을 해보자 그럼 몇번의계산을 수행을 해야 할까?

이 코드의 시간 복잡도를 확인을 하면 지수함수의 시간 복잡도를 가지니 100번째 항은 계산이 불가능 할 정도로 너무 큰 시간 복잡도가 나오게 된다.

 

 

 

이때 필요한 것이 동적계획법, 다이나믹 프로그래밍이다.  최적의 부분 구조를 가지고 있으며 중복되는 문제 즉 동일한 작은 문제를 반복적으로 계산해야 되는 경우에 사용할 수 있다.

 

피보나치 수열을 구하는 문제를 DP를 사용하면 최적의 시간복잡도를 가지게 되며 빠르게 문제를 해결할수있게 되는 것이다.

 

다이나믹프로그래밍은 크게 2가지로 나눌 수 있다.

 

1. 탑다운 방식 (하양식)

메모이제이션 기법을 사용하는 방식이다. 

+메모이제이션 기법이란 한번 계산이 된 결과를 DP테이블 즉 임이의 리스트에 담아 불필요한 계산을 하지 않도록 하는 방법을 말한다.

 

2. 바텀업 방식 (상향식)

작은 문제를 합쳐 큰문제를 만든 방식이다.

 

이해가 잘 되지 않으니 간단하게 코드를 살펴보자 먼저 메모이제이션 기법을 사용하는 경우이다.

 

 

 

탑다운 방식

dp=[0]*101 #인덱스를 1부터 사용을 할것이기 때문에 101사용함
#100번째 피보나치 수를 찾을거임

def fibo(x):
  if x==1 or x==2:
    return 1
  if dp[x]!=0: #dp테이블에 정보가 있는 경우
    return dp[x]
  dp[x]=fibo(x-1)+fibo(x-2) #없는경우 만들어주기
  return dp[x]

print(fibo(100))

 

 

 

바텀업 방식

dp=[0]*101 #인덱스를 1부터 사용을 할것이기 때문에 101사용함
#100번째 피보나치 수를 찾을거임

dp[1]=1
dp[2]=1
n=100

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

print(dp[100])