[이론] DP(Dynamic Programming, 동적 계획법)

이번에는 DP(Dynamic Programming, 동적 계획법)에 대해 공부해봤습니다.

원래 BFS와 DFS를 했으니 다른 그래프 이론들을 공부하려다가 코테에 잘 나오는거 먼저 하자!! 해서 순서가 좀 바뀌었습니다 ㅎㅎ

 

DP(Dynamic Programming, 동적 계획법)

파이썬 알고리즘 인터뷰

: 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법 중 하나입니다.

이 방법은 주로 최적화 문제를 해결하는 데 사용되며, 큰 문제를 작은 부분 문제로 나누어 해결한 후, 그 결과를 저장해두고 필요할 때 다시 사용(메모이제이션)함으로써 계산의 중복을 피하는 것이 핵심 전략입니다. 동적 계획법은 문제를 분할하여 각각의 작은 문제들을 한 번씩만 풀어 큰 문제의 해답을 구하는 방식으로, 불필요한 계산을 줄이고 효율성을 높입니다.

 

메모이제이션(Memoization)

동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용합니다. 이를 통해 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용합니다. 이는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킵니다.

 

동적 계획법의 핵심 요소

1. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해결 방법이 그것을 구성하는 작은 문제들의 최적 해결 방법으로부터 구성될 수 있는 성질을 말합니다. 즉, 전체 문제의 최적 해가 부분 문제의 최적 해로부터 도출될 수 있음을 의미합니다.
2. 중복되는 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 여러 번 발생하여, 이 문제들의 해결 결과를 저장해두고 재사용할 수 있음을 의미합니다. 이를 통해 중복 계산을 방지하고 알고리즘의 효율성을 높일 수 있습니다.

 

동적 계획법의 접근 방식

상향식 접근법 (Bottom-Up, Tabulation 방식)	- 가장 작은 하위 문제들부터 시작하여 점차적으로 큰 문제로 나아가는 방식입니다. 일반적으로 반복문을 사용하여 구현하며, 작은 문제의 해를 테이블에 저장하면서 진행합니다. - 일반적으로 더 직관적이고 이해하기 쉽습니다. 또한, 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장합니다. - 반복문 사용
하향식 접근법 (Top-Down, Memoization 방식)	- 큰 문제를 시작으로 하여 필요한 작은 문제로 나누어가는 방식입니다. 일반적으로 재귀 호출을 사용하여 구현하며, 메모이제이션을 통해 이미 해결한 문제의 결과를 저장하여 중복 계산을 방지합니다. - Memoization은 재귀를 사용하므로 구현이 더 간단할 수 있습니다. 또한, 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있습니다. 하지만 재귀 호출의 오버헤드가 발생할 수 있으며, 모든 작은 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있습니다. - 재귀 사용

 

동적 계획법의 예

피보나치 수열	- Top - Down 방식 접근 - 피보나치 수열의 n번째 값을 찾는 문제에서, 기본적인 재귀 방식은 중복 계산이 많아 비효율적입니다. 동적 계획법을 사용하면, 이미 계산된 피보나치 수를 저장하여 재사용함으로써 효율적으로 문제를 해결할 수 있습니다.
배낭 문제 (Knapsack Problem)	- Bottom - Up 방식 접근 - 무게 제한이 있는 배낭에 최대 가치를 가지도록 물건을 담는 방법을 찾는 문제입니다. 작은 배낭 문제로 나누어 해결하고, 각 단계에서의 최적 해결 방법을 메모하여 큰 문제의 해결에 활용할 수 있습니다.

 

- 계산의 중복을 피함으로써 알고리즘의 실행 시간을 크게 줄일 수 있으며, 다양한 최적화 문제에서 중요한 역할.

- 그러나 모든 문제에 대해 DP가 최선의 접근 방법인 것은 아님.

- 문제의 특성과 요구사항을 정확히 파악한 후 적절한 알고리즘을 선택.

- 주어진 문제가 최적 부분 구조와 중복되는 부분 문제의 성질을 가지고 있을 때 효과적으로 적용.

 

동적 계획법의 장점과 한계

장점	효율성: 중복되는 계산을 줄임으로써 알고리즘의 실행 시간을 크게 단축 명확한 구조: 문제를 분할하여 접근하는 과정에서 알고리즘의 구조가 명확해지며, 이를 통해 복잡한 문제를 체계적으로 해결 범용성: 다양한 최적화 문제에 적용 가능합니다. 예를 들어, 경로 찾기, 자원 할당, 스케줄링 문제 등에서 널리 사용
한계	메모리 사용량: 중간 계산 결과를 저장하기 위해 추가적인 메모리가 필요하며, 이는 때로는 상당한 양이 됨. 초기 설계 복잡성: 문제를 적절한 방식으로 분할하고, 각 부분 문제의 해결 방법을 설계하는 과정이 초기에 복잡 적용 제한성: 모든 문제가 동적 계획법을 통해 효과적으로 해결될 수 있는 것은 아니며, 최적 부분 구조와 중복되는 부분 문제의 특성 가짐.

 

 

문제별 분석

알고리즘	풀이 가능한 문제들의 특징	풀이 가능한 문제 및 알고리즘
다이나믹 프로그래밍	• 최적 부분 구조(Optimal Substructure) • 중복된 하위 문제들(Overlapping Subproblems)	• 0-1 배낭 문제 • 피보나치 수열 • 다익스트라 알고리즘
그리디 알고리즘	• 최적 부분 구조(Optimal Substructure) • 탐욕 선택 속성(Greedy Choice Property)	• 분할 가능 배낭 문제 • 다익스트라 알고리즘
분할 정복	• 최적 부분 구조(Optimal Substructure)	• 병합 정렬 • 퀵 정렬

 

 

 

 

 

- 참고 링크 : https://wikidocs.net/233722

- 참고 도서 : 파이썬 알고리즘 인터뷰