일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- #크랙미4번
- #abex크랙미4번
- GraphQL
- #리버싱
- #고클린
- #크랙미 5번
- #크랙미 9번
- #abex
- Easy
- Spring
- #보안이슈
- #크랙미3번
- java8
- #심플즈
- #크랙미
- springframework
- #보안뉴스
- #abex크랙미
- java
- 리버싱
- #크랙미 10번
- #파밍
- #심플즈 크랙미
- leetcode
- #크랙미2번
- Today
- Total
Halo World
분할정복 본문
분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.
분할 정복을 사용하는 알고리즘의 세 가지 구성요소
- 문제를 더 작은 문제로 분할하는 과정(divide)
- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
분할 정복을 적용해 문제를 해결하기 위해서는
1. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하며,
2. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.
[예제] 수열의 빠른 합
1부터 n까지의 합을 구하는 분할 정복 알고리즘
//필수조건 : n은 자연수
//1+2+...+n을 반환한다.
int fastSum(int n) {
if(n==1) return 1;
if(n%2 == 1) return fastSum(n-1) + n;
return 2*fastSum(n/2) + (n/2)*(n/2);
}
시간 복잡도
n의 이진수 표현의 자릿수 + 첫 자리를 제외하고 나타나는 1의 개수. 두 값의 상한은 모두 logn 이므로 시간복잡도는 O(logN)
[예제] 행렬의 거듭제곱
A = n*n 크기의 행렬
A^m = A^(m/2) x A^(m/2)
행렬의 거듭제곱을 구하는 분할정복 알고리즘
//정방행렬을 포현하는 SquareMarix 클래스가 있다고 가정하자.
class SquareMatrix;
//n*n크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
//A^m을 반환한다.
SquareMatrix pow(const SquareMatreix& A, int m) {
if(m==0) return identity(A.size());
if(m%2 > 0) return pow(A, m-1) * A;
SquareMatrix half = pow(A, m/2);
//A^m = (A^(m/2))*(A^(m/2))
return half * half;
}
[예제] merge sort와 quick sort
병합 정렬과 퀵 정렬은 모두 분할 정복 패러다임에 기반하여 만들어진 것들이다.
병함 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.
반대로 퀵 정렬 알고리즘은 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽의 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 퀵 정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.
병합 정렬은 주어진 배열을 나누는데는 O(1) 시간이 소요되지만, 정렬한 배열들을 하나로 합치는데 O(n)의 시간이 걸린다. 반면 퀵 정렬은 분할에서 O(n)의 시간이 걸리지만, 별도의 병합 작업이 필요 없다.
병합 정렬과 퀵 정렬의 시간복잡도 (부분 문제가 절반에 가깝게 나누어 지는 경우) : O(NlogN)
[문제] 쿼드 트리 뒤집기
algospot.com/judge/problem/read/QUADTREE
string reverse(string::iterator& it) {
char head = *it;
++it;
if(head == 'b' || head == 'w')
return string (1,head)
string upperLeft = reverse(it);
string upperRight = reverse(it);
string lowerLeft = reverse(it);
string lowerRight = reverse(it);
return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}
[문제] 울타리 잘라내기
algospot.com/judge/problem/read/FENCE
//각 판자의 높이를 저장하는 배열
vector<int> h;
//h[left,right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환
int solve(int left, int right) {
if(left == right) return h[left];
int mid = (left + right)/2;
int ret = max(solve(left, mid), solve(mid+1, right));
//두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
int lo = mid, hi = mid+1;
int height = min(h[lo], h[hi]);
//[mid, mid+1]만 포함하는 너비 2인 사각형을 고려한다.
ret = max(ret, height * 2);
//사각형이 입력 전체를 덮을 때까지 확장해 나간다.
while(left<lo || hi<right) {
//항상 높이가 더 높은 쪽으로 확장한다.
if(hi < right && (lo==left || h[lo-1] < h[hi+1])) {
++hi;
height = min(height, h[hi]);
}
else {
--lo;
height = min(height, h[lo]);
}
//확장한 후 사각형의 넓이
ret = max(ret, height * (hi - lo + 1));
}
return ret;
}
출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 - 구종만 저
'개발 지식 > ALGORITHM' 카테고리의 다른 글
LeetCode 1025. Divisor Game - DP (0) | 2021.02.11 |
---|---|
리스트로 구현한 스택 (0) | 2017.07.11 |
정렬 알고리즘 (0) | 2017.06.03 |