센로그
2장. 분할 정복법 (Divide & Conquer) 본문
◆ 분할 정복식 설계 전략
큰 문제를 작은 문제로 나누어 해결한 후, 해답을 모아 큰 문제의 해를 만드는 방법
문제의 성질과 전체 형태가 작은 문제에서도 똑같이 유지 됨 <-- 재귀적인 형태도 가능!
분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
정복(Conquer): 나눈 작은 문제를 각각 해결한다.
통합(Combine): (필요하다면) 해결된 해답을 모은다.
이러한 문제 해결 방법을 하향식(top-down) 접근 방법이라고 한다.
◆ 바닥 함수와 천장 함수
바닥 함수: 실수 x에 대해, x보다 작거나 같은 정수 중 가장 큰 정수
천장 함수: 실수 x에 대해, x보다 크거나 같은 정수 중 가장 작은 정수
◆ 이분 검색 (binary search)
배열을 반으로 나눠서, 찾아야할 x와 location을 비교해 location을 옮겨감
재귀적 방식으로 진행함
✓ 분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고,
그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다.
✓ 통합 : 없음
| ※ 입력 파라미터 n, S, x는 수행중 변하지 않는 값이므로, 재귀 호출시마다 계속 갖다니면 낭비! 얘네를 전역변수로 지정하고, 재귀 호출 시에는 인덱스만 넘겨줄 수 있음. ※ 반복 알고리즘이 재귀 알고리즘보다 상수적으로 계산이 빠름. (계산 복잡도가 좋다는 건 아님) |
◇ 이분 검색 코드
index location(index low, index high){
index mid;
if (low > high) //데이터가 없는 경우
return 0;
else{
mid = (low + high) / 2; //중간 값 갱신
if (x == S[mid]) //key를 찾은 경우
return mid;
else if (x < S[mid]) //key가 중간값보다 작은 경우
return location(low, mid - 1); //왼쪽 배열 반 선택
else //key가 중간값보다 큰 경우
return location(mid + 1, high); //오른쪽 배열 반 선택
}
}
◇ 이분 검색 - 최악의 경우 시간 복잡도 분석
- 단위연산 : x와 S[mid]의 비교
- 입력크기 : 배열의 크기 n
이분 검색에서 최악의 경우는, 검색하게 될 반쪽 배열의 크기가 항상 정확히 절반이 되는 경우이다.
W(n) 을 n에 대한 Worst Case의 시간 복잡도 함수라 하자.
아래와 같이 W에 관한 식이 W로 또 표현되는 걸 재현식, 연쇄식이라 함
배열의 크기가 n인 경우의 비교 횟수는, 배열의 크기가 n/2인 경우의 비교횟수 + 처음 비교횟수 1번이라는 뜻
이러한 재현식의 해는, W(1) = 1인 성질을 가지고 대입해가며 풀거나
아래와 같이 반복 대입법을 통해 구할 수 있다.
ㆍ반복 대입법 : W를 W에 대입하여 규칙을 찾는 방법
n =1 인 경우에도 x와 S[mid]가 같은지 한번 비교하기 때문에, W(1) = 1
◆ 합병 정렬 (merge sort)
쪼갰다가 정렬하면서 합쳐서 올라오기
| 데이터의 개수가 1보다 크면 S[1]부터 S[h]까지(절반)을 U에다 복사 S[h+1]부터 S[n]까지(남은 절반)을 V에다 복사 Mergesort(h,U)가 종료되면 정렬된 U가 얻어질 것이고 Mergesort(m,V)가 종료되면 정렬된 V가 얻어질 것! 그러고나면 merge(h,m,U,V,S)로 얘네를 합치면서 정렬하면 댐 |
<과정>
◇ 합병 정렬 코드
void mergesort(int n, keytype S[]){
const int h = n/2, m = n - h; // 반씩 나눔
keytype U[1..h], V[1..m]; // U, V
if (n > 1){ // 데이터의 개수가 1보다 크면
copy S[1...h] to U[1...h]; // S[1~h]를 U로 복사
copy S[h+1...n] to V[1...m]; // S[h+1~n]을 V로 복사
mergesort(h, U); // U에서 mergesort 재귀 --> 정렬된 U가 나옴
mergesort(m, V); // V에서 mergesort 재귀 --> 정렬된 V가 나옴
merge(h, m, U, V, S); // 각각 정렬된 U,V를 다시 합침
}
}
void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]){
index i, j, k; // U[i], V[j], S[k]
i = 1; j = 1; k = 1; // 1로 초기화
while (i <= h && j <= m){ //
if (U[i] < V[j]){ // U의 데이터가 V의 데이터보다 작으면
S[k] = U[i]; // U의 데이터를 S로 복사
i++; // U의 인덱스 증가
}
else{ //V의 데이터가 U의 데이터보다 작으면
S[k] = V[j]; //V의 데이터를 S로 복사
j++; //V의 인덱스 증가
}
k++; //S의 인덱스 증가
}
if (i > h) //U의 데이터가 모두 S로 옮겨감 -> 인덱스 다 돌았는데 V의 데이터 남은 경우
copy V[j...m] to S[k...h+m]; // V의 남은 데이터들 S로 복사
else //V의 데이터가 모두 S로 옮겨감 -> 인덱스 다 돌았는데 U의 데이터 남은 경우
copy U[i...h] to S[k...h+m]; // U의 남은 데이터들 S로 복사
}
◇ 합병 정렬 - 최악의 경우 시간 복잡도 분석
■ merge 함수
- 단위연산 : merge 함수에서의 U[i]와 V[j]의 비교
- 입력크기 : h와 m
merge 함수에서 최악의 경우는, 합병시 U, V 데이터를 하나씩 번갈아가며 합친 경우이다.
즉, i = h + 1이고, j = m인 상태로 루프를 빠져나가는 경우가 최악이다.
이때 단위연산의 시행 횟수는 h + m - 1이다.
따라서 W(h,m) = h + m -1
■ mergesort 알고리즘
- 단위연산 : merge()에서 발생하는 비교
- 입력크기 : S의 데이터의 개수인 n
mergesort 알고리즘에서 최악의 경우는, U를 정렬하는 데 걸리는 시간 + V를 정렬하는 데 걸리는 시간 + 합병하는 데 걸리는 시간이 젤 오래 걸리는 경우이다. 즉, W(h) + W(m) + h + m -1이다. 이때 h와 m은 n/2이므로, W(n) = 2W(n/2) + n - 1이라 할 수 있다.
▽ 이정돈 유도할 수 있어야 함
입력 크기가 1이면 비교 자체를 안 들어가므로 W(1) = 0
◇ 합병 정렬 - 공간 복잡도 분석
합병 정렬은 입력 배열S 외에, U와 V를 추가로 만들어서 사용하기 때문에, 제자리 정렬이 아님
| ※ 제자리 정렬(in-place sort) 알고리즘이란? 추가적인 저장 장소를 사용하지 않고 정렬하는 알고리즘 |
다음 재귀 호출에는 n/2의 추가적인 저장 장소가 필요하므로, 필요한 총 저장 장소의 크기는 다음과 같다.
즉 2n만큼의 추가 저장 장소가 필요함!
◇ 공간 복잡도가 향상된 합병 정렬
합병 정렬이 제자리 정렬이 될 수는 없지만, 2n만큼 요구되는 추가 저장 장소를 n만큼으로 줄일 수는 있음.
| S에서 인덱스를 사용해 반절, 반절 나눠서 U에다 정렬하며 옮겨쓴 후, 끝나기 직전에 U를 다시 S에다 옮겨 적음 |
그림에서 A가 모두 정렬된 후 B를 정렬함. 이때 A에서 사용이 끝난 추가 공간을 재사용할 수 있음.
일단 나눠놓고 나중에 복사하는 방식!
앞에서는 맨 끝단이 정렬될 때까지 쭉 공간을 붙잡고 있었지만,
이 방법은 중간중간 메모리를 반납하면서 사용하기 때문에 공간적 측면에서 더 효율적임.
void mergesort2(index low, index high){
index mid;
if (low < high){
mid = (low + high) / 2;
mergesort2(low, mid);
mergesort2(mid + 1, high);
merge2(low, mid, high);
}
}
void merge2(index low, index mid, index high){
index i, j, k; //U[i], U[j], S[k]
keytype U[low...high];
i = low;
j = mid + 1;
k = low;
while (i <= mid && j <= high){ // U 왼쪽과 오른쪽에 비교할 데이터가 남았다는 뜻
if (S[i] < S[j]){ // 각각 정렬된 상태
U[k] = S[i]; // U에다 S 앞쪽 데이터 넣기
i++;
}
else{
U[k] = S[j];
j++;
}
k++;
}
if (i > mid) //S의 왼쪽 부분이 다 U에 복사됨 -> 오른쪽 부분이 남음
copy S[j...high] to U[k...high]; //S에 남은 오른쪽 부분을 U에 복사
else //S의 오른쪽 부분이 다 U에 복사됨 -> 왼쪽 부분이 남음
copy S[i...mid] to U[k...high]; //S에 남은 왼쪽 부분을 U에 복사
copy U[low...high] to S[low...high]; //U에 정렬된 데이터들을 S로 복사
}
◆ Quick sort
파티션 → 퀵소트(피봇왼쪽) →퀵소트(피봇오른쪽)
파티션은 : pivotpoint보다 작은 것/큰 것으로 배열을 분리할 수 있도록 하는 pivotpoint의 자리 찾기
| partition(low, high, &pivotpoint) 함수에서 pivotitem과 S[i]를 하나씩 비교. pivotitem > S[i]인 경우가 나오면 pivotpoint++ 하고, S[i]와 S[pivotpoint] 바꾸기 끝까지 가면 pivotpoint 인덱스 리턴 (이때 pivotitem과 S[pivotpoint] 바꾸면, pivotitem 기준 왼쪽/오른쪽 분리됨) |
quicksort는 아래와 같이 분할 정복 방법을 따름.
quick sort의 경우, 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되지 않는 Unstable Sort이다.
◇ Quick sort 코드
void quicksort (index low, index high) {
index pivotpoint;
if (high > low) { // 적어도 데이터가 2개일 때
partition(low,high,pivotpoint); // pivotpoint의 적절한 위치를 잡아서 레퍼런스로 돌려줌
quicksort(low,pivotpoint-1); // pivotpoint 왼쪽부분 quicksort
quicksort(pivotpoint+1,high); // pivotpoint 오른쪽부분 quicksort
}
}
partition()을 통해 pivotpoint의 적절한 위치를 잡아서 레퍼런스로 돌려줌
void partition (index low, index high, index& pivotpoint){
index i, j;
keytype pivotitem;
pivotitem = S[low]; // 맨 왼쪽에 있는 데이터를 pivotitem으로 설정
j = low; // j를 맨 왼쪽 데이터로 초기화. j는 잠재적 pivotpoint
for (i = low + 1; i <= high; i++){ // i는 젤 왼쪽 다음~ 젤 오른쪽까지
if (S[i] < pivotitem){ // S[i]가 현재 pivotitem보다 작으면,
j++; // j 하나 증가 (S[i] 들어갈 자리 하나 확보)
exchange S[i] and S[j]; //S[i] <-> S[j] 해서 S[i]를 앞쪽으로 옮김
}
} //j: pivotitem 보다 작은 그룹의 제일 우측 끝 데이터의 위치
pivotpoint = j; // 반환할 pivotpoint 인덱스 위치 설정
exchange S[low] and S[pivotpoint]; // 현재 pivotitem 값을 pivotpoint(올바른 위치임)에 넣어준다.
}
◇ Quick sort - 시간 복잡도 분석
■ partition 함수
- 단위연산 : S[i]와 pivotitem의 비교
- 입력크기 : high-low+1
partition 함수에서는 입력 배열의 첫 항목 빼고 나머지 항목을 한번씩 비교하므로, T(n) = n-1 이다.
■ quicksort 알고리즘
- 단위연산 : partition 알고리즘의 S[i]와 pivotitem의 비교
- 입력크기 : 배열 S의 총 항목 수인 n
quicksort 알고리즘에서 최악의 경우는, 입력 배열이 이미 비내림차순으로 정렬되어 있는 경우이다.
즉 n 크기의 분석을 한 다음 차례에 n-1개의 분석을 해야 함.
따라서 T(n) = T(n-1) + n-1 이다. 이 재현식을 풀면 다음과 같다.
따라서 quicksort 알고리즘의 최악의 시간 복잡도 W(n) = n(n-1)/2 이다.
참고) 최선의 경우는, 문제가 매번 반씩으로 나누어질 때를 의미한다.
그때의 시간 복잡도 함수는 아래와 같다.
◆ 행렬 곱셈 (matrix multiplication)
단순한 행렬 곱셈 알고리즘은 행렬의 크기가 커질수록 계산량이 많아지므로 다른 방법이 필요함
여기서는 행렬의 곱셈을 어떻게 빨리 하느냐가 아니라, 어떻게 분할정복법으로 적용할 수 있는지 알아볼 것임
◇ 단순한 행렬 곱셈 코드
void matrixmult (int n, const number A[][], const number B[][], number C[][]) {
// nxn 행렬인 A,B를 곱해서 C를 출력
index i, j, k;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
C[i][j] = 0; // 일단 계산전에 0으로 초기화
for (k = 1; k <= n; k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j]; // 행렬 곱셈
}
}
}
◇ 단순한 행렬 곱셈 - 시간 복잡도 분석
■ 곱셈 기준
- 단위연산 : 맨 안쪽 루프의 곱셈 연산
- 입력크기 : n
모든 경우 시간 복잡도는 총 곱셈 횟수(한자리에 필요한 곱셈 * 행 개수 * 열 개수)이므로, T(n) = n * n * n = n³
■ 덧셈/뺄셈 기준
- 단위연산 : 맨 안쪽 루프의 덧셈 연산
- 입력크기 : n
모든 경우 시간 복잡도는 총 덧셈 횟수(한자리에 필요한 덧셈 * 행 개수 * 열 개수)이므로, T(n) = (n-1) * n * n = n³ - n²
ex) 2x2 행렬
--> 총 8번의 곱셈과 4번의 덧셈이 필요함.
◆ 행렬 곱셈 - 쉬트라센 방법 (Strassen Algorithm)
행렬 곱셈에서 덧셈, 뺄셈을 늘리는 대신에 곱셈 횟수를 하나 줄인 방법
위와 같이 2x2행렬 곱셈이 주어졌을 때, 쉬트라쎈(Strassen)의 해는 다음과 같다.
여기서 각 원소는 아래와 같이 표현됨
2x2 행렬 곱셈시, 7번의 곱셈과 18번의 덧셈(뺄셈)이 필요함.
언뜻 봐서는 별로지만, 행렬 크기가 어느정도 이상으로 커지면 좋아진다!
◇ 행렬 곱셈 - 쉬트라쎈 방법 코드
void strassen (int n, n*n_matrix A, n*n_matrix B, n*n_matrix& C){
if (n <= threshold) // n이 임계점보다 작은 경우
단순한 알고리즘을 사용하여 C = A * B를 계산
else {
A를 4개의 부분행렬 A11, A12, A21, A22로 분할
B를 4개의 부분행렬 B11, B12, B21, B22로 분할
쉬트라센 방법을 사용하여 C = A * B를 계산
// 되부르는 호출의 예: strassen(n/2, A11+A22, B11+B22, M1)
}
}
n이 2의 거듭제곱인 nxn 행렬에서, 다음과 같이 나눠서 진행함.
※ 행렬의 크기가 2의 거듭제곱이 아닌 경우에는, 크기를 맞추기 위해 필요한 만큼 0을 넣어서 푼다.
◇ 행렬 곱셈 - 쉬트라쎈 시간 복잡도 분석
■ 곱셈 기준
- 단위연산: 곱셈 연산
- 입력크기: 행과 열의 수, n
임계값을 1이라 하자. 재현식은 다음과 같다.
이 식을 전개해보면,
따라서 T(n) ∈ Θ(n^2.81) 이다.
■ 덧셈/뺄셈 기준
- 단위연산: 덧셈/뺄셈 연산
- 입력크기: 행과 열의 수, n
임계값을 1이라 하자. 재현식은 다음과 같다.
이 식을 정리해보면,
따라서 T(n) ∈ Θ(n^2.81) 이다.
◇ 단순 행렬 곱셈 vs 쉬트라쎈 시간복잡도 비교
임계점(두 알고리즘의 효율성이 교차하는 시점)을 넘어가면, 쉬트라센 알고리즘이 단순한 곱셈 알고리즘보다 효율적!!
◆ 큰 정수의 곱셈
보통 n자리수의 두 숫자를 곱하는 데 걸리는 시간은 n². 즉 2차 시간이 걸림
이걸 1차 시간만 걸리도록 만들 수 있음!
u * v를 계산한다고 하자. u와 v를 다음과같이 표현함
← n자리 수인 u를, ⌈n/2⌉자리 수인 x와 ⌊n/2⌋자리 수인 y로 표현
이렇게 곱하면 1차 시간에 수행하는 셈이다.
⎣n/2⎦
◇ 큰 정수의 곱셈 코드
large_integer prod(large_integer u, large_integer v){
large_integer x, y, w, z;
int n, m;
n = maximum(u의 자리수, v의 자리수);
if(u == 0 || v == 0)
return 0;
else if( n <= threshold)
return 일반적인 방법으로 구한 u × v ;
else{
m = ⎣n/2⎦;
x = u divide 10m; y = u mod 10m;
w = v divide 10m; z = v mod 10m;
return prod(x, w) × 10^(2m) + (prod(x, z)+prod(w, y)) × 10^m + prod(y, z);
}
}prod 안에서 prod를 4번 불러서 수행함.
근데 사실..
이때도 최악의 경우 시간복잡도 W(n) ∈ Θ(n²)이라, 원래 방법과 비교했을 때 노이득임
◇ 큰 정수의 곱셈 - 개선 ver
r 계산을 추가해 곱셈 한번을 줄여주는 방법
이것도 분할 정복으로
큰 자리수 곱셈 문제를 쪼개서 작은 자리수 곱셈 문제로 해결한 후 전체 문제를 처리하는 방식임
<방법>
r에서 xz+yw를 한번에 구해서 전개식에 대입하면 곱셈 횟수를 한번 줄일 수 있음.
◇ 큰 정수의 곱셈 - 개선 ver 코드
large_integer prod2(large_integer u, large_integer v){
large_integer x, y, w, z, r, p, q;
int n, m;
n = maximum(u의 자리수, v의 자리수);
if(u == 0 || v == 0)
return 0;
else if( n <= threshold)
return 일반적인 방법으로 구한 u × v ;
else{
m = ⎣n/2⎦;
x = u divide 10m; y = u mod 10m;
w = v divide 10m; z = v mod 10m;
r = prod2(x+y,w+z);
p = prod2(x, w);
q = prod2(y, z);
return p×10^(2m) + (r–p-q)×10^m + q; // p = zw // r-p-q = xz + yw // q = yz
}
}prod 안에서 prod를 3번 불러서 수행함
최악의 경우 시간복잡도 W(n) ∈ Θ(n^(1.58)) 정도에 속함. 굿
◆ 분할 정복법을 사용하지 말아야 하는 경우
1) 시간복잡도가 형태인 경우
- 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우
2) 시간복잡도가 의 형태인 경우
- 크기가 n인 입력이 n개 이상의 조각으로 분할되며, 분할된 부분의 크기가 인 경우
◆ 도사 정리
T(n) = aT(n/b) + f(n)일 때 시간 복잡도 함수를 쉽게 구하는 법.
T(n) = aT(n/b) + f(n)이고, nlogb a = g(n)이라 하자
이때, 다음 내용을 만족한다.
- g(n)이 더 무거우면 g(n)이 수행 시간을 결정함
- f(n)이 더 무거우면 f(n)이 수행 시간을 결정함
- g(n)과 f(n)이 같은 차수면 g(n)에 log n을 곱한 것이 수행 시간이다
관련 공식)
예시)
참고)
T(n) ≤ aT(~~) 이면 O()로 표현
T(n) ≥ aT(~~) 이면 Ω()로 표현
'CS > 알고릴라' 카테고리의 다른 글
| 5장. 되추적 (Back-tracking) (0) | 2023.05.16 |
|---|---|
| 4장. 탐욕적인 접근방법(Greedy Algorithm) (2) (0) | 2023.05.01 |
| 4장. 탐욕적인 접근방법 (Greedy Algorithm) (1) (0) | 2023.04.17 |
| 3장. 동적 계획법 (Dynamic Programming) (1) | 2023.04.13 |
| 1장. 알고리즘: 효율, 분석, 그리고 차수 (0) | 2023.03.06 |
