✅ 개요
동적계획법(Dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법
✅핵심이론
- 큰 문제를 작은 문제로 나눌 수 있어야 함
- 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야함
- 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용
이를 메모이제이션(memoization)기법이라고 함 - 동적계획법은 톱-다운 방식 과 바텀-업 방식으로 구현가능
📌대표 문제 : 피보나치수열
피보나치수열 공식 : 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 바텀-업
두 방식 중 좀 더 안전한 방식은 바텀-업
톱-다운 방식은 재귀함수 형태로 구현돼 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있음
하지만 코테에서 이 부분까지 고려해야하는 난이도는 잘 나오지 않음
이 문제를 제외하고 두 방식의 차이점은 거의 없음
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 3주차 : 그리디 (0) | 2024.06.24 |
---|---|
[코테 스터디] 2주차 : 시간복잡도 (0) | 2024.06.17 |
[코테 스터디] 2주차 : DFS/BFS (1) | 2024.06.17 |
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |