[알고리즘] 순환

Hyunwoo·2025년 1월 18일

알고리즘

목록 보기

3/9

순환

순환이란?

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

장점
순환은 어떤 문제에서는 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
단점
-일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다.
(물론 순환이 반복보다 빠른 예제도 존재하긴 한다.)
-순환 호출시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억되어야 하므로 여분의 기억장소가 필요하다.

순환 시에는 반드시 순환 호출을 멈추는 문장이 필요하다. 만약 멈추는 문장이 없다면 무한히 순환 호출을 하게 되어 결국 오류를 발생시키기 때문이다.

순환 호출의 내부

하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일
복귀주소가 시스템 스택에 할당되고, 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당 받음
호출된 함수의 코드의 시작 위치로 점프(만약, 호출된 함수가 자기 자신이라면 자기 자신의 시작 주소로 점프)
호출된 함수가 끝나게 되면 시스템 스택에 복귀 주소를 호출하여 호출한 함수로 되돌아가게 됨

순환의 원리

분할 정복(divide and conquer): 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법

순환 예제

팩토리얼 계산

int factorial(int n)
{
	if (n <= 1) return(1);
    else return (n * factorial(n - 1));
}

거듭제곱값 계산

지수법칙을 이용하여 효율적으로 작성하였다.

위의 지수의 덧셈 성질을 이용하여

2^8 = 2^4 + 2^4
2^9 = 2^4 + 2^4 + 2^1

a^n = a^(n / 2) + a^(n / 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);
}

거듭제곱값을 계산하는 프로그램은 반복적인 방법보다 순환적인 방법으로 구현하는 것이 효과적이다. 입력 값이 알고리즘의 반복마다 반씩 줄기 때문에 시간복잡도는 O(log n)이다.

피보나치 수열의 계산

int fib(int n)
{
	if(n == 0) return 0;
    if(n == 1) return 1;
    return (fib(n - 1) + fib(n - 2));
}

피보나치 수열은 정의 자체가 순환적으로 되어있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 위 코드는 매우 단순하고 이해하기 쉽지만 매우 비효율적이다.
이유는 중간에 이미 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다.
시간 복잡도도 O(2^n)으로 실질적으로 피보나치 수열은 순환적인 방법으로 계산하는 것이 불가능하다. 따라서 반복적인 방법으로 계산해야 한다.

하노이탑 문제

void hanoi(int n, char from, char tmp, char to)
{
	if(n == 1)
    {
    	printf("원판 1을 %c에서 %c로 옮긴다.\n", from, to);
    }
    else
    {
    	hanoi(n - 1, from, to, tmp);
        printf("원판 %d를 %c에서 %c로 옮긴다.\n", n, from, to);
        hanoi(n - 1, tmp, from, to);
    }
}

int main()
{
	hanoi(4, 'A', 'B', 'C');
    
    return 0;
}