파이썬 알고리즘 인터뷰 21-23장 참조
최적 부분 구조란?
Optimal substructure
최적 부분 구조 문제를 푸는 알고리즘은 아주 다양하다.
최적 부분 구조란,
문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성된 문제 구조를 의미한다.
최적 부분 구조는 특징이지, 방법론이 아님을 알아두자.
최적 부분 구조 특징을 가진 문제는 다음과 같은 3가지 종류의 알고리즘으로 해결한다.
⛏️분할 정복이란?
Divide and Conquer
다중 재귀를 이용해 큰 문제를 동일한 작은 문제들로 나눈다.
해결하기 쉬울 정도로 문제가 작아지면 분할하지 않고 문제를 해결하고,
해결된 결과들을 합쳐 큰 문제를 해결하는 방식이다.
분할 정복은 3단계 처리 과정을 거친다.
- 분할: 큰 문제는 동일한 작은 문제로 나눈다.
- 정복: 문제가 간단해질 정도로 작아지면 해결해버린다.
- 조합: 정복된 작은 문제들의 결과를 조합해 큰 문제를 해결한다.
분할 정복은 재귀를 이용해 푸는 방식인 것을 알아두자.
예시로는 퀵/ 병합 정렬이 있다.
😈그리디 알고리즘이란?
Greedy Algorithm
그리디 알고리즘은 탐욕 선택 속성을 가진 최적 부분 구조 문제를 푸는 방법론이다.
😋탐욕 선택 속성
탐욕 선택 속성은 이전의 단계가 현재 단계에 영향을 주지 않는 속성을 의미한다.
그리디 알고리즘은 현재 단계에서의 최적해만을 고려한다.
때문에, 탐욕 선택 속성이 전제돼야 한다. 그렇지 않으면 정확한 값을 얻지 못한다.
💥다이나믹 프로그래밍이란?
Dynamic Programming
그리디 알고리즘과 다르게, 다이나믹 프로그래밍은 부분 문제의 해를 저장(메모이제이션)하여, 큰 문제를 해결하는 방법론이다. 이 과정에서 부분 문제의 해가 현재 문제에 영향을 줄 수 있다.
❗DP와 분할 정복의 차이
DP와 분할 정복 모두 큰 문제를 작은 문제로 나누어 해결하는 공통점을 가지고 있다.
그러나, DP는 그 작은 문제가 중복되서 사용된다는 차이점이 있다.
또, DP는 앞에서 해결한 문제와 선형적으로 연관이 되어 있다.
F(N) = F(N - 1) + F(N - 2)처럼 N - 1, N - 2와 같이 선형적으로 결합되어 있다.
분할 정복은 그렇지 않고, 완전히 나누어 독립적으로 해결한 뒤, 해결된 결과 값을 조합할 뿐이다.
그래서 F(N) = A * F(N/B)같은 형태로 작은 문제들이 선형적이지 않은 관계로 구성된다.
