[Algorithm] 분할정복 알고리즘 맛보기

이번 포스팅은 분할정복을 처음 배우면서 맛보기(?)를 하면서 끄적인 것이기 때문에 두서가 없습니다.

 

분할정복에 대해 자세히 알고 싶으신 분은 아래를 참고해주시면 감사하겠습니다.

 

 

 

 

👉 분할정복

2022.09.28 - [Computer Science/Algorithm] - [Algorithm] 분할정복(1) - Master Theorem과 일반해

[Algorithm] 분할정복(1) - Master Theorem과 일반해

2022.09.29 - [Computer Science/Algorithm] - [Algorithm] 분할정복(2) - Multiplication

[Algorithm] 분할정복(2) - Multiplication

2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 분할정복(5) - Median of Medians

[Algorithm] 분할정복(5) - Median of Medians

 

 

 

🤔 Divide-And-Conquer

Divide-And-Conquer(분할 정복)이란 일반적으로 주어진 문제가 클 때 이를 divide(분할)하여 input size를 줄입니다.

이때 divide 하여 input size를 줄인 문제의 단위를 subproblem이라고 합니다.

위와 같이 주어진 문제를 아래의 방식으로 해결할 수 있습니다.

 

 

1. 주어진 문제를 subproblem으로 쪼갭니다.

2. 1번에서 나눈 subproblem들을 base-case에 도달할 때 까지 recursively 하게 해결합니다.

3. 2번에서 푼 subproblem들의 답을 적절하게 조합하여 본 문제의 답을 제시합니다.

 

 

이때 2번과 3번이 conquer을 의미합니다.

 

 

Divide-And-Conquer Algorithm의 핵심은 "작은 단위의 문제 해결을 통해 큰 문제를 해결하는 것"입니다.

 

 

지금부터 Divide-And-Conquer Algorithm에 대해 알아보겠습니다.

 

 

 

 

 

 

 

 

 

🔎 Merge Sort

Merge Sort는 Divide-And-Conquer을 사용한 정렬 방식 중 하나입니다.

 

 

다음과 같은 A라는 배열이 존재할 때 오름차순으로 Merge Sort를 진행해보겠습니다.

 

 

 

1. 먼저 배열 A를 두 개의 subproblem으로 쪼갭니다.

 

 

 

 

2. 아직 Base Case가 나오지 않았으므로 1번 과정을 반복합니다.

 

 

 

여기서 중요한 것은 "구조"입니다.

각각이 Subproblem을 의미하고 가장 아래가 Base Case이므로 이는 트리구조로 나타낼 수 있다는 것을 알 수 있습니다.

 

위와 같이 recursion을 통해 Subproblem이 파생되는 모양을 그린 트리를 Recursion Tree라고 합니다.

Recursion Tree의 Root는 원래 문제의 input이 되며, leaf node 들은 base case의 input이 됩니다.

 

 

 

 

3. Base Case Subproblem을 해결합니다.

 

 

Subproblem들의 답을 이용하여 leaf node에 해당하는 문제의 답으로 부터 시작하여 Recursion Tree를 거꾸로 올라가면서 답을 구합니다.(Bottom-Up Solution)

 

 

Merge Sort의 최종 결과는 아래와 같습니다.

 

 

 

 

 

Merge Sort에 대한 자세한 정보는 아래의 링크에서 확인하실 수 있습니다.

 

 

 

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Master Theorem

Master Theorem은 재귀 관계식으로 표현할 알고리즘의 동작 시간을 점근적으로 계싼하여 간단하게 계산하는 방법입니다.

 

복습을 했지만 이해가 부족하여 이해한 후에 다시 작성하겠습니다.

 

 

 

 

 

 

 

 

 

아래의 링크에서 복습이후 이해한 내용을 정리했습니다.

 

 

 

 

https://2t-hong.tistory.com/60

[Algorithm] 분할정복(1) - Master Theorem과 일반해