언제나 휴일

[C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 하노이 타워 알고리즘을 구현합시다. 알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다. void Hanoi(const char *src, const char *use, const char *dest, int n) { 만약 돌이 없으면 아무 것도 수행하지 않고 함수를 종료합니다. 즉 탈출 조건입니다. if(n

[C언어 알고리즘] 3.2.1 하노이 타워 알고리즘 성능 분석 하노이 타워 알고리즘 성능을 분석합시다. n 개 돌을 옮기는 데 걸리는 수행 시간을 T(n)이라고 합시다. 하노이 타워 알고리즘의 수행 시간 T(n)은 T(n-1) 2번과 Move 1번으로 진행합니다. T(n) = 2*T(n-1) + 1 = 2 *T(n-2) + 2 +1 = 2^2*T(n-3) +4+2+1 = ... = 2^n -1 따라서 하노이 타워 알고리즘 수행 시간은 O(2^n)이라고 말할 수 있습니다. [그림 3.2] 하노이 타워 알고리즘

[C언어 알고리즘] 3.2 하노이 타워 재귀 알고리즘 중에 하노이 타워가 있습니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. [그림 3.1] 하노이 타워 이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다. 가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다. 규칙에 의해 1개의 돌을 A에서 C로 옮깁니다. 가정에 의해 B에 있는 n-1개의 돌을 A를 이용하..

[C언어 알고리즘] 3. 재귀 알고리즘 이번에는 재귀 알고리즘을 살펴봅시다. 재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용하여 해결하는 것을 말합니다. 수학에서 특정 명제가 참인지 증명하기 위해 명제를 이용하여 증명하는 방법과 같은 방식입니다. 예를 들어 "n!을 f(n)이라 할 때 n>1인 정수이면 n!은 n*f(n-1)이다."라는 명제를 증명하면 다음과 같이 증명할 수 있습니다. n-1일 때 위 명제가 참이라 가정하자. 가정에 의해 f(n-1) = (n-1)*(n-2)*...*3*2*1 이다. n*f(n-1) = n*(n-1)*(n-2)*...*3*2*1 = n! 이므로 위 명제는 참인 명제이다. 이처럼 자신을 이용하여 문제를 해결하는 방법을 재귀적 귀납법이라 하는데 이와 같은 방법으로..

[C언어 알고리즘] 2.6.3 쉘 정렬 알고리즘 소스 코드//쉘 정렬(Shell Sort) #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 int *origin; int on; void ShellSort(int *base, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; origin = arr; on = 10; ShellSort(arr, 10); return 0; } void InsertionSort2(int *base, int size, int step); void ViewArr(int *arr, int n); void ShellSort(int *base, int size..

[C언어 알고리즘] 2.6.2 쉘 정렬 알고리즘 구현쉘 정렬 알고리즘을 구현합시다. 쉘 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(step:=size/2; step>0 ; step:=step/2) 반복(i:=0; i0; step /= 2)//step의 폭을 1/2로 줄여간다. { 여기에서는 step에 따라 어떻게 배열 상태가 바뀌는지 출력하는 부분을 작성합시다. 만약 정렬 과정이 필요없다면 주석 처리하세요. printf("step:%d\n", step); 0, step, 2*step, ... 원소를 정렬한 후에 1, step+1, 2*step+1, ... 원소 정렬합니다. 이와 같은 작업을 step-1, 2*step – (step-1), 3*step – (step-1), ....

[C언어 알고리즘] 2.6.1 쉘 정렬 알고리즘 성능 분석 쉘 정렬 알고리즘 성능을 분석합시다. 쉘 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(step:=size/2; step>0 ; step:=step/2) 반복(i:=0; i

[C언어 알고리즘] 2.6 쉘 정렬(Shell Sort) 알고리즘이번에는 반복 알고리즘 중에 쉘 정렬 알고리즘을 알아봅시다. 쉘 정렬 알고리즘은 삽입 정렬 알고리즘을 이용하는 정렬 방식입니다. 쉘 정렬은 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복합니다. 이 때 간격의 초기값은 배열의 크기/2이며 간격이 1일 때까지 1/2로 줄이면서 반복합니다. 쉘 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(step:=size/2; step>0 ; step:=step/2) 반복(i:=0; i

[C언어 알고리즘] 2.5.3 삽입 정렬 알고리즘 소스 코드//삽입 정렬(Insertion Sort) #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 void InsertionSort(int *base, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; InsertionSort(arr, 10); return 0; } void ViewArr(int *arr, int n); void InsertionSort(int *base, int n) { int i, j; ViewArr(base, n);//현재 상태 출력 for (i = 1; i0; j--) { if (base[j - 1]>..

[C언어 알고리즘] 2.5.2 삽입 정렬 알고리즘 구현 삽입 정렬 알고리즘을 구현합시다. 삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리) 반복(i:=1; i0 ; j:=j-1) 조건(compare (base [j-1], base [j]) < 0) temp: = base [j-1] base[j-1] = base [j] base[j] = temp 아니면 루프 탈출 //삽입 정렬(Insertion Sort) #include 먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다. #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 ..