어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.
팩토리얼 문제를 풀며 순환에 대해 알아본다.
팩토리얼 n!을 다음과 같이 정의하는데 다시 (n-1)!이 사용된다. 이러한 정의를 순환적이라고 한다.
위의 정의에 따라 n!을 구하는 함수인 factorial(n)을 만든다.
int factorial(int n)
{
if (n <= 1) return(1);
else return(n * factorial(n - 1));
}입력을 3이라고 하면 실행 과정은 다음과 같다.
factorial(3) = 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1
= 3 * 2
= 6
- 순환 호출의 내부적인 구현
프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 따라서 복귀주소를 시스템 스택에 저장하고 호출되는 함수를 위한 매개변수, 지역변수를 스택으로부터 할당받는다. 함수를 위한 시스템 스택에서의 공간을 활성 레코드라고 한다.
이러한 준비가 끝난 후 호출된 함수의 시작 위치로 점프하여 수행을 시작한다. 호출된 함수가 끝나면 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 되돌아간다. main()에서 factorial()을 호출하였을 때의 시스템 스택은 아래 그림과 같다.
)
)
순환호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들은 계속 쌓인다.
C와 같은 현대적인 프로그래밍 언어에서는 순환을 지원하지만 COBOL과 같은 고전적인 언어는 지역변수가 없거나 있더라도 정적으로 할당되기 때문에 순환이 불가능하다. 즉 함수 호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수 없어 순환 호출이 불가능하다.
- 순환 알고리즘의 구조
만약 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 호출되다가 결국 오류를 내면서 멈출 것이다. 따라서 반드시 순환 호출에는 순환 호출을 멈추는 문장이 포함되어야 한다.
프로그래밍 언어에서 되풀이하는 방법에는 반복과 순환이 있다.
1.반복
반복이란 for나 while 등의 반복구조로 되풀이 하는 방법이다.
반복은 제어하는 변수를 사용해 일정횟수동안 반복할 수 있고 어떤 조건이 만족될 때까지 반복시킬 수도 있다.
2.순환
순환은 주어진 문제를 해결하기 위해 자신을 다시 호출하여 작업을 수행하는 방식이다.
반복과 순환은 문제 해결 능력이 같고 많은 경우에 순환 알고리즘을 반복 버전으로 또는 그 반대로 바꿔 쓸 수 있다.
순환 호출이 끝에서 이루어지는 순환을 꼬리 순환이라고 하는데 이를 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있다.
- 장점
어떤 문제에서는 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
- 단점
일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 실행 속도 면에서는 떨어진다.
위에서 사용한 팩토리얼 함수를 반복 구조를 사용하면 아래와 같다.
int factorial_iter(int n)
{
int i, result = 1;
for(i=1; i<=n; i++)
result = result * i;
return(result);
}
- 순환의 원리
순환은 문제의 일부를 해결한 다음 나머지 문제에 대해 순환 호출한다.
즉 순환은 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법인 분할정복을 사용한다.여기서 중요한 것은 순환호출이 일어날 때마다 문제의 크기가 작아진다는 것이다.
팩토리얼 문제에서 순환의 원리를 적용하면 다음과 같다.
factorial(int n)
{
if(n <= 1) return 1;
else return (n * factorial(n-1) );
}else구문에서 n*는 해결된 부분이고 factorial(n-1)은 남아있는 부분이다.
- 거듭제곱값 계산
팩토리얼 계산에는 반복적인 방법이 순환적인 방법보다 빠르다.
반복적인 방법보다 순환적인 방법이 빠른 예제로 거듭제곱값 계산을 다룬다.
- n 제곱거듭값인 $ x^n $을 반복적인 방법으로 구하는 코드
double slow_power(double x, int n)
{
int i;
double result = 1.0;
for (i = 0; i < n; i++)
{
result = result * x;
}
return 0;
}이 경우 한 번의 루프마다 한 번의 곱셈이 필요하고 루프의 개수는 n이므로 시간 복잡도는 O(n)이다.
- n 제곱거듭값인 $ x^n $을 순환적인 방법으로 구하는 코드
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);
}
}알고리즘은 다음과 같다.
power(x, n):
if n==0
then return 1;
else if n이 짝수
then return power(x^2,n/2);
else if n이 홀수
then return x*power(x^2, (n-1)/2);만약 n이 100이라면 다음과 같이 문제의 크기가 줄어든다.
100 → 50 → 25 → 12 → 6 → 3 → 1
따라서 시간 복잡도는 O($log$n)과 같다.
- 피보나치 수열의 계산
먼저 피보나치 수열이란 아래와 같이 정의되는 수열이다.
피보나치 수열은 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다. 예를 들면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
- 피보나치 수열을 순환적인 방법으로 구하는 코드
int fib(int n)
{
if( n== 0 ) return 0;
if( n== 1 ) return 1;
return (fib(n-1) + fib(n-2));
}이 코드는 가독성이 좋고 단순하지만 매우 비효율적이다.
인자로 fib(6)으로 호출하면 fib(4)는 두 번 계산되고 fib(3)은 3번 계산된다. 즉 fib(6)을 계산하기 위해 fib()함수가 25번이나 호출된다.
호출되는 fib()함수는 다음과 같다.
fib(6) * //1번 호출
fib(5) * //1번 호출
fib(4) ** //2번 호출
fib(3) *** //3번 호출
fib(2) ***** //5번 호출
fib(1) ******** //8번 호출즉 이 알고리즘의 시간 복잡도는 O($2^n$)이다. 이 경우에는 순환을 사용하지 않고 반복구조를 이용하는 것이 더 좋다.
2. 피보나치 수열을 반복적인 방법으로 구하는 코드
int fib_iter(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
int pp = 0;
int p = 1;
int result = 0 ;
for (int i = 2; i <= n; i++){
result = p + pp;
pp = p;
p = result;
}
return result;
}반복구조를 이용한 알고리즘의 시간 복잡도는 for문을 사용하였기 때문에 O(n)이다.
- 하노이 탑 문제
A에 쌓여있는 원판을 막대 C로 옮기는 문제이다. 단 아래의 조건을 지켜야한다.
- 한 번에 하나의 원판만 이동할 수 있다.
- 맨 위에 있는 원판만 이동할 수 있다.
- 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
- 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.
이 문제의 알고리즘은 아래와 같다.
void hanoi_tower(int n, char from, char tmp, char to)
{
if ( n== 1)
{
from에 있는 한 개의 원판을 to로 옮긴다.
}
else
{
1. from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮긴다.
2. from에 있는 한 개의 원판을 to로 옮긴다.
3. tmp의 원판들을 to로 옮긴다.
}
}1번과 3번은 막대의 위치만 달라지고 원래의 문제의 축소된 형태라는 것을 알 수 있다.
따라서 순환 알고리즘을 통해 이 문제를 풀 수 있다.
하노이 탑 문제를 순환적인 방법으로 구하는 코드
#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);
}
}
int main()
{
hanoi_tower(4, 'A', 'B', 'C');
return 0;
}하노이 탑 문제를 푸는 코드의 시간복잡도는 O($2^n$)가 된다.
결과
- 반복적인 형태로 바꾸기 어려운 순환
//1
return n * factorial(n - 1);
//2
return facotrial(n-1) * n;1처럼 순환 호출이 순환 함수의 맨 끝에서 이루어지는 형태의 순환을 꼬리 순환이라고 한다. 이 경우 알고리즘이 쉽게 반복적인 형태로 변환이 가능하다.
2와 같이 머리 순환인 경우 하노이의 탑 문제처럼 여러 군데에서 자기 자신을 호출하는 경우 쉽게 바꿀 수 없다. 만약 동일한 알고리즘을 꼬리 순환과 머리 순환 양쪽으로 모두 표현할 수 있다면 꼬리 순환으로 작성해야 한다.
관련 문제
백준9095: 1,2,3 더하기
'알고리즘 > 개념' 카테고리의 다른 글
| 스택 (1) | 2023.01.13 |
|---|---|
| 알고리즘과 자료구조 (0) | 2023.01.13 |
