⚡ 알고리즘 - 동적 계획법(Dynamic Programming)
⚡ 알고리즘 - 동적 계획법(Dynamic Programming)
🔹 동적 계획법이란?
▫️ 개념
- 큰 문제를 여러 개의 작은 문제로 나눠서 푸는 방식
- 동일한 하위 문제가 반복되는 경우, 그 결과를 저장해 중복 계산을 피함
- 하향식(메모이제이션) 또는 상향식(반복문) 방식으로 구현
▫️ 특징
- 중복되는 하위 문제(
Overlapping Subproblems
) - 최적 부분 구조(
Optimal Substructure
) - 재귀 호출 또는 반복문 기반으로 해결 가능
🔹 DP
구현 방식
하향식 (Top-Down
)
- 재귀 호출을 사용하며, 이미 계산한 결과는 배열 등에 저장
- 메모이제이션이라고도 부름
1
2
3
4
5
6
7
8
int[] memo = new int[100];
int fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
상향식 (Bottom-Up
)
- 작은 문제부터 차례대로 값을 구해 나가며 테이블을 채워감
1
2
3
4
5
6
7
8
9
int fib(int n) {
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
🔹 대표 문제 유형
▫️ 피보나치 수열
- 기본적인
DP
예제 n
번째 수는n-1
,n-2
번째 수의 합
▫️ 0-1
배낭 문제
- 무게 제한이 있는 가방에 최대 가치를 넣는 문제
- 물건을 담거나 담지 않는 두 선택 사이에서 최적 해 선택
▫️ 최장 공통 부분 수열(LCS
)
- 두 문자열에서 순서를 유지한 채 가장 긴 공통 부분 문자열의 길이 구하기
▫️ 최소 편집 거리
- 한 문자열을 다른 문자열로 바꾸는 최소 연산 횟수 구하기
- 삽입, 삭제, 교체 연산이 사용됨
🔹 DP
와 그리디의 차이
- 그리디는 각 단계에서 최선만 선택
DP
는 모든 경우를 고려하고 저장하면서 최적 해를 도출- 같은 문제라도 조건에 따라 적절한 방법을 선택해야함
🔹 마무리
- 동적 계획법은 중복되는 하위 문제와 최적 부분 구조가 있는 경우 매우 강력한 알고리즘
- 효율적인 시간 복잡도를 갖고, 많은 면접 문제에 출제되므로 다양한 유형을 연습하는 것이 중요하다
This post is licensed under CC BY 4.0 by the author.