#9 [C 자료구조] 알고리즘의 기초 of 기초: 순환 예시

순환 실제 예시

이제는 순환 실전이다! 총 4가지의 종류에 대해서 순환문과 반복문의 차이를 알아보도록 하자.

 

 

거듭제곱 - 순환호출

순환호출st

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));
}

n의 숫자를 계속 2로 쪼개서 순환 호출 중이다.

#시간 복잡도 = O(log₂n) <- 반반씩 쪼개서 찾는 이진 탐색법과 같기 때문

 

반복문st

#include <stdio.h>
double power(double x, int n){
    double result = 1;
    int i = 1;
    for (i=1; i<=n; i++)
    	result = result * x;
    return result;
}

결코 계산! 계산만 하는 중이다.

#시간 복잡도 = O(n) <- n번의 for 문

 

결론: 순환호출이 더 효율적이다.

---

 

 

---

피보나치 - 반복문

순환호출st

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

#시간 복잡도 = O(2ⁿ) <- 한 함수에 두 번씩 재귀호출을 하기 때문!

 

반복문st

int fib(int n){
    int ret = 0;
    if (n < 2)
    	ret = n;
    else {
    	int i = 0, temp = 0;
        int current = 1, last = 0;
        for(i=2; i<=n, i++){
            temp = current;
            current += last;
            last = temp;
        }
        ret = current;
    }
    return ret;
}

#시간 복잡도 = O(n) <- for문의 n

잘 생각해보자, 여기서는 4개의 변수를 이용해 current만을 종합적으로 고려하였다.

 

결론: 반복문이 더 효율적이다.

---

 

 

 

---

하노이의 탑

1번 탑에서 3번탑으로 옮기는 경우를 가정해보자.

 

순환호출st

void move(int from, int to){
    printf("%d --> %d\n", from, to);
}

void hanoi(int n, int from, int by, int to){
    if (n == 1)
        move(from, to);
    else{
        hanoi(n - 1, from, to, by);
        move(from, to);
        hanoi(n - 1, by, from, to);
    }
}

하노이의 탑은 a에서 출발해서 b를 거쳐서 c까지 가는 작업을 반복해야 원판 하나를 옮길 수 있다.

위 방식은 가장 아래의 판을 옮기는 경우의 수 부터 --> 가장 위 판을 옮기는 경우의 수로 점차 호출해나가는 방법이다.

위와 같은 방법을 사용하면 move함수가 몇번 호출되는지 계산해볼 수 있다.

#시간 복잡도 = O(2ⁿ) <- 한 함수에 두개의 함수 호출

 

반복문st

하노이의 탑을 반복문으로 이용하면 변경이 어려울 뿐만아니라 시간 복잡도도 똑같다. 그러므로 생략한다.모르는 게 아님

#시간 복잡도 = O(2ⁿ)

---

 

 

 

---

이진 탐색

특정 수를 찾을 때, 리스트를 정렬해놓고 가운데 숫자와 특정 수의 크기를 비교해 가면서 방향을 정하는 것이다.

술게임 업다운이나 소주 병뚜껑 숫자 맞추기(1~50)를 생각할 때 가운데 숫자로 시작하는 것을 생각하면 쉽다ㅎㅎ

25 -> 업 -> 38 -> 업 -> 44 -> 업 -> 47 -> 앗  술이 들어간다 쭉쭉쭉쭉쭉

 

순환호출st

value[]: 찾고자 하는 숫자가 있는 리스트

left: 가장 왼쪽 key

right: 가장 오른쪽 key

key: 찾고자 하는 숫자

int BS(int values[], int left, int right, int key){
    int ret = -1;
    int middle = 0;
    
    if (left <= right){
    	middle = (left + right) / 2;
        if (key < values[middle])
        	ret = BS(values, left, middle-1, key);
        else if (key == values[middle])
        	ret = middle;
        else
        	ret = BS(values, middle+1, right, key);
    }

배열에 찾는 숫자(ret)가 있는지 확인하는 문제이다.

조금만 생각해보면 위에 술자리 게임과 같은 형식으로 진행된다는 것을 알 수 있다.

#시간 복잡도 = O(log₂n)

 

반복문st

int BS(int values[], int left, int right, int key){
    int ret = -1;
    int middle = 0;
    
    while (left <= right){
    	middle = (left + right)/2
        if (key < values[middle])
        	right = middle -1;
        else if (key == values[middle]{
        	ret = middle;
            break;
        }
        else left = middle +1;
    }

코드는 결국 다르지만 같은 결국 같은 복잡도를 가지고 있다는 것을 알 수 있다.

자연로그 n만 돌면 값을 찾을 수 있다.

#시간 복잡도 = O(log₂n)

---

---

 

 

 

오늘은 처음으로 코드를 딥하게 들어갔다. 이제 자료구조의 꽃, 배열이 기다리고 있다. 꽃에는 가시가 많다. 겁먹지 말고 화이팅하자!