기본 개념
분할정복법이란 주어진 문제를 동일 유형의 하위 문제로 나눈뒤 각각의 작은 문제들을 해결하여 정복하는 방식이다.
분할 정복법은 다음과 같이 크게 3단계의 과정을 통해 진행된다. 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있다.
-
분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. _divide
-
정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. _solve (conquer)
-
조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. _combine (merge)
* 장점: 문제를 나누어 해결함으로써 복잡한 문제를 부분적으로 해결하여 병렬형식로 문제를 보다 쉽게 해결한다는 장점이 있다.
* 단점 : 재귀함수를 사용함으로 인해 함수 호출에 의한 오버헤드가 발생
관련문제
쿼드트리 1992번 https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는
www.acmicpc.net
Z 1074번 https://www.acmicpc.net/problem/1074
1074번: Z
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 ��
www.acmicpc.net
부분배열 고르기 2104번 https://www.acmicpc.net/problem/2104
2104번: 부분배열 고르기
크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 ��
www.acmicpc.net
히스토그램 1725번 https://www.acmicpc.net/problem/1725
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 �
www.acmicpc.net
'알고리즘스터디' 카테고리의 다른 글
| [알고리즘] 이진 탐색 알고리즘 (Binary Search Algorithm) (0) | 2020.09.29 |
|---|---|
| [알고리즘] 동적 계획법 (Dynamic Programming) (0) | 2020.09.18 |
| [알고리즘] 탐욕법 (Greedy Algorithm) (0) | 2020.09.07 |
| [알고리즘] 완전 탐색 (Exhaustive search) (0) | 2020.08.31 |
| [알고리즘] 버킷 정렬 (Bucket Sort) (0) | 2020.08.26 |