분할 정복 알고리즘(Divide and Conquer Algorithm)

목차

머리말

들어가기 전에

정렬 알고리즘

저번에 포스팅한 정렬 알고리즘에서 버블 정렬과 선택 정렬, 삽입 정렬에 대해 알아 보았다.

효율성

이 세 가지 정렬 알고리즘은 코드가 직관적이긴 하지만 데이터 크기 n에 대한 이중 for 문으로 되어 있기에 굉장히 비효율적이다.

분할 정복 알고리즘

이들의 시간복잡도는 $O(n^2)$이다. 보다 효율적인 정렬 알고리즘을 배우기 위해 분할 정복(Divide and Conquer)에 대해 알아 보자.

배우기 전 알아야 할 개념

재귀

그렇다면 위의 3단계는 어떻게 구현할 수 있을까? 분할과 정복, 통합은 재귀적으로(recursively) 하는 것이다.

따라서 재귀 알고리즘에 대해 먼저 알아야 분할 정복 알고리즘을 제대로 알 수 있다.

분할 정복 알고리즘(Divide and Conquer Algorithm)

Divide and conquer algorithms (article) | Khan Academy

분할 정복은 크게 3단계로 나눌 수 있다.

단계

1. 분할(Divide)

• 주어진 문제(problem)를 같은 형태의 작은 문제(subproblem)로 나눈다.
• 문제가 해결이 가능할 때까지 분할을 재귀적으로(recursively) 반복한다.

2. 정복(Conquer)

충분히 나누어져서 해결 가능한 작은 문제를 재귀적으로 해결한다.

3. 통합(Combine)

작은 문제에서 구한 해답을 서로 합쳐서 본래의 문제에 대한 해답을 도출한다.

• 작성일 2023-03-29 수
• 수정일 2023-12-27 수