대표적인분할정복알고리즘 4 장. 재귀호출 학습목표 재귀호출이라는개념자체를명확히이해한다. 재귀호출함수의내부구조를이해한다. 재귀호출에내재하는효율성에대해이해한다. 1
Section 01 상징적의미 - 도미노 도미노 2
도미노 100 번째것이반드시쓰러진다는사실을증명하라. 수학적귀납법 (Mathematical Induction) 처음것 (K=1) 은반드시쓰러진다. K 번째막대가쓰러지면 (K+1) 번째막대도반드시쓰러진다. 재귀적알고리즘 (Recursive Algorithm) 수학적귀납법의순서를역순으로적용 99 번째것이쓰러지면인접한 100 번째것이쓰러지니, 99 번째것이반드시쓰러진다는사실을증명하라. 98 번째것이쓰러지면인접한 99 번째것이쓰러지니, 98 번째것이반드시쓰러진다는사실을증명하라. 처음것이반드시쓰러진다는사실을증명하라. 그건직접밀었기때문에반드시쓰러진다. 3
재귀호출분할정복 문제의크기 N 큰문제를작은문제로환원작은문제역시큰문제와유사함 재귀호출 Self Call Boomerang 아주작은문제 직접해결할정도로작아짐 베이스케이스 ( 디제너릿케이스 ) 4
BinarySearch(SearchRange) Section 02 이진탐색 - 이진탐색 괄호안은탐색범위 { if (One Page) 베이스케이스 Scan Until Found; else { Unfold the Middle Page; 가운데펼침 Determine Which Half; 전반부, 후반부판단 if First Half BinarySearch(First Half); 전반부재귀호출 else BinarySearch(Second Half); 후반부재귀호출 문제크기감소 : N, N/2, N/4,., 1 재귀호출은반드시베이스케이스에도달해야함 5
Section 03 재귀적팩토리얼 팩토리얼연산 n! = n (n-1) (n-2)... 1 ( 단, 1! = 0! = 1) int Factorial(int n) { if (n = = 1) return 1; else return(n * Factorial(n-1)); [ 그림 4-3] 재귀호출의들어가기와나오기 6
int Factorial(int n) { if (n = = 1) return 1; else return(n * Factorial(n-1)); 활성화레코드 Stack Expands Parm. n = 4 Ret. Val =? Parm. n = 3 Ret. Val =? Parm. n = 2 Ret. Val =? Parm. n = 1 Ret. Val =? Parm. n = 4 Ret. Val = 4 * 6 Parm. n = 3 Ret. Val = 3 * 2 Parm. n = 2 Ret. Val = 2 * 1 Parm. n = 1 Ret. Val = 1 Stack Shrinks [ 그림 4-2] 재귀호출에따른활성화레코드 7
Section 04 문자열뒤집기 문자열뒤집기 I void Reverse(char S[ ], int Size) { if (Size = = 0) return; 호출함수로되돌아감 else { printf("%c", S[Size-1]); 마지막문자를쓰기 Reverse(S, Size-1); 재귀호출 마지막문자를먼저제거 문자열 PET 에대해서추적해보라. 8
void Reverse(char S[ ], int First, int Last) { if (First > Last) return; else { printf("%c", S[First]); Reverse(S, First+1, Last); 문자열뒤집기 II 첫문자를먼저제거 위코드는제대로돌지않음 어떻게고쳐야하는가 9
문자열뒤집기 II void Reverse(char S[ ], int First, int Last) { if (First > Last) return; else { printf("%c", S[First]); Reverse(S, First+1, Last); First = 0 Last = 3 Reverse(S, 1, 3) First = 1 Last = 3 Reverse(S, 2, 3) First = 2 Last = 3 Reverse(S, 3, 3) First = 3 Last = 3 Reverse(S, 4, 3) First = 4 Last = 3 First = 0 Last = 3 printf(s[0]) First = 1 Last = 3 printf(s[1]) First = 2 Last = 3 printf(s[2]) First = 3 Last = 3 printf(s[3]) First = 4 Fast = 3 return [ 그림 4-4] 문자열뒤집기의활성화레코드 10
Section 05 K번째작은수찾기 K 번째작은수찾기 10, 7, 2, 8, 3, 1, 9, 6 이라는숫자중에서세번째작은수는 3 재귀적방법론 10, 7, 2, 8 과 3, 1, 9, 6으로분할 10, 7, 2, 8 중세번째작은수는 8 3, 1, 9, 6 중세번째작은수는 6 작은문제의해결책이큰문제의해결책으로이어지지않는다. 11
파티션 1) 임의로피벗설정 2) 다운포인터와업포인터설정 3) 다운은피벗보다작거나같은것, 업은피벗보다크거나같은것찾음 4) 스와핑 10 7 2 8 3 1 9 6 10 7 2 8 3 1 9 6 10 7 2 8 3 1 9 6 1 7 2 8 3 10 9 6 5) 포인터가일치하거나교차할때까지 3),4) 를반복 1 7 2 8 3 10 9 6 1 3 2 8 7 10 9 6 1 3 2 8 7 10 9 6 6) 업포인터위치에있는숫자와피벗을스와핑 p 1 3 2 6 7 10 9 8 [ 그림 3-10] 가비지 12
파티션파티션 피벗보다작은것은왼쪽으로, 피벗보다큰것은오른쪽으로전체데이터가정렬된상태는아님모든데이터가정렬되어도피벗위치는불변 K가 4라면네번째작은수를이미찾은것임 p 1 3 2 6 7 10 9 8 세번째작은수찾기 분할된왼쪽에대해서다시파티션을가함 ( 결과 p = 2) 1 3 2 p 1 2 3 분할된오른쪽에대해서다시파티션을가함 : self-swap ( 결과 p = 3) p 3 13
Section 06 피보나치수열 피보나치수열 F(n) = F(n-1) + F(n-2) ( 단, F(0) = 0, F(1) = 1) int Fibonacci(int n) { if (n < 2) 베이스케이스 return 1; F(0) = F(1) = 1 else return (Fibonacci(n-1) + Fibonacci(n-2)); 재귀호출 [ 그림 4-5] 피보나치수열의재귀호출 14
Step 1 Section 07 재귀함수의작성 재귀함수작성 더작은문제로표시할수있는지시도 문제크기를하나씩줄이는방법 반으로줄이는방법 다른여러개의작은문제의조합으로표시하는방법문제크기파라미터 N 을확인 Step 2 문제를직접풀수있는것이어떤경우인지베이스케이스확인 Step 3 N 이줄어서반드시베이스케이스를만나는지확인 N 이양수인지음수인지, 짝수인지홀수인지, 또는부동소수인지정수인지모든경우에대해모두검증. Step 4 베이스케이스와베이스케이스가아닌경우를나누어서코드를작성 15
Section 08 재귀호출의효율성 재귀호출의효율성활성화레코드의비효율 공간적비효율 ( 저장공간 ) 시간적비효율 ( 저장, 복원에걸리는시간 ) 가능하다면반복문으로대치하는것이유리 16
재귀호출의반복문변환 int Factorial(int n) 팩토리얼 { int product = 1; 곱셈의결과값을초기화 for (int i = 1; i <= n; i++) 1부터 n까지 product *= i; 계속곱해서저장 return product; 결과를리턴 void Reverse(char S[ ], int Size) 문자열뒤집기 { while (Size > 0) 한글자라도남아있을때까지 { printf("%c", S[Size-1]); 일단마지막문자를찍고 --Size; 문자열마지막을한칸앞으로 int Fibonacci(int n) 피보나치수열 { int A[Max]; 배열크기를 n보다크게잡음 F[0] = 1; F[1] = 1; 수열의처음두숫자초기화 for (int i = 2; i <= n; i++) F[2] 부터 n까지 F[i] = F[i-2] + F[i-1]; 앞에서뒤로채워나감 return (F[i]); 배열의마지막요소를돌려줌 17
Section 09 꼬리재귀 꼬리재귀재귀호출명령이함수마지막에위치 되돌아올때할일이없는재귀호출새로운활성화레코드공간을만들지않고이전공간재사용 return (N * Factorial(N-1)); 는꼬리재귀아님 Factorial(N-1) 결과가리턴되면거기에 N을곱하는일이남아있음. 꼬리재귀를사용한팩토리얼 int Factorial(int n, int a) { if (n = = 0) return a; a에결과값이축적됨 else return Factorial(n-1, n*a); 꼬리재귀 18
Thank you 19