언제나 휴일

[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.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++ 무료 동영상 강의]17. 정적(static) 멤버 다루는 내용static,정적 멤버의 특징,정정 멤버를 사용하는 예, 정적 멤버 주의할 점 앞으로 프로그래밍 관련 글은 새롭게 개설한 언제나 휴일 전용 사이트에서 만나보세요. 2017년 1월 1일까지 이 곳의 프로그래밍 자료는 http://ehpub.co.kr 로 옮길 예정입니다. 본문[디딤돌 C++] 17. 정적(static) 멤버

[C++ 무료 동영상 강의]16. 생성자, 소멸자 (Part3, 복사 생성자)다루는 내용복사 생성자,얕은 복사,깊은 복사, 복사 생성자를 개발자가 작성해야 할 때 앞으로 프로그래밍 관련 글은 새롭게 개설한 언제나 휴일 전용 사이트에서 만나보세요. 2017년 1월 1일까지 이 곳의 프로그래밍 자료는 http://ehpub.co.kr 로 옮길 예정입니다. 본문[디딤돌 C++] 16. 생성자, 소멸자

[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