동적계획법(다이나믹 프로그래밍) 배워보기-python

백준문제중 동적계획법으로 구하는 문제가 있길래 동적계획법을 공부했습니다(근데 동적계획법 이거 안쓰고 바로 풀었는데 멀까요?)

백준 # 11051

def 쾅(x):
    n=1
    for i in range(1,x+1):
        n=n*i
    return n

n,k=map(int,input().split()) 
if k < 0 or k > n:
    print(0)
else:
    print(       (쾅(n)//(쾅(k)*쾅(n-k)))%10007    )

수학귀신을 보신분이라면 왜 함수이름이 쾅인지 아실듯

 

아래내용은 동적계획법을 인터넷에서 찾아보고 정리한 내용입니다

출처

https://www.youtube.com/watch?v=5Lu34WIx2Us 

https://namu.wiki/w/동적%20계획법

 

동적계획법을 쓰지 않았을때의 문제점: 

피보나치 수의 값을 구할때를 예로 들었을때

fib(5)는 15번의 함수호출을 발생시킨다 수가 커질수록 시간복잡도와 공간복잡도가 크게 증가하는데 이걸

Exponential Explosion이라고한다 (피보나치를 이용한 재귀함수공부는 전에 해봤기때문에 이해가 잘 되었다)

 

동적계획법 

1. 메모리를 적절히 사용하여 시간효율성을 비약적으로 향상시킨다

2. 이미 계산된 결과(작은문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록한다

3. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다

 

일반적인 피보나치 수열

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

print(fibo(4))

 

피보나치 수열의 시간 복잡도 분석

O(2^N) 

빅오 표기법을 기준으로 f(30)은 약10억회가량의 연산필요

 

다이나믹 프로그래밍의 사용조건

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌수 있다

2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결

 

메모이제이션?

1. 다이나믹 프로그램을 구현하는 방법중 하나

2. 한번 계산한 결과를 메모리 공간에 메호나는 기법

    같은문제 호출시 메모결과 가져옴

    값을 기록해 놓는다는점에서 캐싱(Cashing)이라고도함

 

탑다운(메모이제이션) vs 보텀업?

1.  탑다운 하향식이라고도 하며 보텀업 방식은 상향식이라고도 함

2. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식    

    결과 저장용 리스트는 DP테이블이라고 부름

 

아래는 메모이제이션 방식으로 구현한 피보나치수 구하기(나한테는 익숙하다)

memo={}
def fibo(x):
    if x==1 or x==2:
        return 1
    # 메모한값 꺼내오기
    try:  
        return memo[x]
    # 없으면 등록하기
    except:
        memo[x]=fibo(x-1) + fibo(x-2)
        return memo[x]

강의에서는 리스트를 이용했는데 난 딕셔너리 형태가 더 간결한것같다

x값에따라 리스트를 변경해야하는게 좀 바보같다고 생각했다

d=[0]*10000
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]

아래는 보텀업 방법으로 구현된 피보나치 수 구하기이다

def fibo(x):
    d = [0] * (x+1)
    d[1]=1
    d[2]=1
    for i in range(3, x+1):
        d[i]=d[i-1]+d[i-2]
    return d[x]

코드를 읽어보니 왜 보텀업과 탑다운으로 이름 붙여졌는지 알것같았다

탑다운=큰문제를 풀기위해 작은 문제를 풀어나가는 느낌

보텀업=작은문제를 큰문제까지 풀어나가는 느낌(탑을 쌓아가는느낌)

 

메모이제이션 이용으로 시간복잡도 크게 감소가능

O(2^N) -> O(N)

 

내가 다이나믹 프로그래밍을 잘 이해했는지 확인하기위해 해당강의의 관련 문제를 하나 풀어보았다

문제를 풀수있다면 내가 제대로 이해했다는 의미니까

 

근데 생각보다 문제가 어려웠다 

개미전사에대한 내용은 다음포스팅에 있다