2. 순환

Data Structures 2017. 3. 21. 11:06

2.1 순환의 소개



순환

- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법


ex) 팩토리얼 값 구하기, 피보나치 수열, 이항계수, 하노이의 탑



순환적인 팩토리얼 계산 프로그램



 int factorial(int n) {

        if(n <= 1) return 1;

        else return (n * factorial(n-1));

 }


ex) factorial(3) = 3 * factorial(2)

  = 3 * 2 * factorial(1)

  = 3 * 2 * 1

  = 6



* 순환 알고리즘의 구조

1. 자기 자신을 순환적으로 호출하는 부분        ex) if(n <= 1) return 1;

2. 순환 호출을 멈추는 부분                          ex) else return (n * factorial(n-1));



* 순환 vs 반복


순환

반복

 - 순환 호출 이용

 - 순환적인 문제에서 쓰이며 대부분 반복으로 바꾸어 작성 가능

 - 함수 호출의 오버헤드 (수행 속도 느림)

 - for이나 while 등의 반복문 이용

 - 순환적인 문제에서 사용하기 어려움

 - 수행 속도 빠름



* 반복적인 팩토리얼 계산 프로그램


 int factorial_iter(int n) {

        int k, v = 1;

        for(k=n; k>0; k--) {

                v *= k;

        }

        return(v);

 }



2.2 거듭제곱 값 계산



반복적인 거듭제곱 계산 프로그램


 double slow_power(double x, int n) {

        int i;

        double r = 1.0;

        for(i=0; i<n; i++)

                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);

 }


ex) power(2, 10) = power(4, 5)

     = 4 * power(16, 2)

     = 4 * power(256, 1)

     = 4 * 256 * power(65536, 0)

     = 4 * 256 * 1

     = 1024



* 거듭제곱 계산의 반복적인 프로그램과 순환적인 프로그램의 비교


반복적인 함수 slow_power

순환적인 함수 power

 시간 복잡도

O(n)

O(log2n)

실제 수행 속도 

7.17초

0.47초


순환적인 함수가 더 빠르다!



2.3 피보나치 수열의 계산



* 피보나치 수열




순환적인 피보나치 수열 계산 프로그램


 int fib(int n) {

        if(n == 0) return 0;

        else if(n == 1) return 1;

        else return (fib(n-1) + fib(n-2));

 }


같은 항이 중복되서 계산되므로 순호나 호출 사용 시 비효율적이다.


ex) fib(4) = fib(3) + fib(2)

 = fib(2) + fib(1) + fib(1) + fib(0)

 = fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

 = 1 + 0 + 1 + 1 + 0

 = 3


     fib(4)로 호출하면 fib(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;

        }

 } 



2.4 하노이탑 문제



하노이탑


- 막대 A에 쌓여 있는 우너판 3개를 막대 C로 옮기는 문제



* 하노이탑 규칙

1. 한 번에 하나의 원판만 이동할 수 있다.

2. 맨 위에 있는 원판만 이동할 수 있다.

3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.

4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.



* 하노이탑 해결 방법

- 맨 밑에 있는 가장 큰 원판을 1이라고 할 때, 위에 쌓여있는 n-1개의 원판을 B로 옮긴 다음, 제일 밑에 있던 원판을 C에 옮긴다.

- B에 쌓여있던 n-1개의 원판을 C로 옮긴다.

- 해결해야 하는 것은 n개의 원판A에서 C로 옮기는 것!



* 하노이탑 문제 프로그램


 Pseudo code

 void hanoi_tower(int n, char from, char tmp, char to) {

        if(n == 1)

                from에서 to로 원판을 옮긴다.

        else {

                from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮긴다.

                from에 있는 한 개의 원판을 to로 옮긴다.

                tmp의 원판들을 to로 옮긴다.

        }   

 }


 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);

        }   

 }


ex) hanoi_tower(4, 'A', 'B', 'C');


원판 1을 A에서 B로 옮긴다.

------------------------------

원판 2을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다.    //   ①

------------------------------

원판 3을 A에서 B로 옮긴다

원판 1을 C에서 A로 옮긴다.    //   ①

원판 2을 C에서 B로 옮긴다.    //   ②

원판 1을 A에서 B로 옮긴다.

------------------------------

원판 4을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다.    //   ①

원판 2을 B에서 A로 옮긴다.    //   ②

원판 1을 C에서 A로 옮긴다.

원판 3을 B에서 C로 옮긴다.    //   ③

원판 1을 A에서 B로 옮긴다.

원판 2을 A에서 C로 옮긴다.

원판 1을 B에서 C로 옮긴다.