[DP] Dynamic Programming

<이것이 취업을 위한 코딩 테스트다>를 공부하며 정리한 내용입니다.

알고리즘 소개

중복되는 문제를 줄이자 !! → 다이나믹 프로그래밍

ex) 피보나치 수열 구하기 : 동일한 함수가 반복적으로 호출 → 이거… 어디다 저장해놓으면 안 돼?

다음 조건을 만족해야 사용 가능.

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

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

방법 2가지

• 탑다운(top-down) : 재귀함수 이용, 큰 문제를 해결하기 위해 작은 문제 호출 (하향식) ➕ 메모이제이션 (memoization) : 한번 계산한 정보를 리스트에 저장하기. 그리고 재활용. 꼭 DP에만 쓰이는 건 아님.
  
• 보텀업(bottom-up) : 반복문 이용, 작은 문제부터 차근차근 답을 도출 (상향식)

기존 피보나치 수열 코드

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

print(fibo(4)) #3

탑다운 (메모이제이션) 방식을 이용한 피보나치

• 리스트에 계산한 결과 저장.
• 계산한 결과 있다면 그걸 재활용, 아니면 새로 계산해서 저장해두기.
• 재귀함수 사용. → 필요한 것들을 위에서부터 쫘라락 뽑아두고, 아래서부터 다시 계산해 올라옴.

d=[0]*5 #결과 저장을 위한 리스트 -> n값에 따라서 크기를 잘 조정해줘야겠죠?

def fibo(n):

    if n==1 or n==2:
        return 1

    if d[n]!=0: #이미 계산된 결과가 존재한다면
        return d[n]

    d[n]=fibo(n-1)+fibo(n-2) #새로 계산하고 저장해두기
    return d[n]

print(fibo(4)) #3

바텀업 방식을 이용한 피보나치

• 반복문 활용. → 아예 아래서부터 계산해 나감.

d=[0]*5 #결과 저장을 위한 리스트

d[1]=1 #1, 2번째 피보나치 수 설정
d[2]=1
n=4 #n번째 피보나치 수를 구할 겁니다. 

for i in range(3,n+1): #3번째 수부터 계산 필요하니 n번째까지 천천히 구해본다.
    d[i]=d[i-1]+d[i-2]

print(d[n]) #n번째 피보나치 수 출력.