자료구조 | 자료구조 개념 및 구현 연습문제 풀이 - 3장 | 숙명여대 학점교류

학점교류로 듣는 숙명여대 자료구조

day 7. 중간고사 전날..

 

---

1. 반복문과 비교한 재귀문의 장단점은? 

+ 구현이 편리하다

- frequent function call overhead : 자주 불려서 비효율적임

 

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

 

* 구현

def recursive(lst, item, left, right, cnt):
    if left > right:
        print("cnt = ", cnt)
        return -1
    else:
        mid = (left + right) // 2
        if lst[mid] == item:
            print("Cnt = ", cnt)
            return mid
        elif lst[mid] > item:
            return recursive(lst, item, left, mid, cnt+1)
        else:
            return recursive(lst, item, mid, right, cnt+1)

def withwhile(lst, item, left, right):
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == item:
            return mid
        elif lst[mid] > item:
            right = mid
        else:
            left = mid
    return -1

lst = [1,2,3,4,5,6,7,8,9,10]
item = 3

print(withwhile(lst, item, 0, len(lst)))
print(recursive(lst, item, 0, len(lst), 0))

* 호출 횟수

2
Cnt =  1
2

 

 

 

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

#include <stdio.h>
#define exchange(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
// x는 y로, y는 x로
void word(char*, int, int);

int start = 0, end = 3;

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

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

(전체 아웃풋. 이 중에 첫 8개 즉 S로 시작하는 순열만 적으면 된다)

0
3
SMWU
SMUW
SWMU
SWUM
SUWM
SUMW
MSWU
MSUW
MWSU
MWUS
MUWS
MUSW
WMSU
WMUS
WSMU
WSUM
WUSM
WUMS
UMWS
UMSW
UWMS
UWSM
USWM
USMW

(b) start = 1, end = 4

전체 아웃풋. 마찬가지로 첫 8개의 순열을 기입하면 된다. 이 버전은 M부터 시작한다는 걸 알 수 있다. 

1
4
MWUT
MWTU
MUWT
MUTW
MTUW
MTWU
WMUT
WMTU
WUMT
WUTM
WTUM
WTMU
UWMT
UWTM
UMWT
UMTW
UTMW
UTWM
TWUM
TWMU
TUWM
TUMW
TMUW
TMWU

 

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

 

구현 with python

def swap(str, a, b):
    str[a], str[b]
    return str
    
def permutation(level, str):
    str = (list(str))
    if level >= len(str):
        print("".join(str))
        return
    
    else:
        for i in range(level, len(str)):
            str[level], str[i] = str[i], str[level]
            permutation(level+1, str)
    return

permutation(0,'STRI')