[자료구조 프로그래밍 연습문제] 선택 정렬, 이진 탐색, 다항식 곱하기

1. selection sort

 

A. 교재 1장 Program 1.4: Selection sort의 함수 sort()는 오름순(non-decreasing order) 정렬과 내림순(non-increasing order) 정렬 중 어느쪽을 수행하는가? 교재의 함수 sort()를 교재의 정렬 순서와 반대 순서로 정렬하도록 수정한 C 코드를 제시하시오.

 

오름순(non decreasing order) 정렬을 수행한다.

void sort(int list[], int n)
{
	int i, j, max, temp;
    for (i = 0; i < n - 1; i++) {
    	max = i;
        for (j = i + 1; j < n; j++)
        	if (list[j] > list[max])
            	max = j;
            SWAP(list[i], list[max], temp);
     }
}

 

B. 배열 list[]가 int list[5] = {2, 7, 9, 3, 1}; 로 초기화 되었을 때 내림순 정렬을 수행하는 경우, 배열 list[]의 값이 정렬 종료까지 변해가는 과정을 보이시오. (답안형식: 1장 강의슬라이드(part 1) 11쪽 참조)

 

 

C. 교재 1장 Program 1.4: Selection sort의 C 코드를 컴파일하고 실행하시오. 단, 교재의 C 코드는 사용하는 컴파일러 및 버전에 따라 일부 수정이 필요할 수 있음에 유의 (예: scanf, 헤더파일 등). 이 경우 컴파일 및 실행에 아무 문제가 없도록 먼저 수정하시오. 최종 C 코드 수정본과 실행 결과를 제출하시오. 실행시 요구되는 n 값은 각자 임의로 입력.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) =(t))

void sort(int[], int); /*selection sort*/

void main(void)
{
	int i, n;
	int list[MAX_SIZE];
	printf("Enter the number of numbers to generate: ");
	scanf_s("%d", &n);
	if (n < 1 || n > MAX_SIZE) {
		fprintf(stderr, "Improper value of n\n");
		exit (EXIT_FAILURE);
	}
	for (i = 0; i < n; i++) {
		list[i] = rand() % 1000;
		printf("%d ", list[i]);
	}
	sort(list, n);
	printf("\nSorted array: \n");
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
}

void sort(int list[], int n)
{
	int i, j, min, temp;
	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++)
			if (list[j] < list[min])
				min = j;
		SWAP(list[i], list[min], temp);
	}
}

 

 

2. binary search

 

A. 교재 1장 Program 1.7: Searching an ordered list의 함수 binsearch()는 배열 list[]의 값이 오름순으로 정렬되어 있다고 가정하고 있다. 이를 list[]의 값이 내림순 정렬되어 있는 경우에 작동하도록 수정한 C 코드를 제시하시오.

 

int binsearch(int list[], int searchnum, int left, int right)
{
	int middle;
    while (left <= right) {
    	middle = (left + right) / 2;
        switch (COMPARE(list[middle], searchnum)) {
        case -1: right = middle - 1;
        	break;
        case 0: return middle;
        case 1: left = middle + 1;
        }
    }
    return -1;
}

B. 교재 1장 Program 1.7: Searching an ordered list의 함수 binsearch()를 아래 기능을 추가하여 확장하시오. 수정된 C 코드와 작동 정확성 테스트 실행 결과를 제출하시오.

• 추가 기능: 탐색하는 값이 배열 list[]에 없는 경우 –1을 반환하기 전에 그 값을 배열 list[]에 정렬 순서
  상 정확한 위치에 삽입한 후 –1을 반환. 단, 배열 list[]는 원소가 1개 더 늘어나도 수용 가능한 충분한
  크기로 선언되어 있다고 가정.
  예:
  main()에서 int list[7] = {1, 4, 9, 15, 30, 0, 0}; 와 같이 배열 list[]를 초기화한 후, 아래 순서로 호출
  binsearch(list, 30, 0, 4) 호출 //4 반환
  binsearch(list, 10, 0, 4) 호출 //-1 반환 (list[]는 {1, 4, 9, 10, 15, 30, 0}로 변경됨)
  binsearch(list, 10, 0, 5) 호출 //3 반환
  binsearch(list, 30, 0, 5) 호출 //5 반환

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) =(t))
#define COMPARE(x,y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)

void sort(int[], int); /*selection sort*/
int binsearch(int[], int, int, int); /*binary search*/

void main(void)
{
	int i, n, m;
	int list[MAX_SIZE];
    
	printf("Enter the number of numbers to generate: ");
	scanf_s("%d", &n);
    
	if (n < 1 || n > MAX_SIZE) {
		fprintf(stderr, "Improper value of n\n");
		exit(EXIT_FAILURE);
	}
    
	for (i = 0; i < n; i++) {
		list[i] = rand() % 1000;
		printf("%d ", list[i]);
	}
    
	sort(list, n);
	printf("\nSorted array: \n");
    
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
    
	printf("Enter the number to search: ");
	scanf_s("%d", &m);
	printf("Result: %d", binsearch(list, m, 0, n - 1));
}

void sort(int list[], int n)
{
	int i, j, min, temp;
    
	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++)
			if (list[j] < list[min]) min = j;
				SWAP(list[i], list[min], temp);
	}
}

int binsearch(int list[], int searchnum, int left, int right)
{
	int middle;
	int last = right;
    
	while (left <= right) {
		middle = (left + right) / 2;
		switch (COMPARE(list[middle], searchnum)) {
			case -1: left = middle + 1;
				break;
			case 0: return middle;
			case 1: right = middle - 1;
		}
	}
    
	for (int i = last; i >= left; i--) {
		list[i + 1] = list[i];
	}
    
	list[left] = searchnum;
	printf("Remade list: ");
    
	for (int i = 0; i <= last + 1; i++) {
		printf("%d ", list[i]);
	}
    
	printf("\n");
	return -1;
}

 

 

3. 다항식 곱하기

 

임의의 두 다항식 A, B를 입력받아 곱을 수행한 결과 다항식 C를 출력하는 C 프로그램을 작성하시오.

• 다항식은 아래 구조체를 자료형으로 하는 배열로 표현한다. 즉, 배열 선언은 polynomial A[3], B[3],
  C[9];로 한다. 단, 편의상 A, B의 항(term) 수는 각각 3개, C는 최대 9개로 고정한다.
  typedef struct {
      int coef; //계수
      int exp; //지수
  } polynomial;
• A, B 다항식은 지수값으로 정렬되지 않은 상태로 주어진다고 가정하며, 편의상 아래 예와 같이 계수
  및 지수 값 배열을 통해 최종 A[3], B[3] 배열에 입력되도록 한다. 배열명과 크기 3은 반드시 아래 예
  그대로 사용한다. (조교가 두 line을 계수값 및 지수값만 바뀐 line으로 대체한 후 컴파일 예정)
  int A_coef[3] = {2, 2, 3}; int A_exp[3] = {3, 2, 4}; // A(x) = 2x3 + 2x2 + 3x4
  int B_coef[3] = {7, 3, 4}; int B_exp[3] = {0, 1, 2}; // B(x) = 7 + 3x + 4x2
• C 다항식 산출 과정에서는 2번의 수정된 binary search를 이용한다 (정렬순은 각자 선택).
• 최종 결과 C 다항식은 지수값 내림순으로 아래와 같은 형식으로 출력한다.
  C(x) = 12x6 + 17x5 + 35x4 + 20x3 + 14x2 //각 항을 “계수x지수”로 표시
• 다항식 항의 정렬이 필요하다면 1번의 selection sort를 수정하여 이용한다 (정렬순은 각자 선택).

 

#include <stdio.h>
#include <stdlib.h>
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) =(t))
#define COMPARE(x,y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)
typedef struct {
	int coef; // 계수
	int exp; // 지수
} polynomial;
int binsearch(polynomial[], polynomial, int, int); /*binary search*/
void main(void)
{
	int i, j;
	int cnt = 0;
	int loc;

	int A_coef[3] = { 2, 2, 3 }; int A_exp[3] = { 3, 2, 4 };
	int B_coef[3] = { 7, 3, 4 }; int B_exp[3] = { 0, 1, 2 };

	polynomial A[3], B[3], C[9], temp;

	for (i = 0; i < 3; i++) {
		A[i].coef = A_coef[i];
		A[i].exp = A_exp[i];
		B[i].coef = B_coef[i];
		B[i].exp = B_exp[i];
	}

	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			temp.coef = A[i].coef * B[j].coef;
			temp.exp = A[i].exp + B[j].exp;
			if (cnt) {
				loc = binsearch(C, temp, 0, cnt);
				if (loc > -1) {
					C[loc].coef += temp.coef;
				}
				else cnt++;
			}
			else {
				C[0] = temp;
				cnt = 1;
			}
		}
	}

	printf("C(x) = ");
	for (i = 0; i < cnt - 1; i++) printf("%dx%d + ", C[i].coef, C[i].exp);
	printf("%dx%d", C[cnt - 1].coef, C[cnt - 1].exp);
	printf("\n");
}
int binsearch(polynomial C[], polynomial temp, int left, int right)
{
	int middle;
	int last = right;
	while (left <= right) {
		middle = (left + right) / 2;
		switch (COMPARE(C[middle].exp, temp.exp)) {
		case -1: right = middle - 1;
			break;
		case 0: return middle;
		case 1: left = middle + 1;
		}
	}
	for (int i = last; i >= left; i--) {
		C[i + 1] = C[i];
	}
	C[left] = temp;
	return -1;
}