Dynamic Programming?
DP는 중복 계산을 줄여 성능을 높이는 알고리즘 설계 기법이다.
알고리즘 설계 기법 : 문제를 해결하는 전략
알고리즘 기법 : 그 전략을 구현한 실제 방법
복잡한 문제를 작은 하위 문제로 나누고, 그 결과를 저장해 두었다가 재활용하는 기법.
- 문제를 작은 부분 문제들로 나누고
- 그 결과를 기억(Memoization) 해서
- 중복 계산을 피하며 효율적으로 정답을 구하는 기법
✔ 최적화 문제나 중복 계산이 많은 문제에서 유용하게 쓰인다
언제 DP를 써야할까?
- 중복 부분 문제 즉, 같은 부분 문제를 여러 번 계산하며
- 최적 부분 구조 즉, 큰 문제의 최적해가 작은 문제의 최적해로 구성될때
이 두 조건이 성립되면 DP를 사용한다.
문제 해결
top-down (재귀 + memoization)
큰 문제를 작은 부분 문제로 나누어 해결하는 방식이다. 보통 재귀 함수를 사용하여 큰 문제를 작은 부분으로 쪼개어 권한을 위임하고, 중복을 피하기 위해 memoization 기법을 활용하여 계산된 값을 저장해놓는다.
but! 재귀 호출의 overhead가 발생할 수 있어 시간초과가 발생할 수도 있다.
❓ 언제 사용?
- 모든 상태를 계산할 필요가 없다 -> 필요한 상태만 호출해서 메모리에 효율적
- 문제가 재귀적으로 자연스럽게 풀린다 -> DFS, 백트래킹 + DP 같이 사용하기 좋음
- 상태 전이가 복잡하거나 조건 분기가 많다 -> 재귀 구조가 코드로 표현하기 쉬움
- 문제 크기(N)가 작다 -> 재귀 깊이 제한에 안 걸림
- 빠르게 문제 구조를 실험하고 싶다 -> 코드 구현이 간결하고 빠름
🎐 예시
LCS (최장 공통 부분 수열)
DP + DFS 문제 (ex. 이동 경로 카운팅)
상태 공간이 너무 크지만 실제로 도달하는 경우가 적을 때
bottom-up (반복문)
말 그대로 작은 부분 문제부터 해결하여 전체 문제까지 차례대로 올라오며 해결하는 기법이다. 반복문을 사용하여 작은 부분 문제부터 차례로 해결하며 해결한 값을 배열 등에 저장하여 사용한다.
❓ 언제 사용?
- 모든 상태를 반드시 계산해야 한다 -> 반복문으로 빠르게 순차적으로 계산 가능
- 시간/메모리 효율이 매우 중요하다 -> 스택을 안 쓰고, 고정된 배열로만 처리
- 재귀 깊이가 너무 깊다 (N ≥ 10⁵) -> Java에서는 재귀로 시간 초과 or StackOverflow 가능
- 문제 크기가 크고 단순히 누적하는 형태다 -> 반복문이 깔끔하고 빠름
🎐 예시
1로 만들기 (백준 1463)
피보나치 수 (큰 N)
배낭 문제
계단 오르기, 동전 교환
예시코드
실제로 백준 1463번 : 1로 만들기 문제에서도 먼저 top-down으로 풀었다가 시간초과가 나서 bottom-up으로 다시 풀었다^^..
https://velog.io/@seha01130/백준JAVA-1463번-1로-만들기
