다이나믹 프로그래밍(Dynamic Programming, DP) 란?
최적화 문제를 해결하는 방법 중 하나로, 중복되는 계산을 피하고 효율적으로 문제를 해결할 수 있는 방법.
주로 최적 부분 구조(Optimal Substructure) 와 중복되는 부분 문제(Overlapping Subproblems) 를 가지는 문제에 적용
주요 개념 및 특징
- 최적 부분 구조 (Opimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 최적 해결 방법을 이용해 큰 문제의 최적 해결 방법을 찾을 수 있는 성질
- 중복되는 부분 문제 (Overlapping Subproblems)
- 동일한 부분 문제가 반복적으로 발생하는 성질. DP는 이러한 중복을 피해서 각 부분 문제를 한 번만 해결하고 그 결과를 저장해두고 재활용하여 계산 시간을 줄임
- 상향식 접근법 (Bottom - up Approach)
- 작은 문제부터 시작하여 큰 문제를 해결하는 방법. 주로 반복문과 배열을 사용하여 구현
- 하향식 접근법 (Top - down Approach)
- 큰 문제를 작은 문제로 쪼개면서 해결하는 방법. 주로 재귀 함수와 메모이제이션(Memoization) 을 사용하여 구현됨
- 메모이제이션 (Memoization)
- 계산된 결과를 배열이나 해시맵 등에 저장해 두고 나중에 동일한 계산을 반복하지 않도록 하는 최적화 기법
- 타뷸레이션 (Tabulation) 은 다이나믹 프로그래밍의 한 방법론으로, 상향식 접근법 (Bottom - up Approach) 에 기반한 해결 방법. 작은 문제부터 시작하여 점진적으로 큰 문제를 해결하는 방식으로 동작. 타뷸레이션은 메모이제이션과 달리 배열을 사용하여 중간 계산 결과를 저장하고 재활용
Hello World