➤ DP 알고리즘이란?
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하는 방식을 사용하여, 여러 번 반복되는 동일한 문제를 계산할 때의 비효율성을 방지하는 해결 방법이다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.
위의 그림을 보면 같은 함수들이 여러번 호출되는 것을 볼 수 있다. 컴퓨터 상에서 연산을 할 때 같은 함수를 여러 번 호출하고 사용하다 보면 메모리 낭비가 되고, 연산 속도도 늘어나기 때문에 비효율적이다. 이러한 문제를 해결하기 위해서 사용하는 것이 동적 계획법이다.
DP 알고리즘으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 이어진다.
위를 수식으로 표현하면, n 번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 파이썬에서는 리스트 자료형을, C/C++와 자바에서는 배열을 이용하여 처리한다. (필자는 파이썬으로)
구현 방법 - ① Top-Down (하향식, Memoization 방식)
dp = [0] * (n+1)
def fibo(n):
if n == 1 or n == 2:
return 1
if dp[n] == 0:
dp[n] = fibo(n - 1) + fibo(n - 2)
return dp[n]
print(fibo(n))✔ Memoization(메모이제이션)은 이전에 확인했던 문제를 메모하겠다는 뜻이다. 하향식은 하위 문제에 대한 정답을 계산했는지 확인해 가면서 풀어나간다.
구현 방법 - ② Bottom-Up (상향식, Tabulation 방식)
dp = [0]*(n + 1)
dp[1] = 1
def fibo(n):
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibo(n))✔ Tabulation(타뷸레이션)은 도표라는 뜻인데 도표식으로 저장하는 걸 말한다. 상향식은 더 작은 하위 문제부터 살핀 후 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다.
➤ DP 사용 조건
• Overlapping Subproblems(겹치는 부분 문제)
- 동일한 작은 문제들이 반복하여 나타나는 경우에 사용
• Optional Substructure(최적 부분 구조)
- 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 사용
➤ DP 문제 풀어보기
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
풀이
https://dev-cloud.tistory.com/171
↓ DP에 대한 더 많은 설명 ↓
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로
hongjw1938.tistory.com
'알고리즘' 카테고리의 다른 글
| [Java] String 클래스 주요 메서드 (0) | 2024.09.29 |
|---|---|
| [자료구조] sort, sorted, 정렬, 이중 리스트 정렬 (Python) (0) | 2023.10.31 |
| [알고리즘] 에라토스테네스의 체 (1) | 2023.09.23 |
| [알고리즘] BFS/DFS 알고리즘 (그래프 탐색) (0) | 2023.05.15 |
| Greedy (그리디 알고리즘) (0) | 2023.05.07 |