[algorithm] 분할 정복 알고리즘 Divide and Conquer

 

 

분할 정복(Divide and Conquer) 알고리즘에 대해 알아보자

 

안녕하세요 👀 오늘은 분할 정복(Divide-Conquer) 알고리즘에 대해서 배워볼게요. 분할 정복 알고리즘은 제가 좋아하는 수학자 존 폰 노이만이 개발한 정렬 알고리즘이에요. 정렬은 컴퓨터 과학에서 가장 기본적이면서 중요한 작업 중 하나인데요. 대용량의 데이터를 효율적으로 정렬하는 것은 많은 애플리케이션에서 핵심적인 부분이기 때문입니다. 이번 포스팅에서는 분할정복 알고리즘에 대해 알아볼게요 🧐

 

 

 

---

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

분할 정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 부분 문제로 분할하여 각각을 해결하고, 그 결과를 다시 결합하여 원래의 문제를 해결하는 알고리즘입니다. 분할 정복 알고리즘은 아래의 세 단계를 통해서 이루어집니다.

 

 

📍 분할 정복 알고리즘의 세 단계

1. 분할(Divide)

주어진 문제를 작은 부분 문제로 분할합니다.

이 단계에서 문제를 동일한 형태의 하위 문제들로 쪼갤 수 있어야 합니다. 일반적으로 재귀적인 방법을 사용하여 분할을 수행합니다.

 

2. 정복(Conquer)

분할된 부분 문제들을 독립적으로 해결합니다.

각 하위 문제는 원래 문제의 부분 집합으로 간주되며, 동일한 알고리즘을 적용하여 해결됩니다. 이 단계에서는 하위 문제의 해답을 얻습니다.

 

3. 결합(Combine)

해결된 부분 문제들의 해답을 결합하여 원래의 문제를 해결합니다.

이 단계에서 하위 문제의 결과를 조합하거나 병합하여 최종적인 해답을 얻습니다.

 

 

 

📍 divide & conquer 흐름

분할 정복 알고리즘의 전체적인 흐름이 어떻게 이루어지는지 알아볼게요.

 

먼저 배열이 주어집니다.

 

위 배열을 두 개로 분할(divide) 합니다

 

 

분할된 배열은 또 다시 새로운 배열로서 재귀적으로 분할합니다.

 

 

위 과정을 요소가 하나가 될 때까지 반복하면 위의 그림처럼 됩니다.

 

 

그리고 분할된 요소를 정렬방식을 통해 순서를 정하여서 다시 합칩니다.

 

이러한 일련의 과정들을 분할 정복 알고리즘이라고 합니다.

 

 

 

---

🍊 요약

이처럼 분할 정복 알고리즘에 대해서 알아보았습니다. 분할 정복 알고리즘은 크고 복잡한 문제를 작은 부분으로 분할하여 각각을 해결하고, 그 결과를 결합함으로써 효율적으로 답을 구해내는 알고리즘입니다. 이러한 알고리즘의 활용은 다른 알고리즘의 성능과 효율성을 높여주는데요. 대표적으로 병합 정렬(merge sort)과 퀵 정렬(quick sort)에 활용할 수 있습니다. 다음에는 이 두 알고리즘에 대해서 알아볼게요 👀

 

 

 

참고문서

https://www.programiz.com/dsa/divide-and-conquer

Divide and Conquer Algorithm