[C언어로 쉽게 풀어쓴 자료구조] 02장 순환_개념정리

1. 순환

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

 

1. 순환의 예

ex) 팩토리얼 계산

팩토리얼

🟡 코드

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

- 매개변수 n을 입력받아서 n과 n-1를 매개변수로 받는 함수의 계산 값을 곱해준다.

- 예를 들어 n =3이 입력이되면

ⓐ 3 * factorial(2)

ⓑ 2 * factorial(1)

ⓒ 1

이므로 3 * 2 * 1 = 6 이 결과값으로 나오는 것이다.

 

2. 순환 호출의 내부적인 구현

- 복귀 주소가 시스템 스택에 저장된다.

- 호출되는 함수를 위한 매개변수와 지역변수를 스택으로부터 할당된다.(활성 레코드)

- 호출된 함수가 끝나면 시스템 스택에 복귀주소를 추출하여 호출한 함수로 되돌아 가게된다.

* 순환 호출이 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.

 

 

3. 순환 알고리즘의 구조

- 순환 알고리즘은 자기 자신을 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어있다.

- 기저조건, 즉 멈추는 부분이 없으면 무한적으로 호출하게 되므로 오류가 날 것이다.

 

 

4. 순환 <-> 반복

- 기본적으로 반복과 순환은 문제 해결 능력이 같으며, 많은 경우엔 순환 알고리즘을 반복 버전으로, 반복 알고리즘을 순환 버전으로 바꾸어 쓸 수 있다. 

- 특히 순환 호출이 끝에서 이루어지는 순환을 꼬리 순환이라고 하는데, 이를 반복 알고리즘으로 쉽게 바꿀 수 있다.

 

- 앞선 팩토리얼 순환을 반복으로 바꿀 수 있다

int factorial_iter(int n)
{
    int i, result = 1;
    for(int i=1; i<=n; i++)
        result = result * i;
    return(result);
}

 

5. 순환의 원리

- 문제의 일부를 해결한 다음, 나머지 문제에 대해 순환 호출하는 것에 유의하자.

- 문제의 크기가 순환이 진행될수록 작아진다.

 

6. 순환 알고리즘의 성능

- 위에서 다루었던 팩토리얼의 반복함수는 for을 사용해서 n을 반복하고 순환함수는 n번호출하므로 O(n) 걸린다.

- 순환 알고리즘은 이해하기는 쉽고, 프로그래밍 하기 쉽지만 수행시간과 기억 공간의 사용에서 비효율적일 수 있다.

 

QUIZ 답

01  A = 22

02 

int sub_iter(int n) {
	int ans = 0;
	for (int i = n; i > 0; i -= 3) {
		ans += i;
	}
	return ans;
}

 

2. 거듭제곱값 계산

1. 거듭제곱 함수 만들기

1) 반복 함수

double slow_power(double x, int n) {
	int i;
	double result = 1.0;
	for (int i = 0; i < n; i++){
		result = result *x;
	}
	return(result);
}

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(logn)

- 이유 : n을 2의 거듭제곱인 2^k 라고 할때, 순환 호출를 한번 할 때마다 n의 크기가 절반씩 줄어든다.

따라서 순환호출은 k번 일어나기 때문에 양변에 로그를 취하면 k = log n/ log 2 다 

한 번의 순환 호출이 일어날 때마다 약 1번의 곱셈과 나눗셈이 일어나므로 전체 연산의 개수는 k에 비례할 것이고 

따라서 시간복잡도는 O(logn)이 된다.

 

3. 피보나치 수열의 계산

- 순환 호출 코드

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

위 코드는 단순하고 이해하기 쉽지만 매우 비효율적이다. 

왜냐하면 호출이 중복되어 실행되기 때문이다.(시간복잡도 : O(2^N))

따라서 반복문으로 함수를 작성하는 것이 좋다.

 

4. 하노이탑 

이미지 출처 : '하노이의 탑' 이해하기 - Parkito's on the way (shoark7.github.io)

1) 하노이탑 조건 

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

ⓑ 맨 위에 있는 원판만 이동할 수 있따.

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

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

 

2) 방법

① N개의 원판이 A에 쌓여있는 경우, 먼저 위에 쌓여있는 N-1 개의 원판을 B로 옮긴 다

② A의 제일 밑에 있는 원판을 C로 옮긴다.

③ 이어서 B에 있던 N-1 개의 원판을 C로 옮긴다. 

* 이 때 1번과 3번은 똑같은 형태이기에 순환 호출이 가능하다.

 

- 코드 

* n은 원판의 개수, from 은 A기둥, tmp는 B기둥, to는 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);
	}
}

 

5. 반복적인 형태로 바꾸기 어려운 순환

- 꼬리 순환은 반복문으로 바꾸기 쉽지만 머리순환이나, 여러군데에서 순환호출을 하는 경우는 바꾸기 쉽지 않다.