[DS] 자료구조 개념 및 구현 Chapter 3 연습문제

1. 자료구조 개념 및 구현

1.1. Chapter 3. 재귀 호출 - 연습문제

---

 

Q1. 반복문(iteration)과 비교한 재귀문(recursion)의 장단점은 무엇인가?

- 장점: 알고리즘을 명료하게 표현 가능

- 단점: 빈번한 함수 호출로 인한 스택 오버플로우 현상 발생

 

Q2. n개의 정렬된 정수에 대하여 반복문과 재귀 호출 함수를 각각 사용하여 이진 탐색하는 프로그램을 작성하시오. 재귀 호출 함수가 몇 번 호출되는지 변수를 추가하여 확인하시오.

 

[코드]

      

      

      

    
    

      <c++ />
    
#include <stdio.h>
#include <stdlib.h>


int binary_search(int list[], int item, int left, int right);
int rbinsearch(int list[], int searchkey, int left, int right);
int count=0;



int main() {
    int n, key,tmp;

    printf("입력할 숫자의 개수를 입력하세요:"); scanf("%d",&n);

    int *list = (int*)malloc(sizeof(int)*n);
    printf("%d개의 숫자를 입력하세요.(중복되는 수는 입력하지 않습니다.): \n",n);
    for(int i=0;i<n;i++){
        scanf("%d",&list[i]);
    }

    for(int i=1;i<n;i++){ // 삽입 정렬
        for(int j=0;j<i;j++){
            if(list[i]<list[j]){
                tmp = list[i];
                for(int k=i;k>=j;k--)
                    list[k]=list[k-1];
                list[j]=tmp;
                break;
            }
        }
    }

    printf("찾을 수를 입력하세요 :");scanf("%d",&key);
    printf("이진 탐색 결과: %d\n",binary_search(list,key,0,n-1));
    printf("재귀 이진 탐색 결과: %d\n", rbinsearch(list,key,0,n-1));
    printf("재귀 호출 횟수: %d\n",count);

}

int binary_search(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;
}

int rbinsearch(int list[], int searchkey, int left, int right){
    int middle;
    count++;// 재귀호출시 증가
    if(left<=right){
        middle = (left+right)/2;
        if(list[middle]<searchkey)
            return rbinsearch(list, searchkey, middle+1,right);
        else if(list[middle]>searchkey)
            return rbinsearch(list, searchkey,left,middle-1);
        else
            return middle;
    }
    return -1;
}

 

[실행결과]

 

Q3. 재귀 호출로 순열 구하기

- 다음은 문자들의 순열을 구하는 프로그램이다. start와 end 값이 다음과 같을 때 출력되는 첫 8개의 순열(permutation word)를 각각 쓰시오.

 

[코드]

      

      

      

    
    

      <c++ />
    
#include <stdio.h>
#define exchange(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void word(char* letter, int i, int n);

int start = 0, end = 3;

int main() {
    char letter[] = { 'S', 'M', 'W', 'M','T'};
    printf("Enter start:");scanf("%d", &start);
    printf("Enter end:");scanf("%d", &end);
    word(letter, start, end);

    return 0;
}

void word(char* letter, int i, int n) {
    int j, temp;
    if (i == n) {
        for (j = start; j <= n; j++) printf("%c", letter[j]);
        printf("\n");
    }
    else
        for (j = i; j <= n; j++) {
            exchange(letter[i], letter[j], temp);
            word(letter, i + 1, n);
            exchange(letter[i], letter[j], temp);
        }
}

 

[실행결과]

(a) start = 0, end = 3

(b) start = 1, end = 4

 

Q4. 5개의 문자를 이용하여 가능한 순열(permutation)을 모두 발생시키는 프로그램을 작성하시오. 실행 화면과 같이 순열 번호를 붙여 출력하고 아래의 실행 예를 가지고 테스트하시오.

(단, -1, -1이 입력될 때 프로그램이 종료되도록 한다)

 

[실행 예]

symbol = {'a', 'b', 'c', 'd', 'e'} // 5개의 원소

shuffle(symbol, 0, 3) // 리스트의 0번에서 3번 사이의 원소를 이용하여 순열을 생성하라

shuffle(symbol, 0, 4) // 0번에서 4번 사이의 원소로 순열 생성

shuffle(symbol, 1, 3) // 1번에서 3번 사이의 원소로 순열 생성

 

[코드]

      

      

      

    
    

      <c++ />
    
#include <stdio.h>
#define exchange(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void shuffle(char symbol[], int i, int n);

int start = 0, end = 3,count=0;

int main() {
    char symbol[] = { 'A', 'B', 'C', 'D','E'};
    printf("input two values for start and end position :");
    scanf("%d %d",&start, &end);
    while(start!=-1){
        count=0;
        shuffle(symbol,start,end);
        printf("\ninput two values for start and end position :");
        scanf("%d %d",&start, &end);
    }
    
    return 0;
}

void shuffle(char symbol[], int i, int n) {
    int j, temp;
    if (i == n) {
        printf("[%4d]",++count);
        for (j = start; j <= n; j++) printf("%c", symbol[j]);
        if(count%5==0)printf("\n");
        else printf(" ");
    }
    else
        for (j = i; j <= n; j++) {
            exchange(symbol[i], symbol[j], temp);
            shuffle(symbol, i + 1, n);
            exchange(symbol[i], symbol[j], temp);
        }
}

 

[실행결과]