분할 정복

✅ 분할 정복

• 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 각각의 작은 문제들을 해결하여 정복(Conquer) 하는 방법이다. 문제에 대한 답을 재귀 호출을 이용하여 계산하고 각 부분 문제의 답으로 부터 전체 문제의 답을 계산해 낸다.

• 일반 적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

• 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 순환적으로 분할 하고 분할된 작은 문제들을 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

• 경우가 많은 작업의 경우 더 빠르게 처리

출처 https://data-make.tistory.com/232

💨 3가지의 구성 요소

1 문제를 더 작은 문제로 분할

2 각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 과정

3 더이상 분할 하지 않고 곧장 풀 수 있는 매우 작은 문제

💨 해결하기 위한 문제의 조건

• 둘 이상의 부분 문제로 나누는 자연스러운 방법 존재

• 부분 문제의 답을 조합 해 원래 문제의 답을 계산하는 효율적 방법 존재

쓰이는 예

이분검색, 합병정렬, 퀵정렬, 최대값 찾기, 임계값의 결정, 쉬트라센 행렬곱셈 알고리즘 등

▶ 병합정렬과 퀵정렬

💨 병합 정렬

• 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

출처 https://sexycoder.tistory.com/73

💨 퀵 정렬

• 퀵 정렬은 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다.

• 이를 위해 퀵 정렬은 파티션이라고 부르는 단계를 도입하는데, 이는 기준수를 지정한 후 기준보다 작거나 같은 숫다를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정을 진행한다.

출처 https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html