[알고리즘] 다이나믹 프로그래밍 (DP) 이해하기

다이나믹 프로그래밍(동적계획법)이란?

- 큰 문제를 풀기 위해서 작은 문제를 풀어 나가는 방식이며,

작은 문제에서 반복이 없다는 것이 특징입니다. -> 분할 정복 기법과 다른 결정적인 차이

또한 하나의 문제를 단 한 번만 푸는 알고리즘 

 

다이나믹 프로그래밍 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

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

 

이러한 조건때문에 시간 복잡도를 훨씬 줄일 수 있습니다!!!

 

어떻게 구현할까요??

메모이제이션(Memoization) 기법 활용

말 그대로 메모하는 기법입니다.

작은 문제 계산된 결과값을 배열을 사용해서 저장하고,

나중에 큰 문제에서 동일한 계산을 요구할 때 배열의 저장된 값을 불러오는 것입니다.

-> dp 리스트 초기화해서 안에 담고 나중에 불러오기

유형

Top-down

하향식이며 재귀문으로 표현

# 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d=[0]*100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건 (1 or 2)
    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]

print(fibo(99))

Bottom-up

상향식이며 반복문으로 표현

주로 보텀업 방식이 전형적인 DP유형입니다.

# 앞서 계산된 결과를 저장하귀 위한 dp테이블 초기화
d=[0]*100

# 첫 번째,두 번째 피보나치 수는 1
d[1]=1
d[2]=1
n=99

# 피보나치 함수 반복문으로 구현(보텀업)
for i in range(3,n+1):
    d[i]=d[i-1]+d[i2]


print(d[n])

 

끝으로 나동빈 선생님께서

dp유형은 어렵게 나오면 엄청난 난이도를 요하기 때문에

기본 유형만 알아도 된다는

위로??를 해주셨습니다.

 

영상 보고 참고했습니당

www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

동빈나