ch8. 알고리즘

1. 알고리즘의 조건을 기술하여라.

1) 0 개 이상의 입력과 1 개 이상의 출력이 있어야 한다.

2) 종료되어야 한다.

3) 모든 명령이 실행 가능해야 한다.

2. 다음의 데이터들에 대해 물음에 답하여라

[ 95 ] [ 75 ] [ 85 ] [ 100 ] [ 50 ]

[문제 풀기에 앞서 동작 원리부터 살펴보자]

선택정렬(selection sort) : 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식

#include<stdio.h> #define MAX 20 /* 데이터의 최대 수를 의미하는 매크로 */ void select_sort(int data[], int n); main() { int i, n; int data[MAX]; printf("number of data -> "); scanf("%d", &n); for(i=0; i<n ; i++) { printf("%i\'s number => ", i+1); scanf("%d",&data[i]); } select_sort(data, n); // select_sort 함수 호출 printf("\nsorted data : "); for(i=0; i<n; i++) { printf("%d", data[i]); } printf("\n"); } void select_sort(int data[], int n) { int i,j,k, temp; for(i=0 ; i<n ; i++) { k = i; for(j=i+1; j<n ;j++) { if(data[k] > data[j]) k = j; } //swap temp = data[i]; data[i] = data[k]; data[k] = temp; } }

삽입정렬(insertion sort) : 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

#include<stdio.h> #define MAX 20 /* 데이터의 최대 수를 의미하는 매크로 */ void insert_sort(int data[], int n); main() { int i, n; int data[MAX]; printf("number of data -> "); scanf("%d", &n); for(i=0; i<n ; i++) { printf("%i\'s number => ", i+1); scanf("%d",&data[i]); } insert_sort(data, n); // insert_sort 함수 호출 printf("\nsorted data : "); for(i=0; i<n; i++) { printf("%d", data[i]); } printf("\n"); } void insert_sort(int data[], int n) { int i,j,k; for(i=1 ; i<n ; i++) { k = data[i] for(j=i-1 ; j>=0 && k<data[j] ; j--) data[j+1] = data[j]; data[j+1] = k; } }

버블정렬(bubble sort) : 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식

#include<stdio.h> #define MAX 20 /* 데이터의 최대 수를 의미하는 매크로 */ void bubble_sort(int data[], int n); main() { int i, n; int data[MAX]; printf("number of data -> "); scanf("%d", &n); for(i=0; i<n ; i++) { printf("%i\'s number => ", i+1); scanf("%d",&data[i]); } bubble_sort(data, n); // bubble_sort 함수 호출 printf("\nsorted data : "); for(i=0; i<n; i++) { printf("%d", data[i]); } printf("\n"); } void bubble_sort(int data[], int n) { int i,j,temp; for(i=0; i<n-1 ; i++) { for(j=1; j<n-1 ; j++) { /*data[j-1]이 data[j]보다 크면 swap*/ if(data[j-1] > data[j]) { temp = data[j-1]; data[j-1] = data[j]; data[j] = temp; } } } }

퀵정렬(quick sort) : 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방식

//left는 시작위치 , right는 마지막 위치를 의미한다. key는 기준키를 나타낸다. void quick_sort(int data[], int left, int right){ int i, j, key, temp; if(left<right){ i = left; j = right+1; key = data[left]; do{ do{ i++; }while(data[i] < key); do{ j--; }while(data[j] > key); if( i < j ){ temp = data[i]; data[i] = data[j]; data[j] = temp; } }while( i < j ); temp = data[left]; data[left] = data[j]; data[j] = temp; quick_sort(data, left, j-1); quick_sort(data, j+1, right); }

(1) 선택 정렬을 이용하여 오름차순으로 정렬하여라

(2) 삽입 정렬을 이용하여 오름차순으로 정렬하여라

(3) 버블 정렬을 이용하여 오름차순으로 정렬하여라

(4) 퀵 정렬을 이용하여 오름차순으로 정렬하여라

3. 다음의 데이터들에 대해 물음에 답하여라.

[문제 풀기에 앞서 동작 원리부터 살펴보자]

선형탐색(linear search) : 순차탐색이라고도 하는데, 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법.

int linear_search(int data[], int k, int n) { /*k는 찾고자하는 데이터이고, n은 데이터의 개수 */ int i; for( i=0 ; i<n ; i++){ if(data[i] == k) return i; //탐색 성공 시 i 를 반환 } return -1; // 탐색 실패 시 -1 을 반환 }

이진탐색(binary search) : 정렬된 데이터 집합을 이분화하면서 탐색하는 방법.

int binary_search(int data[], int k, int n) { /*k는 찾고자하는 데이터이고, n은 데이터의 개수 */ int low, high, mid; low = 0; high = n-1; while(low < high-1){ mid = (low+high)/2 ; /*중간에 위치한 데이터의 인덱스 계산*/ if( k < data[mid] ){ /*중간에 위치한 값보다 작으면 왼쪽 영역에서 탐색*/ high = mid - 1; else if( k == data[mid] ) /*탐색에 성공하면 위치 정보인 mid를 반환*/ return mid; else /*중간에 위치한 값보다 크면 오른쪽 영역에서 탐색*/ low = mid + 1; } return -1; /*탐색에 실패하면 -1을 반환*/ }

(1) 선형 탐색을 이용하여 데이터 7을 탐색하여라.

(2) 이진 탐색을 이용하여 데이터 7을 탐색하여라.

4. 재귀호출을 이용하여 n!를 구하는 함수를 작성하여라

int factorial(int n) { if(n>1) return n*factorial(n-1); else return 1; }

5. 하노이 탑을 구하는 함수를 다음과 같이 호출하였을 때의 동작 과정을 기술하여라.

[ hanoi(3 , "left" , "middle", "right"); ]

<하노이 탑을 구하는 함수>

---------------------------------------------------------------------------------

void hanoi(int n, char A[], char B[], char C[])

{

if (n == 1)

printf("board %d move %s -> %s", n , A , C);

else {

hanoi(n-1, A, C, B);

printf("board %d move %s -> %s", n , A , C);

hanoi(n-1, B, A, C);

}

}

---------------------------------------------------------------------------------

빨간색이 출력이구

위에서부터 차례대로 그 출력 결과입니다!