2. 순환
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로 옮긴다.