언제나 휴일

[C언어 자료구조] 1. 다루는 내용 이 책은 프로그래머의 기초 지식인 자료구조를 이론적인 접근과 구현을 다루고 있습니다. 자료구조는 프로그램에 관라할 데이터를 어떠한 구조로 보관하고 접근할 것인가를 다루는 것이죠. 선형 자료구조인 배열이나 연결리스트, 스택, 큐와 비선형 자료구조인, 트리, 그래프 등이 있습니다. 컴퓨터 프로그래밍을 업무로 하는 이들에게 자료구조는 실질적인 구현에서 필수적으로 필요합니다. 그리고 이들을 다루는 책은 매우 다양하죠. 이 책에서는 선형 자료구조인 배열, 연결리스트, 스택, 큐를 다루고 비선형 자료구조는 이진 탐색 트리와 그래프를 다룹니다. 이 책에서는 이러한 자료구조를 설명하고 직접 구현하는 과정이 있습니다. 보다 탄탄한 프로그래밍 실력을 다지기 위해 자료구조를 익히고자 하..

순차 정렬(Sequential Sort) 알고리즘 이번에는 반복적인 방법으로 해결하는 순차 정렬(Sequential Sort) 알고리즘을 살펴볼게요. 정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 알고리즘을 말해요. 정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘이 필요합니다. 그리고 수행 후에는 배열 내의 자료들은 원하는 순서로 배치한 상태여야 합니다. 순차 정렬은 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 이를 위해 배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환해요.순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=..

6.3 병합 정렬 알고리즘 소스 코드 //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력하지 말라. //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }; Book *New_Boo..

6.2 병합 정렬 알고리즘 구현 이제 병합 정렬 알고리즘을 구체적으로 구현합시다. #include "common.h" #include "Book.h" typedef void *Element; typedef int (*Compare)(Element , Element); void merge_sort(Element *base, int n, Compare compare) { n의 절반의 크기를 ahalf에 기억합니다. 이는 배열을 분할할 때 앞쪽 배열의 원소 개수입니다. int ahalf = n/2; 배열을 분할할 때 뒤쪽 배열의 원소 개수를 bhalf에 기억합니다. int bhalf = n - ahalf; 분할할 배열을 하나의 배열로 정복하기 위한 인덱스를 선언합니다. ai는 앞쪽 배열의 인덱스로 사용할 것이..

6.1 병합 정렬 알고리즘 성능 분석병합 정렬 알고리즘 성능을 분석해 보아요. 병합 정렬은 배열의 원소가 1개일 때까지 분할하죠. 분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요. 원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠. 결국 분할 횟수 * n 만큼 수행해요. 분할은 원속 개수를 n=>n/2=>n/4... 형태로 분할하므로 2의 h 승이 1이 될 때까지 분할하죠. 수행 속도는 h*n 이예요. 2의 h 승이 n이므로 h는 logn예요. 따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.

6. 병합 정렬(Merge Sort) 알고리즘 이번에는 병합 정렬 알고리즘을 살펴봅시다. 병합 정렬 알고리즘은 배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘입니다. 병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) ah:= n/2 bh:= n - ah; 조건(n이 1보다 작거나 같으면) 종료 병합정렬(base,ah,compare) 병합접열(base+ah,bh,compare) tbase에 동적 메모리 할당(원소크기*원소개수) 메모리 복사(tbase,base) ai:=0 bi:=ah i:=0 반복(ai가 ah보다 작으면서 bi가 n보다 작다) 조건(tbase[ai]가 tbase[bi]보다 작거나 같으면 b..

5.3 퀵 정렬 알고리즘 소스 코드 다음은 퀵 정렬 알고리즘에 관해 구현한 전체 소스입니다. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1..

5.2 퀵 정렬 알고리즘 구현 앞에서 만들었던 정렬 알고리즘과 같은 방법으로 시뮬레이션 코드를 작성합니다. 여기에서는 퀵 정렬 알고리즘만 구현할게요. 참고로 퀵 정렬 알고리즘을 내부 알고리즘을 별도의 함수로 구현하지 않고 직접 구현할게요. 정렬 알고리즘은 수행 속도가 중요한 이슈이므로 복잡하더라도 하나의 함수로 구현할게요. void quick_sort(Element *base, int n, Compare compare) { 먼저 교환에 사용할 임시 변수와 피벗의 위치와 피벗보다 큰 값과 작은 값의 위치를 기억하기 위한 변수를 선언합시다. Element temp;//교환을 위한 임시 변수 int pivot = 0; //피벗의 위치를 기억하기 위한 변수 int big=0, small=0; //피벗보다 큰 값..

5.1 퀵 정렬 알고리즘 성능 분석 퀵 정렬 알고리즘 성능을 분석합시다. n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다. T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = ... = h*n 재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다. h = logn이므로 T(n) = nlogn 그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하..

5. 퀵 정렬(Quick Sort) 알고리즘 퀵 정렬 알고리즘은 재귀적인 방법으로 문제를 해결하는 알고리즘입니다. 퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다. 그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬을 하게 되어 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다. 여기에서는 맨 앞과 맨 뒤, 그리고 중간 위치의 요소..