2023. 12. 28. 20:27ㆍ알고리즘
♣ DP의 의미
기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것.
일반적인 재귀 방식과 DP는 매우 유사함. 하지만 일반적인 재귀를 사용할 때 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있음.
♣ DP의 사용 조건
1. Overlapping Subproblems(겹치는 부분 문제가 존재)
2. Optimal Substructure(최적 부분 구조)
- Overlapping Subproblems
동일한 작은 문제들이 반복하여 나타나는 경우에 DP를 사용할 수 있음. 즉, 부분 문제의 결과를 저장하여 중복으로 계산할 필요가 없어져야 함.
- Optimal Substructure
부분 문제의 최적 결과 값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우에 DP 사용.
♣ DP 사용 순서
1. DP로 풀 수 있는 문제인지 확인하기
2. 문제의 변수 파악하기
3. 변수 간 관계식 만들기
4. 메모하기(변수의 값에 따른 결과 저장하기)
5. 기저 상태 파악하기(가장 작은 문제의 상태 파악하기)
6. 구현하기
♣ 재귀함수 vs DP
ex) 피보나치 수열 계산
1. 재귀함수로 피보나치 수열 계산
이를 재귀함수로 풀면 똑같은 피보나치 수를 계산하는 경우가 여러 번 반복되어 발생한다.
따라서 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 기하급수적으로 늘어난다.
2. DP로 피보나치 수열 계산
동적계획법에서는 반복 계산을 막기 위해 이전에 계산했던 값들을 배열에 저장함.
♣ 백준 알고리즘 14501번
♣ 참고 자료
https://hongjw1938.tistory.com/47
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로
hongjw1938.tistory.com
https://btfnswt.tistory.com/55
[python] 피보나치수열 (재귀, DP)
재귀적 방식 def fibonacci(i): if i==0: return 0 elif i==1: return 1 else: return fibonacci(i-1)+fibonacci(i-2) for i in range(6): print(fibonacci(i)) DP fibo = [0 for i in range(100)] fibo[0] = 0 fibo[1] = 1 for i in range(0,10): if i==0: print('0') e
btfnswt.tistory.com
'알고리즘' 카테고리의 다른 글
| 신장트리(백준 알고리즘 9372번) (0) | 2024.01.07 |
|---|---|
| DP(Dynamic Programming) 백준 알고리즘 1003번 (0) | 2023.12.31 |
| 그리디 알고리즘(백준 알고리즘 11399) (1) | 2023.12.20 |
| 백준 1541번 잃어버린 괄호 (1) | 2023.12.06 |
| 백준 알고리즘 11659번(구간합 구하기) (1) | 2023.12.04 |