gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. 재귀호출

- 함수가 실행 중에 자기 자신을 다시 호출하는 것이다.

- 같은 작업을 반복하는데 조금씩 상황이 바뀌는 경우에 사용한다.

- 함수에 반드시 종결 조건이 있어야 한다.

- Divide & Conquer 전략에 사용된다.

- 재귀 호출문은 if-else나 while문을 활용한 반복문으로 바꿀 수 있다.

- 컴파일러의 관점에서 재귀 호출은 새로운 함수를 호출하는 것과 같다.

- 따라서 함수를 호출할 때마다 함수의 지역 변수, 복귀 주소 등 컨텍스트 정보를 활성 레코드에 저장해야 한다.

- 장점 : 알고리즘을 깔끔하게 표현할 수 있다.

- 단점 : 함수를 실행할 때마다 메모리에 환경 변수를 저장하기 때문에 메모리의 소모가 일어난다.

2. 팩토리얼 예제

- n! = 1 x 2 x ... x (n-1) x n = (n-1)! x n

- 같은 일 (곱셈) 을 반복하면서 n = 0이면 n! = 1 이라는 종결 조건이 포함되어있기 때문에 재귀 호출을 사용할 수 있다.

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

이와 같이 n = 0 이면 1을, n > 0 이면 n * (n-1)! 을 반환하는 형식으로 표현할 수 있다.

3. 최대공약수 (GCD) 예제

- 공통으로 나누는 수 중 가장 큰 수 

- 조건 (by 유클리드 호제법)

    - gcd (x, y) = gcd (y, x % y)  (if (y > 0))

    - gcd (x, 0) = x

ind gcd (x, y)
{
    if (y == 0)
        return x;
    else return gcd (y, x % y);
}

4. Binary Search 이진 탐색

- 정렬된 항목 리스트에 대해서 중간값과 크기를 비교하고 그 결과에 따라 가능성이 있는 절반의 리스트에 대해서만 과정을 반복하는 탐색 알고리즘이다.

- 한 번 비교할 때마다 탐색 대상 원소의 수가 절반으로 감소한다.

- 원소의 수가 n개일 때 이진탐색은 총 log₂ⁿ 번의 비교 횟수를 요구한다. 따라서 순차 탐색보다 속도가 빠르다.

- 조건은 리스트 안에 겹치는 숫자가 없어야 한다는 것이다. 

-while문과 if문을 이용한 이진탐색

#include <stdio.h>
int binsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int binsearch (int list[], int item, int left, int right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (list[mid] == item)
            return mid;
        else {
            if (item < list[mid]
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return -1;
}

- 재귀호출 형식의 이진탐색

#include <stdio.h>
int rbinsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int rbinsearch (int list[], int item, int left, int right)
{
    int mid;
    if (left <= right)
    {
        mid = (left + right) / 2;
        if (item == list[mid] 
            return mid;
        else if (list[mid] < item)
            return rbinsearch(list, item, mid + 1, right);
        else 
            return rbinsearch (list, item, left, mid - 1);
     }
     return -1;
 }
        

5. 하노이 타워 예제

- 세 개의 기둥과 크기가 다양한 원판이 존재한다. 

- 해결할 문제는 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮기는 것이다.

- 조건

    - 한 번에 하나의 원판만 옮길 수 있다.

    - 큰 원판이 작은 원판 위에 놓일 수 없다.

- 알고리즘

    - 세 개의 기둥 A, B, C 가 있고, A에서 B로 n개의 원판을 옮긴다.

    1) A에서 (n-1)개의 원판을 C로 옮긴다.

    2) A에 남은 1개의 원판을 B로 옮긴다.

    3) C에 있는 (n-1)개를 B로 옮긴다. 

- 기둥 a = 1, b = 2, c = 6 - a - b // a, b 제외한 빈 기둥이 c

- 총 이동횟수 : 2ⁿ - 1

#include <stdio.h>
void htower(int n, int a, int b);

int count = 0;

void main()
{
    int n;
    count = 0;
    printf("Enter disc number = ");
    scanf("%d", &n);
    htower(n, 1, 2);
    printf("# move for %d discs : %d\n", n, count);
}

void htower (int n, int a, int b)
{
    int c;
    count ++;
    if (n == 1)
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, b);
        
    else {
        c = 6 - a - b;
        htower(n-1, a, c);
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, c);
        htower(n-1, c, b);
    }
}

- Time complexity 시간 복잡도 

    - t(1) = 1 : 하나의 디스크 옮기는데 필요한 시간

    - time to move n disks : t(n)

        - t(n) = 2 t(n-1) + 1

                 = 2 (2 t(n-2) + 1) + 1

                 = ...

                 = 2ⁿ⁻¹ + 2ⁿ⁻² + ... + 2¹ + 2⁰

                 = 2ⁿ - 1 ≅ 2ⁿ

    - t(n) = O(2ⁿ) 

    → n 이 크면 사용하지 않는 것이 좋다.

6. Permutation 순열

- 순서를 다르게 나열하는 방법의 수

- {a, b, c, d}  → ₄P₄ = 4! = 24

a) (a, Perm (b, c, d))  →  Perm(b, c, d) = (b, Perm (c, d)), (c, Perm (b, d)), (d, Perm (b, c)) 

b) (b, Perm (a, c, d))

c) (c, Perm (a, b, d))

d) (d, Perm (a, b, c))

// i : start index of range
// n : end index of range

void perm(char list[], itn i, int n)
{
    int j;
    if (i == n)      // list print
    { 
        for (j = 0; j <= n; j++)
            printf("%c", list[j]);
        printf("   ");
    }
    else {
        for (j = i; j <= n; j++) {
            Swap(list[i], list[j]);    // 두 수 교환
            perm(list, i + 1; n);
            Swap(list[i], list[j]);
        }
    }
}