동적계획법과 분할정복의 차이 ,그리고 동적계획법의 특징

#동적 계획법(DP)이란?

 

DP의 두 가지 핵심 특성

1. 중복되는 부분 문제(Overlapping Subproblems):
   • 동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.
2. 최적 부분 구조(Optimal Substructure):
   • 최적 부분 구조란, 큰 문제의 해답이 그 문제를 구성하는 작은 문제들의 최적 해답으로부터 도출될 수 있다는 특성입니다. 즉, 작은 문제의 최적 해가 변하지 않고 그대로 전체 문제의 최적 해를 이루는 데 기여한다는 것입니다.
   • 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)로 계산할 수 있듯이, 작은 문제들의 최적해를 통해 큰 문제의 답을 구할 수 있습니다.

 

동적 계획법의 활용 예

• 피보나치 수열: 피보나치 수열을 재귀적으로 구할 때, 각 숫자의 결과를 저장하여 중복된 계산을 방지합니다.
• 배낭 문제: 배낭 문제에서 최대 가치를 구할 때, 각 부분 문제(작은 용량의 배낭에서 최대 가치를 구하는 문제)가 전체 문제의 해답을 구성합니다.

 

 

즉 DP 는 동일한 부분문제가 반복되면서 그 부분문제로 전체의 큰 문제를 풀 수 있으며

작은 문제의 최적 해가 바뀌지 않을 때 라고 할 수 있다.

 

 

 

#분할 정복(Divide and Conquer)이란?

**분할 정복(Divide and Conquer)**은 문제를 더 작은 부분 문제로 나눈 후, 각 부분 문제를 독립적으로 해결하고, 이들의 해답을 합쳐서 전체 문제를 해결하는 방식입니다. 분할 정복에서는 중복된 부분 문제가 발생하지 않으며, 각 부분 문제의 결과가 전체 문제의 최적 해답을 직접적으로 보장하지는 않습니다.

분할 정복의 특징

1. 최적 부분 구조가 없다:
   • 분할 정복에서는 각 부분 문제의 해답이 전체 문제의 최적 해답을 바로 보장하지 않습니다. 작은 문제들을 해결한 후, 이를 병합하는 과정에서 전체 문제의 해답이 달라질 수 있습니다.
   • 예를 들어, 병합 정렬(Merge Sort)에서 부분 배열이 정렬되었다고 해서 바로 전체 배열이 정렬되는 것은 아닙니다. 부분 배열들을 병합해야 최종적으로 전체 배열이 정렬됩니다.
2. 중복되는 부분 문제가 없다:
   • 분할 정복에서 각 부분 문제는 독립적입니다. 동일한 부분 문제가 여러 번 반복되지 않으며, 한 번 계산한 부분 문제는 다른 문제에서 다시 계산되지 않습니다.
   • 이는 동적 계획법과의 큰 차이점 중 하나입니다. 예를 들어, 병합 정렬에서 배열을 두 부분으로 나누어 정렬할 때, 같은 부분 문제를 반복해서 계산하지 않으며, 각 부분 문제는 독립적으로 처리됩니다.

분할 정복의 활용 예

• 병합 정렬(Merge Sort): 배열을 반으로 나누어 각각을 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 알고리즘입니다. 작은 문제들이 해결된 후에도 병합 과정에서 전체 해답이 결정됩니다.
• 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누어 각각을 정렬하고, 그 결과를 합쳐서 전체 배열을 정렬하는 알고리즘입니다.

 

동적 계획법 (DP)                                                                               분할 정복 (Divide and Conquer)

중복되는 부분 문제	존재함. 중복된 계산을 방지하기 위해 메모이제이션이나 테이블을 사용	중복된 부분 문제가 없으며, 각 부분 문제는 독립적으로 해결됨
최적 부분 구조	최적 부분 구조를 가짐. 작은 문제의 최적 해가 전체 문제의 최적 해를 구성	최적 부분 구조가 없음. 부분 문제의 해답이 전체 문제의 최적 해를 보장하지 않음
작은 문제의 해답	작은 문제의 해답은 바뀌지 않으며, 전체 문제를 해결하는 데 그대로 사용	작은 문제의 해답이 전체 문제를 해결하는 과정에서 다시 조정될 수 있음
해결 방식	작은 문제의 해답을 저장해 재사용, 중복 계산 방지	부분 문제를 독립적으로 해결하고, 해답을 병합하여 전체 문제를 해결
대표적인 예시	피보나치 수열, 배낭 문제, 최단 경로 문제	병합 정렬, 퀵 정렬, 이진 탐색

 

 

 

 

 

# 쉽게 생각해서..

 

예를들어서 병합정렬을 생각해보도록하자

병합정렬은 부분으로 나눠서 정렬하는데

결국에는 합쳐서 모두 정렬을 해야 되기 때문에

 

부분적으로 정렬한것이 그대로 최적해가 보장되지 않는다고 할 수 있다.

(부분 정렬한거 그대로 사용 안하니까)

때문에  부분 문제의 답이 최적해가 아니라고 볼 수 있고

 

그리고 또한

**병합 정렬(Merge Sort)**에서는 부분 배열을 계속해서 더 작은 부분으로 나눠도, 이미 처리된 부분 문제를 다시 처리하지 않는다. 이게 바로 중복되는 부분 문제가 없다는 의미이다

 

더 설명해보자면

병합정렬을 위해서 부분을 쪼개서 합치게 된다면

그 합쳐진 부분문제는 "다른문제" 라고 할 수 있다.

왜냐면 그 다른 문제를 풀때는 이전의 부분문제를 요구하지 않기 때문이다.

 

 때문에 이전문제를 메모리제이션 할 필요가 없으니 중복되는 부분문제라 볼수 없다