① 분할 정복(divide and conquer)은 컴퓨터 과학과 알고리즘 설계에서 널리 사용되는 문제 해결 전략이다.
㉠ 분할(divide) : 분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 분할하는 과정을 거친다.
㉡ 정복(conquer) : 분할된 하위 문제를 재귀적으로 해결하는 과정을 거친다. 하위 문제의 크기가 충분히 작아질 경우, 직관적인 방법으로 해결할 수 있다.
㉢ 결합(combinie) : 분할된 문제를 다시 결합하면서 원래의 큰 문제의 해결책을 구한다.
② 분할 정복을 사용하는 유명한 알고리즘의 예시는 병합/합병 정렬(merge sort), 퀵 정렬(quick sort), 고속 푸리에 변환(fast fourier transform, FFT), 쉬트라센의 행렬 곱셈(Strassen's Matrix Multiplication) 등이 있다.
③ 분할 정복 알고리즘을 사용하면 문제를 간단하게 하는 것이 가능하다.
㉠ 커다란 문제를 작은 하위 문제로 분할하기 때문에 원래의 문제에서는 풀 수 없어 보였던 것을 쉽게 해결할 수 있다.
ⓐ 백준 1074번 문제를 예시로 들 수 있다.
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
백준 1074번 : Z
hemahero.tistory.com
ⓑ 백준 1992번 문제를 예시로 들 수 있다.
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
백준 1992번 : 쿼드트리
hemahero.tistory.com
ⓒ 백준 10830번 문제를 예시로 들 수 있다.
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
백준 10830번 : 행렬 제곱
hemahero.tistory.com
ⓓ 백준 2263번 문제를 예시로 들 수 있다.
2263번: 트리의 순회
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
백준 2263번 : 트리의 순회
hemahero.tistory.com
㉡ 분할 정복 알고리즘의 하위 문제들은 독립적인 해결책을 갖고 있을 수 있는데, 이러한 경우 여러 프로세서나 코어에서 병렬로 연산할 수 있다.
ⓐ 현대 병렬 컴퓨팅 시스템의 발전으로 분할 정복 알고리즘의 중요성이 커졌다.
㉢ 분할 정복 알고리즘은 정렬, 탐색, 그래프 알고리즘 등 다양한 알고리즘에 적용할 수 있다.
④ 분할 정복 알고리즘은 재귀식을 사용하여 시간 복잡도를 구할 때 큰 도움을 준다.
㉠ 예를 들어 아래 시간 복잡도는 병합 정렬(merge sort)의 시간 복잡도이다.
ⓐ n이 1보다 클 경우 n을 반으로 쪼개서 문제의 크기를 반으로 줄일 수 있다.
ⓑ 문제의 크기가 1이 될 때까지 쪼개기 때문에 문제의 크기가 n일 때, 문제의 크기가 log(n)으로 줄어들었다. 따라서 분할에 걸리는 시간은 O(log(n))이다.
ⓒ 분할된 하위 문제를 다시 결합하는데, 이는 분할의 역연산과 같기 때문에 결합에 걸리는 시간은 O(log(n))이다.
ⓓ 선형 탐색(linear search)에 걸리는 시간은 O(n)이다.
ⓔ 병합 정렬에 걸리는 시간 T(n) = O(nlog(n))이다. O(n^2)인 다른 정렬에 비교하면 상당히 빠르다는 것을 알 수 있다.
㉡ 문제의 크기를 절반이 아닌 여러 크기로도 분할할 수 있다.
ⓐ 분할한 하위 문제의 크기의 합은 원래 크기가 되야 한다.
㉢ 시간 복잡도를 구하는 좀 더 자세한 내용은 아래를 참고하자.
마스터 정리(Master Theorem)
※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 마스터 정리(master theorem)는 복잡한 알고리즘(recursive algorithm)의 시간 복잡도를 구하기 위해 사용한다. ② 마스터 정리로 해결할 수 있는 알고리
hemahero.tistory.com
'All about Data Structure & Algorithm > 심화' 카테고리의 다른 글
| 홀짝 정렬(Odd-Even sort) (0) | 2023.03.31 |
|---|---|
| 향상된 퀵 정렬 (0) | 2023.03.24 |
| 셸 정렬(Shell Sort) (0) | 2023.03.24 |
| 일반 마스터 정리(Generalized Master theorem) (0) | 2023.03.15 |
| 마스터 정리(Master Theorem) (0) | 2023.03.14 |
