[C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드 [C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드//Program.c #include #include void Hanoi(const char *src, const char *use, const char *dest, int n) { if(n 언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어) 2016.11.30
[C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 [C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 하노이 타워 알고리즘을 구현합시다. 알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다. void Hanoi(const char *src, const char *use, const char *dest, int n) { 만약 돌이 없으면 아무 것도 수행하지 않고 함수를 종료합니다. 즉 탈출 조건입니다. if(n 언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어) 2016.11.30
[C언어 알고리즘] 3.2.1 하노이 타워 알고리즘 성능 분석 [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언어) 2016.11.30
[C언어 알고리즘] 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언어) 2016.11.30
[디딤돌 자료구조와 알고리즘 with C] 3.2 하노이 타워 3. 2 하노이 타워 재귀 알고리즘 중에 하노이 타워가 있습니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. [그림 3.1] 하노이 타워 이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다.가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다.규칙에 의해 1개의 돌을 A에서 C로 옮깁니다.가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다.따라서.. 언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘 2016.04.10
6.1 하노이 타워 [디딤돌 자료구조와 알고리즘 with C++] 6.1 하노이 타워 하노이 타워는 대표적인 재귀 알고리즘입니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. 이 문제를 재귀적으로 해결하면 다음처럼 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다. 가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다. 규칙에 의해 1개의 돌을 A에서 C로 옮깁니다. 가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다. 따라서 n개의 돌을 옮길 수 있습니다. 의.. 언어 자료구조 알고리즘/[C++]디딤돌 자료구조와 알고리즘 2016.04.04
