언제나 휴일

[C언어 알고리즘] 3.1 탈출 조건 재귀 알고리즘으로 문제를 해결할 때 주의해야 할 점은 탈출 조건입니다. 재귀 알고리즘으로 문제를 해결할 때는 재귀 호출을 수행하기 이전보다 탈출 조건에 근접하다는 것을 증명할 수 있어야 합니다. 만약 이를 증명하지 못하면 영원히 문제를 해결하지 못할 수 있습니다. 예를 들어 n!를 구하는 알고리즘을 f(n)이라고 할 때 n이 0 이하일 때는 오류를 반환하고 1일 때는 1을 반환하게 해야 합니다. 이와 같이 하면 재귀 호출하기 전보다 n 값이 1이 줄어들어 탈출 조건에 근접합니다. 만약 탈출 조건을 작성하지 않으면 무한 재귀로 스택 오버 플로우가 발생합니다. Factorial(n) 조건 n

[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를 교환 이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 ..

[C언어 알고리즘] 2.5.1 삽입 정렬 알고리즘 성능 분석 삽입 정렬 알고리즘 성능을 분석합시다. 삽입 정렬(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 아니면 루프 탈출 n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다. T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1)..

[C언어 알고리즘] 2.5 삽입 정렬(Insertion Sort) 알고리즘이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다. 삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다. 삽입 정렬(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 아니면 루프 탈출 예: 정렬 전: 10 9 2 11 19 1.1회전: 9 1..