1. Dynamic Programming
- 복잡한 문제를 작은 문제로 나누어 푸는 알고리즘 입니다.
- 작은 문제의 해를 저장해 나중에 같은 부분 문제를 계산하지 않도록 합니다.
조건
중복 부분 문제 구조 (Overlapping subproblems)
- 전체 문제를 작은 부분 문제들로 나누었을 때, 같은 부분 문제들이 반복됨
- Memoization: 작은 문제들의 해를 저장 및 재사용함으로써 중복계산을 방지할 수 있습니다.
최적 부분 구조 (Optimal substructure)
- 전체 문제의 해가 부분 문제의 해를 이용해 구해질 수 있는 성질
- 부분 문제와 전체 문제간에 의존성이 존재합니다.
- 이러한 의존성을 점화식으로 도출하여 전체 해를 작은 문제의 해의 조합으로 표현할 수 있습니다.
- 작은 문제부터 해결해 나가면서, 점진적으로 문제의 해를 도출해 나갑니다.
풀이 방식
top-down (recursion)
- 지연 계산
- 문제를 해결하는 과정에서 하위 문제가 필요할 때만, 특정 하위 문제를 계산하고 결과를 저장하여 재사용합니다.
- 장점
- 필요한 하위 문제만 계산하므로 불필요한 계산을 줄일 수 있습니다.
- 재귀적으로 작성하므로, 직관적이고 이해하기 쉬운 코드를 작성할 수 있습니다.
- 단점
- 재귀 호출 시, 오버헤드가 발생합니다.
- 깊은 재귀로 스택 오버플로우 에러가 발생할 수 있습니다.
bottom-up (iteration)
- dp 테이블 사용
- 가장 작은 하위 문제부터 시작하여 차례대로 모든 하위 문제를 해결해 나갑니다.
- 이 때 계산한 하위 문제의 해를 dp 테이블에 저장하여 전체 문제를 구성할 때까지 재사용합니다.
- 장점
- 누락없이 모든 하위 문제를 해결할 수 있습니다.
- 단점
- 필요하지 않은 하위문제의 계산까지 실행하므로, 필요한 해만 구할 경우 비효율적일 수 있습니다.
2. 적용 과정
분할
- 주어진 문제를 작은 부분 문제로 나눕니다.
점화식 도출
- 각 부분 문제와 전체 해 간의 관계를 나타내는 수학적 식을 정의합니다.
메모이제이션 테이블 정의
dp 배열 정의
- 부분 문제의 해를 저장할 자료구조를 정의합니다. (크기, 차수)
인덱스 의미 정하기
- dp 배열의 각 인덱스가 어떤 의미를 가질 지 정의합니다. (점화식과 밀접하게 연관됩니다)
초기값 정하기
- 점화식의 계산을 시작하기 위한 초기값을 설정합니다. (반복적인 연산의 기점이 됩니다)
부분 문제 해결 및 저장
결과 재사용
결과 조합 및 전체 해 도출
출처
'Algorithm' 카테고리의 다른 글
| [알고리즘] Divide and Conquer (0) | 2024.02.18 |
|---|---|
| [고급 알고리즘] Graph(Shortest Path): Dijkstra Algorithm (1) | 2024.02.10 |
| [기초 알고리즘] String (0) | 2023.11.08 |
| [기초 알고리즘] 수학: 소수 (0) | 2023.11.08 |
| [고급 알고리즘] Greedy (0) | 2023.11.08 |