CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.

Presentation on theme: "CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005."— Presentation transcript:

1 CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005

2 순환(recursion)이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
정의자체가 순환적으로 되어 있는 경우에 적합한 방법 (예제) 팩토리얼 값 구하기 피보나치 수열 하노이의 탑 이진탐색

3 팩토리얼 프로그래밍 #1 팩토리얼의 정의 팩토리얼 프로그래밍 #1: 위의 정의대로 구현
(n-1)! 팩토리얼을 구하는 서브 함수 factorial_n_1를 따로 제작 int factorial(int n) { if( n == 1 ) return(1); else return (n * factorial_n_1(n-1) ); }

4 팩토리얼 프로그래밍 #2 팩토리얼 프로그래밍 #2:
(n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산(순환 호출) int factorial(int n) { if( n == 1 ) return(1); else return (n * factorial(n-1) ); } 3!은? 3!를 계산하려면 3! = 3*2! 2!를 계산하려면 2! = 2*1! 1!은 1 3!는? 2!는? 1!는? 6 2 1

5 순환호출순서 개념설명: 순환호출 팩토리얼 함수의 호출 순서 factorial(5) = 5 * factorial(4)
= 5 * 4 * 3 * 2 * 1 = 120 factorial(3) { if( 3 == 1 ) return 1;     else return (3 * factorial(3-1) ); } ④ ① factorial(2) { if( 2 == 1 ) return 1;     else return (2 * factorial(2-1) ); } ③ ② factorial(1) { if( 1 == 1 ) return 1; ..... }

6 순환 호출의 내부적인 구현 p.46 그림 2-3 factorial(3)의 호출 중의 시스템 스택의 변화

7 시스템 스택을 다 사용하여 결국 에러 발생 (Stack Overflow)
순환 알고리즘의 구조 가상실습: 팩토리얼 순환 알고리즘은 다음과 같은 부분들을 포함한다. 순환 호출을 하는 부분 순환 호출을 멈추는 부분 else return n * factorial(n-1); int factorial(int n) { 순환을 멈추는 부분 순환호출을 하는 부분 } if( n == 1 ) return 1 만약 순환 호출을 멈추는 부분이 없다면?. 시스템 오류가 발생할 때까지 무한정 호출하게 된다. 시스템 스택을 다 사용하여 결국 에러 발생 (Stack Overflow)

8 순환 <-> 반복 컴퓨터에서의 되풀이 대부분의 순환은 반복으로 바꾸어 작성할 수 있다. 순환 반복
순환(recursion): 순환 호출 이용 반복(iteration): for나 while을 이용한 반복 대부분의 순환은 반복으로 바꾸어 작성할 수 있다. 순환 순환적인 문제에서는 자연스러운 방법 함수 호출의 오버헤드 반복 수행속도가 빠름 순환적인 문제에 대해서는 프로그램 작성이 아주 어려울 수 있음 1!=1 2!=2 3!=6 … 3!를 계산하려면 3! = 3*2! 2!를 2! = 2*1! 1!은 1 2!는? 1!는? 1 2

9 팩토리얼의 반복적 구현 int factorial_iter(int n) { int k, v=1;
for(k=n; k>0; k--) v = v*k; return(v); }

10 순환의 원리 p.50 [그림2-7] [그림2-8] 알고리즘 정의가 순환적으로 되어있는 경우에 유리
해결된 부분 + 남아있는 부분 [그림2-8] 최대 값을 구하는 순환호출 알고리즘 정의가 순환적으로 되어있는 경우에 유리 (예) 팩토리얼 함수, 피보나치 수열, 이항계수 계산, 각종 이진트리 알고리즘, 이진탐색, 하노이 탑 문제 순환은 강력한 프로그래밍 도구!!

11 순환 알고리즘의 성능 n번의 순환 호출 : O(n)
int factorial(int n) { if( n == 1 ) return(1); else return (n * factorial(n-1) ); } int factorial_iter(int n) { int k, v=1; for(k=n; k>0; k--) v = v*k; return(v); } 순환 반복 n번의 순환 호출 : O(n) 하지만 함수 호출의 경우 여분의 기억공간이 더 필요, 파라미터를 스택에 저장하는 등의 사전작업 필요 for를 이용하여 n번 반복 : O(n)

12 거듭제곱 프로그래밍 #1 순환적인 방법이 반복적인 방법보다 더 효율적인 예 숫자 x의 n제곱값을 구하는 문제: xn
double slow_power(double x, int n) { int i; double r = 1.0; for(i=0; i<n; i++) r = r * x; return(r); }

13 거들제곱값 프로그래밍 #2 순환적인 방법 power(x, n) if n=0 then return 1; else if n이 짝수
then return power(x2,n/2); else if n이 홀수 then return x*power(x2, (n-1)/2); double power(double x, int n) { if( n==0 ) return 1; else if ( (n%2)==0 ) return power(x*x, n/2); else return x*power(x*x, (n-1)/2); } // 생능출판장테스트.cpp : 콘솔응용프로그램에대한진입점을정의합니다. // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <time.h> double slow_power(double x, int n) { int i; double r = 1.0; for(i=0; i<n; i++) r = r * x; return(r); } double power(double x, int n) if( n==0 ) return 1; else if ( (n%2)==0 ) return power(x*x, n/2); else return x*power(x*x, (n-1)/2); int _tmain(int argc, _TCHAR* argv[]) clock_t start, finish; double duration; start = clock(); // 수행시간을측정하고하는코드.... double r = slow_power(2,500); printf("%lf\n", r); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); double r2 = power(2,500); printf("%lf\n", r2); return 0;

14 거들제곱값 프로그래밍 분석 순환적인 방법의 시간 복잡도 반복적인 방법과 순환적인 방법의 비교
만약 n이 2의 제곱이라고 가정하면 다음과 같이 문제의 크기가 줄어든다. 반복적인 방법과 순환적인 방법의 비교 반복적인 함수 slow_power 순환적인 함수 power 시간복잡도 O(n) O(logn) 실제수행속도 7.17초 0.47초

15 피보나치 수열의 계산 #1 순환 호출을 사용하면 비효율적인 예 피보나치 수열 순환적인 구현
0,1,1,2,3,5,8,13,21,… 순환적인 구현 // 생능출판장테스트.cpp : 콘솔응용프로그램에대한진입점을정의합니다. // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <time.h> int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); } int fib_iter(int n) if( n < 2 ) return n; else { int i, tmp, current=1, last=0; for(i=2;i<=n;i++){ tmp = current; current += last; last = tmp; return current; int _tmain(int argc, _TCHAR* argv[]) clock_t start, finish; double duration; puts("순환적방법\n"); start = clock(); // 수행시간을측정하고하는코드.... printf("%d\n", fib(30)); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); puts("반복적방법\n"); printf("%d\n", fib_iter(30)); return 0; int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); }

16 피보나치 수열의 계산 #2 순환 호출을 사용했을 경우의 비효율성 fib(6) fib(4) fib(5) fib(2) fib(3)
같은 항이 중복해서 계산됨 예를 들어 fib(6)을 호출하게 되면 fib(3)이 4번이나 중복되어서 계산됨 이러한 현상은 n이 커지면 더 심해짐 fib(6) fib(4) fib(5) // 생능출판장테스트.cpp : 콘솔응용프로그램에대한진입점을정의합니다. // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <time.h> int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); } int fib_iter(int n) if( n < 2 ) return n; else { int i, tmp, current=1, last=0; for(i=2;i<=n;i++){ tmp = current; current += last; last = tmp; return current; int _tmain(int argc, _TCHAR* argv[]) clock_t start, finish; double duration; puts("순환적방법\n"); start = clock(); // 수행시간을측정하고하는코드.... printf("%d\n", fib(30)); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); puts("반복적방법\n"); printf("%d\n", fib_iter(30)); return 0; fib(2) fib(3) fib(3) fib(4) fib(2) fib(3) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3)

17 피보나치 수열의 반복구현 반복 구조를 사용한 구현 fib_iter(int n) { if( n < 2 ) return n;
else { int i, tmp, current=1, last=0; for(i=2;i<=n;i++){ tmp = current; current += last; last = tmp; } return current; // 생능출판장테스트.cpp : 콘솔응용프로그램에대한진입점을정의합니다. // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <time.h> int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); } int fib_iter(int n) if( n < 2 ) return n; else { int i, tmp, current=1, last=0; for(i=2;i<=n;i++){ tmp = current; current += last; last = tmp; return current; int _tmain(int argc, _TCHAR* argv[]) clock_t start, finish; double duration; puts("순환적방법\n"); start = clock(); // 수행시간을측정하고하는코드.... printf("%d\n", fib(30)); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); puts("반복적방법\n"); printf("%d\n", fib_iter(30)); return 0;

18 하노이 탑 문제 문제는 막대 A에 쌓여있는 원판 n개를 막대 C로 옮기는 것이다. 단 다음의 조건을 지켜야 한다. A B C
한 번에 하나의 원판만 이동할 수 있다 맨 위에 있는 원판만 이동할 수 있다 크기가 작은 원판위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다. A B C

19 n=3인 경우의 해답 A B C A B C

20 일반적인 경우에는? C를 임시버퍼로 사용하여 A에 쌓여있는 n-1개의 원판을 B로 옮긴다. A의 가장 큰 원판을 C로 옮긴다.
A를 임시버퍼로 사용하여 B에 쌓여있는 n-1개의 원판을 C로 옮긴다.

21 남아있는 문제는? 자 그러면 어떻게 n-1개의 원판을 A에서 B로, 또 B에서 C로 이동하는가?
(힌트) 우리의 원래 문제가 n개의 원판을 A에서 C로 옮기는 것임을 기억하라. 따라서 지금 작성하고 있는 함수를 파라미터를 n-1로 바꾸어 순환호출하면 된다. // 막대 from에 쌓여있는 n개의 원판을 막대 tmp를 사용하여 막대 to로 // 옮긴다. void hanoi_tower(int n, char from, char tmp, char to) {    if (n==1){        from에서 to로 원판을 옮긴다.    }    else{        hanoi_tower(n-1, from, to, tmp);        from에 있는 한 개의 원판을 to로 옮긴다.        hanoi_tower(n-1, tmp, from, to); }

22 하노이탑 최종 프로그램 가상실습: 하노이탑 n-1개의 원판을 A에서 B로 옮기고 n번째 원판을 A에서 C로 옮긴 다음, n-1개의 원판을 B에서 C로 옮기면 된다. #include <stdio.h> void hanoi_tower(int n, char from, char tmp, char to) { if( n==1 ) printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to); else { hanoi_tower(n-1, from, to, tmp); printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to); hanoi_tower(n-1, tmp, from, to); } main() hanoi_tower(4, 'A', 'B', 'C'); void hanoi_tower(int n, char from, char tmp, char to) { if( n==1 ) printf("원판1을%c 에서%c으로옮긴다.\n",from,to); else { hanoi_tower(n-1, from, to, tmp); printf("원판%d을%c에서%c으로옮긴다.\n",n, from, to); hanoi_tower(n-1, tmp, from, to); } int _tmain(int argc, _TCHAR* argv[]) hanoi_tower(4,'a','b','c');

23 #include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) { if( n==1 ) printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to); else { hanoi_tower(n-1, from, to, tmp); printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to); hanoi_tower(n-1, tmp, from, to); } hanoi_tower(3,a,b,c) hanoi_tower(2,a,c,b) hanoi_tower(1,a,b,c) 원판 1을 a에서 c로 옮긴다 원판2를 a에서 b로 옮긴다 hanoi_tower(1,c,a,b) 원판 1을 c에서 b로 옮긴다. 원판3을 a에서 c로 옮긴다 hanoi_tower(2,b,a,c) hanoi_tower(1,b,c,a) 원판 1을 b에서 a로 옮긴다 원판2를 b에서 c로 옮긴다 원판 1을 a에서 c로 옮긴다.