2022. 3. 25. 13:41ㆍMajor`/알고리즘
Recursion?
Recursion이란 동일한 문제를 Reduction을 통해서 사이즈를 줄여가는 방식이다
당연히 재귀를 멈춰줄 "Base Case"가 필요하다
Recursive Algorithms의 "Correctness"는 induction으로 증명하고, "Time Complexity"는 점화식을 통해서 구한다
Divide & Conquer?
Divide & Conquer이란 Recursion을 사용하는 알고리즘 기법이다
- Merge Sort
- Quick Sort
- ....
Recursion은 "input Size"를 줄여가는 방식이다
여기서 단순히 줄여가는 방식은 효율이 그렇지 뛰어나지 않기 때문에 아예 "줄인다"라는 개념을 "잘라버린다"의 개념으로 바꾼 것이 Divide & Conquer이다
Recursion에서는 Reduction된 subproblem들에 대해서 다시 "Recursion"으로 보내듯이
Divde & Conquer에서도 "자른 2개의 subproblem"들에 대해서 Recursion을 보낸다
D&C Pattern
1. Divide
'Several Independent Smaller Instance'
- 일단 큰 전체 문제를 "독립적인 작은 instance"로 나누기
- 동일 문제 & 입력 사이즈 ↓
2. Delegate (Conquer)
'Each Smaller Instance to the Recursion Fairy'
- 1)을 통해서 나눠진 각각의 독립적인 instance를 "재귀의 요정"에게 보내서 처리하도록 한다
- 이 단계에서 각각의 독립적 instance들의 solution이 도출된다 - By Recursion
3. Combine (Merge)
'The soluitons for the smaller instances into the final solution for the given instance'
- 2)에서 도출된 각각의 독립적 instance의 solution을 우리가 원래 풀고자 했던 문제에서 사용함으로써 문제를 해결한다
- 각 solution들을 조합/개선/정리해서 최종 문제 풀기
Example 1) Sum : Iteration / Recursion / D&C
// sum - Iteration
// input : Natural number n
// output : value of (1 + 2 + 3 + .... + n)
----- Pseudo Code -----
sum1(n)
s <- 0
for i <- 1 to n
s <- s + i
return s
----- Java Code -----
static int sum_for(int [] list){
int sum = 0;
for(int n : list){
sum += n;
}
return sum;
}>> O(n)
// sum - Recursion
// input : Natural number n
// output : value of (1 + 2 + 3 + .... + n)
----- Pseudo Code -----
sum2(n)
if n = 1 return 1
return n + sum2(n-1)
----- Java Code -----
static int sum_recursion(int [] list, int N){
if (N == 0){
return 1;
}
else{
return sum_recursion += list[N] + sum_recursion(list, N-1);
}
}T(n) = T(n-1) + O(1)
>> O(n)
// sum - D&C
// input : Natural number n
// output : value of (1 + 2 + 3 + .... + n)
----- Pseudo Code -----
sum3(n)
if n = 1 return 1
if n is even
then return 2 * sum3(n/2) + (n/2)*(n/2)
else // n is odd
then return 2 * sum3((n-1)/2) + ((n-1)/2)*((n-1)/2) + n
----- Java Code -----
static int sum_Divide_Conquer(int N){
if (N == 1){
return 1;
}
if(N%2 == 0){ // list's last value is "even"
return 2*sum_Divide_Conquer(N/2) + (N/2)*(N/2);
}
else{ // list's last value is "odd"
return 2*sum_Divide_Conquer((N-1)/2) + ((N-1)/2)*((N-1)/2) + N;
}
}
>> O(log n)
Example 2) Max : Iteration / D&C
// max - Iteration
// input : array A[0, 1, 2, ...., n-1]
// output : maximum value of input array
----- Pseudo Code -----
max1(A[0, 1, 2, ...., n-1])
m <- A[0]
for i <- 1 to n-1
if A[i] > m then m <- A[i]
return m
----- Java Code -----
static int max_for(int [] list){
int max = list[0];
for(int i=1; i<list.length; i++){
if(list[i] > max){
max = list[i];
}
}
return max;
}>> O(n)
// max - D&C
// input : array A[0, 1, 2, ...., n-1]
// output : maximum value of input array
----- Pseudo Code -----
max2(A[0, 1, 2, ....., n-1])
// "Base Case"
if n = 1 return A[0]
// 1. Divide
mid <- n/2
// 2. Delegate (Conquer)
m1 <- max2(A[0, 1, 2, ...., mid])
m2 <- max2(A[mid + 1, mid + 2, ..... n-1])
// 3. Combine (Merge)
if m1 > m2
return m1
else
return m2
----- Java Code -----
static int max_Divide_Conquer(int [] list, int start, int end){
// start : list's first index
// end : list's last index
if(end - start == 0){
// can't divide anymore
return list[end];
}
// 1. Divide
int mid = (start + end)/2;
// 2. Delegate (Conquer)
int m1 = max_Divide_Conquer(list, 0, mid);
int m2 = max_Divide_Conquer(list, mid + 1, end);
// 3. Combine (Merge)
return Math.max(m1, m2);
}
>> O(n)
- max라는 개념은 최소한 해당 list에서 (n-1)번의 비교를 수행해야 하기 때문에 D&C로 구현해도 시간복잡도가 줄어들지 않는다
Recursion Tree
- 재귀 호출을 수행한 만큼 자식 node가 생기는 구조
"Value of Node"
- 호출된 node상에서 수행한 연산의 개수
>> "Recursive Call"을 제외한 연산의 개수이다
"Sum of the values of all nodes"
- 해당 알고리즘의 running time이다
일반적인 D&C Algorithm의 Recursion Tree (Master Theorem)
L : Tree Depth
>> 제일 밑단의 노드의 value는 1이여야 한다
leaf의 개수
>> leaf의 개수는 곧 leaf의 비용이라고도 할 수 있다
재귀 호출하는 부분 시간 = r * T(n/c)
비재귀 호출하는 부분 시간 = O(f(n))
Case 1)은 f(n)이 꽤 큰 경우이다.
이 경우는 다시 말해서, f(n)이 leaf노드의 비용보다 더 빨리 증가해서 해당 알고리즘은 결국 f(n)에 비례한다는 의미이다
>> tree에서 밑으로 갈수록 level sum이 작아져서 결국 수렴하는 경우이다
"비 재귀호출 부분에서 시간을 많이 쓴다"
Case 2)는 f(n)과 leaf노드의 비용이 동등하게 증가하는 것이다
>> tree에서 밑으로 가도 level sum이 동등한 경우이다
Case 3)는 f(n)이 leaf노드의 비용보다 느리게 증가해서 결국 해당 알고리즘은 leaf노드의 비용에 비례한다
이 말은 다시 말해서 leaf노드의 개수에 비례한다
>> tree에서 밑으로 갈수록 level sum이 증가해서 발산하는 경우이다
"비 재귀호출 부분에서 시간을 더 적게 쓴다"
