자료구조 3(순환 2)

- 피보나치수열

피보나치수열은 앞의 두 개의 숫자를 더해 뒤의 숫자를 만든다.

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$$

일반적인 피보나치수열의 코드를 알아보자

int fibo(int n) {
	
    if(n == 0)
    	return 0;
    else if(n == 1)
    	return 1;
    return (fibo(n - 1) + fobo(n - 2));
    
}

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

위의 그림처럼 숫가자 작은 경우에도 똑같은 함수가 여러 번 반복되기 때문에 숫자가 점점 더 커지고 깊이가 점점 깊어질수록 심해지기 때문에 상당히 비효율적이라고 말할 수 있다. 그리고 6이라는 숫자를 구하기 위해서 함수가 25번 호출되었고 이 숫자가 커지면 커질수록 숫자가 기하급수적으로 늘어나기 때문에 순환 호출을 사용하여 피보나치수열을 계산하는 것은 굉장히 비효율적이라고 말할 수 있다.

간단히 시간 복잡도를 계산해보면

$$T(n) = T(n-1) + T(n-2) + ... $$

이 수식을 빅오표기법으로 나타낸다면

$$O(2^n)$$

이다. 따라서 이 경우에는 순환 알고리즘을 사용하기보다는 반복 구조를 이용하여 프로그램을 계산하면 가장 좋은 결과를 얻을 수 있다.

 

int fibo(int n) {
            
    if(n == 0)
    	return 0;
        
    else if(n == 1)
    	return 1;
    
    int first = 0;
    int second = 1;
    int result = 0;
    int i;
    
    for(i = 2; i <= n; i++) {
    	result = fisrt + second;
        first = second;
        second = result;
   	}
    
    return result;
}

언뜻 보기에는 훨씬 복잡해보이지만 시간 복잡도를 생각해본다면 훨씬 효율적인 코드라 할 수 있다.

---

- 하노이탑

순환의 기본적인 예시이다.

---

하노이탑의 조건

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

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

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

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

---

하노이탑의 기본 알고리즘

이 알고리즘으로 의사 코드를 대충 짜 본다면

하노이탑 풀이함수 (원판의 갯수 n, A, B, C) {

    if(n == 1)
    	A->C로 이동
    
    else{
    	A의 n-1개를 B로 이동
        A의 나머지 1개를 C로 이동

	if(B의 갯수가 1개이하일때)	//함수를 다시 호출하면서 n-1 == 1일때 3번째줄의 코드가 실행되므로 필요없음
        	바로 C로 이동후 종료
        
        B의 원판을을 하나만 빼고 A로 이동
    }
}
//전부 옮겨질때까지 반복

로 볼 수 있다. 이 의사 코드를 기반으로 코드를 작성해본다면

void hanoi (int n, char A, char B, char C) {
	if(n == 1)
    	printf("원판1을 %c에서 %c로 이동한다. \n", A, C);
        
    else{
		hanoi(n - 1, A, C, B);	//원판을 B로 우선적으로 옮기기 위해 순서를 바꿔서 호출
        printf("원판 %d를 %c에서 %c로 이동한다. \n", n, A, C);
        hanoi(n - 1, B, A, C);
    }
}

로 작성할 수 있다.

---