[코테 스터디] 4주차 : 동적계획법

✅ 개요

동적계획법(Dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

✅핵심이론

1. 큰 문제를 작은 문제로 나눌 수 있어야 함
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야함
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용 
   이를 메모이제이션(memoization)기법이라고 함
4. 동적계획법은 톱-다운 방식 과 바텀-업 방식으로 구현가능

📌대표 문제 : 피보나치수열

피보나치수열 공식 : D[N] = D[N-1] + D[N-2]

1. 동적계획법으로 풀 수 있는지 확인

6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있음

2. 점화식 세우기

점화식을 세울 때 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요

피보나치 수열의 점화식은 

D[i] = D[i-1] + D[i-2]

3. 메모이제이션 원리 이해하기

메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하기 않고 DP 테이블의 값을 이용하는 것

이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있음

4. 톱-다운 구현 방식 이해하기 

주로 재귀함수 형태로 코드를 구현

장점 : 코드의 가독성이 좋고, 이해하기 편함

import sys
input = sys.stdin.readline

N = int(input())

D = [-1]*(N+1)
D[0] = 0
D[1] = 1

def fibo(n):
    print(f'fibo{n} 호출')
    if D[n] != -1: # 기존에 계산한 적이 있는 부분의 문제는 재계산 하지 않음
        return D[n]
    
    # 메모이제이션 : 구현 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴
    D[n] = fibo(n-1) + fibo(n-2)
    print(f'fibo({n-1}) + fibo({n-2}) =  {D[n]}')
    return D[n]

fibo(N)
print(D[N])

'''
입력 : 6

fibo6 호출
fibo5 호출
fibo4 호출
fibo3 호출
fibo2 호출
fibo1 호출
fibo0 호출
fibo(1) + fibo(0) =  1
fibo1 호출
fibo(2) + fibo(1) =  2
fibo2 호출
fibo(3) + fibo(2) =  3
fibo3 호출
fibo(4) + fibo(3) =  5
fibo4 호출
fibo(5) + fibo(4) =  8

답 : 8

'''

5. 바텀-업 구현 방식 이해하기

주로 반복문 형태로 구현

import sys
input = sys.stdin.readline

N = int(input())

D = [-1]*(N+1)
D[0] = 0
D[1] = 1

for i in range(2,N+1):
    D[i] = D[i-1] + D[i-2] # 반복문을 이용하여 아래서부터 값을 채워나감
    print(f'D[{i-1}] + D[{i-2}] = {D[i]}')
print(D[N])

'''
입력 : 6

D[1] + D[0] = 1
D[2] + D[1] = 2
D[3] + D[2] = 3
D[4] + D[3] = 5
D[5] + D[4] = 8

답 : 8

'''

7. 톱-다운 vs 바텀-업

두 방식 중 좀 더 안전한 방식은 바텀-업 

톱-다운 방식은 재귀함수 형태로 구현돼 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있음

하지만 코테에서 이 부분까지 고려해야하는 난이도는 잘 나오지 않음

이 문제를 제외하고 두 방식의 차이점은 거의 없음