정렬, 재귀, 링키드 리스트... Quiz 2nd 2007

 알고리즘 수업 시간 교수님 왈, '3월 한달간 과제의 수가 10개더구나' 라고 한다. 그러면서 어제 두번째 퀴즈라고 하시면서 문제를 4문제 내 주셨는데, 이것이 또 과제가 되었다. 어제 약속이 있어서 약간은 늦은 11시에 시작해서 오늘 아침 6시가 넘어서야 완전하게 끝낼 수 있었다(퀴즈 + 이전 과제).
 문제는 정렬에 관련된 것이 두 문제, 재귀에 관한 것이 하나, 링키드 리스트에 관한 문제가 하나였다. 이번주 월요일부터 몸이 안좋아서 최근 일년이내에서 가장 몸 상태가 안좋은데, 이거 한다고 밤새는 바람에 목소리까지 변할 정도로 감기가 악화되었다. 문제는 아주 어려운 정도는 아니다. 물론 이 정도의 문제도 나에게 책도 펴보지 말고 풀라고 하면 다 못풀지도 모르겠지만...
1. 배열 a, b는 각각 크기순으로 정렬된 m 및 n개의 배열 요소로 이루어진 1차원 배열이다. 이 배열 a, b를 합쳐서 크기순으로 정렬하여 배열 c에 기억시키는 merge(a, b, c, m, n) 함수를 정의하고 이것을 이용한 프로그램이다. 괄호를 메우시오(빈칸 채우기, 밑줄 부분이 원래 빈칸이였음)
#include <stdio.h>

void merge(int *a, int *b, int *c, int m, int n)
{
int i = 0, j = 0;
while(i < m && j < n) // i 혹은 j 둘중 하나라도 배열의 끝에 도달하면 끝.
{
if (*a <= *b) // a 가 b 보다 작으면 먼저 a의 값을 순차적으로 대입
{
*c++ = *a++; // c는 최종적으로 병합된 결과값이 될 배열
i++;
}
else // 아니면 b의 값을 순차적으로 대입
{
*c++ = *b++;
j++;
}
}

if (i == m && j == n) // 병합이 끝났다는 의미므로 리턴
return;
else if(j < n) // j < n 일 경우, b에 남은 모든 값은 a의 값보다 크다.
{
for(; j < n; j++)
*c++ = *b++;
}
else if(i < m) // i < m 일 경우, a의 남은 모든 값은 b의 값보다 크다.
{
for(; i < m; i++)
*c++ = *a++;
}
}

int main()
{
static int asm1[5] = {56, 64, 76, 85, 94};
static int asm2[6] = {55, 68, 78, 82, 90, 95};
int total[11];
int i, item;

merge(asm1, asm2, total, 5, 6);

for (i = 0, item = 0; i < 11; i++)
{
printf("%5d", total[i]);
item++;
if (item == 4)
{
putchar('\n');
item = 0;
}
}
return 0;
}
2. 다음 정의된 함수를 재귀함수 프로그램으로 정의하고 f(7)의 값을 구하시오
     f(x)=f(x-1)+f(x-2) 단 f(0)=1, f(1)=1, 그 외 x는 양수
#include <stdio.h>

int f(int x)
{
if (x <= 1)
return 1;
else {
return f(x-1) + f(x-2);
}
}

int main()
{
int x = 7;
printf("%d fibonacci number : %d\n", x, f(x));

return 0;
}
3. 아래의 그림과 같이 문자 'a', 'b', 'd'가 링키드 리스트에 연결되어 있다고 할 때, 'b'와 'd' 사이에 문자 'c'를 삽입하는 프로그램을 작성하시오. 단, struct를 사용하고 NULL은 0으로 정의되어 있다.(그림 생략)
#include <stdio.h>
#include <malloc.h>

typedef struct list {
char ch;
struct list* next;
}LIST;

LIST* addNode(char ch);
int insertNode(char insert_ch, char search_ch);
void printNode(LIST* head);

LIST* head;

int main()
{
head = 0;

addNode('a'); // a 노드 추가
addNode('b'); // b 노드 추가
addNode('d'); // c 노드 추가

printf("\n** Before insert node\n ");
printNode(head); // 전체 노드 출력

if(insertNode('c', 'b')) // c 노드를 b노드 다음에 삽입
printf("** New node insert sucessed\n\n");
else {
printf("** New node insert failed\n\n");
return 0;
}

printf("** After insert node\n ");
printNode(head); // 전체 노드 출력

return 0;
}

LIST* addNode(char ch)
{
LIST* tmp = 0;
LIST* new = 0;

// 추가될 노드의 메모리 확보
new = (LIST*)malloc(sizeof(LIST));
new->ch = ch; // 새로운 노드에 값 추가
new->next = 0;

if(head == 0) { // 첫번째 노드이면
head = new; // head는 새로운(첫번쨰) 노드이다.
return head;
} else { // 첫번째 노드가 아니면
tmp = head;
while(tmp->next != 0) // 마지막 노드를 찾는다.
tmp = tmp->next;
tmp->next = new; // 마지막 노드 뒤에 새로운 노드를 추가
return tmp;
}
}

int insertNode(char insert_ch, char search_ch)
{
LIST* new;
LIST* tmp = head;

// 삽입할 노드의 메모리 할당
new = (LIST*)malloc(sizeof(LIST));

// 찾는 노드가 나올때 까지 끝까지 검색
while( (tmp->ch != search_ch) && (tmp->next != 0) ) {
tmp = tmp->next;
}
if( tmp->next == 0) // 노드를 못 찾으면 false값 리턴
return 0;
else { // 노드를 찾았으면 그 노드 위에 새로운 노드 추가 후 ture값 리턴
new->ch = insert_ch; // 새로운 노드에 값 삽입
new->next = tmp->next; // 새로운 노드의 next는 이전 노드의 next
tmp->next = new; // 이전 노드의 next는 이제 새로운 노드
return 1;
}
}

void printNode(LIST* head)
{
LIST* tmp = head;
while(tmp != 0) { // 노드가 빌때 까지(끝까지) 노드 값 출력
printf("\'%c\' next_node -> ", tmp->ch);
tmp = tmp->next;
}
printf("0\n\n");
}
4. 다음 데이터들이 주어져 있다.
        92.0, 73.2, 32.5, 67.6, 88.0, 45.0, 69.0
   위 데이터를 퀵정렬과 버블정렬을 사용하여 정렬되는 과정을 나타내는 프로그램을 작성하시오.
#include <stdio.h>

int size, i = 0;
int tmp[30];

int partition(int a[], int begin, int end);
void merge(int S[], int m, int middle, int n);
void mergeSort(int S[], int m, int n);
void quickSort(int S[], int begin, int end);

int main()
{
int S[8] = {69, 10, 30, 2, 16, 8, 31, 22};
int menu, t;
size = 8;

printf("\n 입력 원소 >> ");
for(t = 0; t < size; t++)
printf("%d ", S[t]);

printf("\n 정렬 방법 선택\n 1. 병합정렬\n 2. 빠른정렬\n #) ");
scanf("%d", &menu);

switch(menu) {
case 1:
mergeSort(S, 0, size-1);
printf("\n");
break;
case 2:
quickSort(S, 0, size-1);
break;
default:
printf("\n1과 2중에서 선택하세요.\n");
}

return 0;
}

void merge(int S[], int m, int middle, int n)
{
int j, k, t;
i = m;
j = middle+1;
k = m;

// 최좌측의 수가 중간 값보다 작거나 같고
// 최우측의 수가 중간 값보다 중간값(+1)보다 크거나 같으면 반복
while (i <= middle && j <= n) {
// S의 최좌측이 S의 최우측보다 작거나 같으면 tmp에 S의 최좌측 값을 대입
if(S[i] <= S[j]) {
tmp[k] = S[i];
i++;
} else { // 아니면 tmp에 S의 최우측 값을 대입
tmp[k] = S[j];
j++;
}
k++;
}
// 최 좌측의 수가 중간값보다 크면
if(i > middle)
for(t = j; t <= n; t++, k++)
tmp[k] = S[t];
else // 최 좌측의 수가 중간값보다 작거나 같으면
for(t = i; t <= middle; t++, k++)
tmp[k] = S[t];
// S의 최좌측부터 최우측까지 tmp의 값을 대입
for(t = m; t <= n; t++)
S[t] = tmp[t];

printf("\n 병합 정렬 >>\n\t\t");
for(t = 0; t < size; t++) // 현재까지의 결과 출력
printf("%d ", S[t]);
}

void mergeSort(int S[], int m, int n)
{
int middle;
if(m < n) {
middle = (m + n) / 2;
mergeSort(S, m, middle); // 중간값 기준 좌측
mergeSort(S, middle+1, n); // 중간값 기준 우측
merge(S, m, middle, n); // 병합
}
}

int partition(int S[], int begin, int end)
{
int pivot, temp, L, R, t;
L = begin;
R = end;
pivot = (begin + end) / 2; // 기준점(pivot)은 중간으로 선택

printf("\n[ %d 단계 : pivot = %d]\n", ++i, S[pivot]);

// L이 R의 좌측에 있을 동안
while(L < R) {
// 피봇 좌측의 수가 피봇보다 작고, L이 R의 좌측에 있을 동안 L 증가
while((S[L] < S[pivot]) && (L < R))
L++;
// 피복의 우측의 수가 피봇보다 크고, L이 R의 좌측에 있을 동안 R 감소
while((S[R] >= S[pivot]) && (L < R))
R--;
/* 피봇 좌측의 수가 피봇의 수보다 크거나
* 피봇의 우측의 수가 피봇보다 작거나 같을 때 while을 벗어남으로
* 그렇게 증가한 L과 감소한 R을 비교했을때 여전히 L이 R의 좌측이면
* L과 R의 값을 교환 */
if(L < R) {
temp = S[L];
S[L] = S[R];
S[R] = temp;
}
}

// 피봇과 R의 우측값을 교환
temp = S[pivot];
S[pivot] = S[R];
S[R] = temp;

// 현재까지 결과 출력
for(t = 0; t < size; t++)
printf(" %d", S[t]);
printf("\n");

return L;
}

void quickSort(int S[], int begin, int end)
{
if(begin < end) {
int p;
p = partition(S, begin, end);
quickSort(S, begin, p-1); // 피봇의 좌측
quickSort(S, p+1, end); // 피봇의 우측
}
}

    참고자료
  • C로 배우는 쉬운 자료구조 - 이지영 저 / 한빛미디어
  • C/C++ 개발자를 위한 포인터 실무 KIN - 진용훈 저 / 사이텍미디어

by sakuragi | 2007/04/05 20:00 | :: R space :: 과제 | 트랙백 | 덧글(4)

트랙백 주소 : http://sakuragis.egloos.com/tb/3275703
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 환상경 at 2007/04/07 10:59
후..... 대단하세요 >_<
저는 전혀 이해가 안되는 -_-ㅋ

ps. 건강관리 잘하세요 이제 곧 중간고사도 다가오는데 최상의 컨디션을 유지하셔야죠 ^^
Commented by sakuragi at 2007/04/08 20:50
환상경, 훼~ 이해가 안되시긴요. 잘 하시면서.. :)
그러게요. 다음주까지 감기를 끌고 가면 안되는데.. 우찌 될런지..
Commented by freecatz at 2007/04/09 10:17
아웅..멀미나...ㅡㅡ;;
Commented by sakuragi at 2007/04/10 21:10
freecatz, = _=)a.. 알고보면 아무것도 아니예요..

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: