언제나 휴일

[C언어 알고리즘] 2.2.1 순차 정렬 알고리즘 성능 분석이번에는 순차 정렬 알고리즘의 타당성 및 수행 속도를 계산해 보기로 해요. 순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=0->n) 반복(j:=i+1->n) 조건(compare(base[i], base[j]) > 0) 교환(base[i],base[j]) 순차 정렬의 내부 반복문은 j값이 i+1에서 n까지 변하죠. 그리고 i번째와 j번째 요소와 비교하여 i번째 원소가 크면 교환하기 때문에 i번째에서 j번째 원소 중에 제일 작은 값은 언제나 i번째에 존재합니다. 따라서 내부 반복문을 수행하면 i에서 마지막 원소 중에 제일 작은 값이 i번째에 배치함을 알 수 있어요. 외부 반복문은 i값이 0에서 n까지 ..

[C언어 알고리즘] 2.1 루프 변성과 루프 불변성 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용합니다. 루프 변성은 반복문을 수행하면서 변하는 성질이며 루프 불변성은 변하지 않는 성질을 말합니다. 예를 들어 정수 start에서 end 사이의 합계를 구하는 문제가 있다고 가정합시다. 이 문제는 다음과 같은 방법으로 해결할 수 있습니다. 특정 범위의 합계 구하기(start:시작 값, end: 끝 값) sum:= 0 반복(index:=start; index

[C언어 알고리즘] 1.3 공통으로 사용할 코드앞으로 이 책에서 공통으로 사용할 소스를 먼저 소개할게요. 같은 부분을 계속 지면을 할애하는 것보다 앞에서 언급하고 넘어갈게요. 이 책에서 공통으로 사용할 Book 형식을 정의합시다. Book 형식에는 제목, 저자, 번호를 멤버로 구성하세요. #pragma once #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을 생성하는 함수와 소멸하는 함수를 제공합시다. Book *New_Book(const char *..

[C언어 알고리즘] 1. 2 알고리즘의 평가와 접근적 표기같은 문제를 해결하는 알고리즘은 여러 개가 있을 수 있죠. 전산에서 알고리즘을 평가하는 방법은 여러가지가 있어요. 그 중에서 수행 속도를 평가하거나 메모리 효율을 평가하는 점근식 방법을 많이 사용하죠. 점근적 표기에서는 n개의 자료가 있을 때 알고리즘 수행 시간(혹은 메모리 사용)이 n과 어떠한 상관관계가 있는지 표현하는 방법입니다. 예를 들어 어떠한 알고리즘이 n개의 자료가 있을 때 수행 시간 T(n)= 3n+27이라고 가정할게요. 만약 n이 충분히 큰 수라면 가장 높은 차수의 항이 결과에 가장 큰 영향을 주겠죠. 점근식 표기에서는 가장 높은 차수의 항을 제외한 나머지 차수의 항은 버리고 계산해요. 그리고 상수도 생략하여 평가합니다. 따라서 T(..

[C언어 알고리즘] 1.1 알고리즘(Algorithm) 알고리즘은 특정 문제를 해결하기 위한 논리를 말해요. 해결해야 할 어떠한 문제가 주어지면 문제에 주어지는 선행 조건과 영향 인자와 후행 조건을 알아겠죠. 선행 조건은 알고리즘을 수행 하기 전의 상태를 말합니다. 그리고 영향 인자는 문제를 해결하는데 영향을 주는 인자예요. 후행 조건은 문제를 해결하고 난 후의 상태를 말해요. 결국 알고리즘은 선행 조건인 상태에서 주어진 영향 인자를 가지고 후행 조건에 맞게 문제를 해결하는 것이죠. 예를 들어 특정 범위 내의 정수의 합계를 구하는 문제를 살펴봅시다. 이 때는 선행 조건은 특별한 것이 없네요. 문제를 해결하는 데 영향을 주는 인자는 범위의 시작과 끝이겠죠. 따라서 알고리즘을 함수로 구현한다면 입력 인자로 ..

[C언어 알고리즘] 1. 다루는 내용출간일 2016년 11월 30일판매가 3000원형태 ebook학습에 도움이 되시면 ebook을 구입하여 소장하시면 감사하겠습니다.언제나 휴일 출판사의 수익금의 대부분은 아프리카에 기부하고 있습니다. 이 책은 프로그래머의 기초 지식인 알고리즘을 이론적인 접근과 구현을 다루고 있습니다. 알고리즘은 문제를 해결하기 위한 논리의 집합이예요. 문제 해결 방법으로 분류하면 반복 알고리즘, 재귀 알고리즘, 분할 정복, 동적 프로그래밍, 탐욕 알고리즘 등이 있죠. 컴퓨터 프로그래밍을 업무로 하는 이들에게 알고리즘은 실질적인 구현에서 필수적으로 필요합니다. 그리고 이들을 다루는 책은 매우 다양하죠. 이론으로 접근하는 책들은 다양한 알고리즘을 다루지만 실질적인 구현없이 추상적으로 소개할..

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