[알고리즘] 순환 알고리즘 Recursion / 하노이 탑

순환 알고리즘 (recursive algorithm)

• 직접순환(direct recursion), 간접순환(indirect recursion)
• 간결하고 명확 but, 일반적으로 수행속도 및 기억장소 사용에 비효율적이다.
• 순환(recursion) vs 반복(iteration) 

 

순환 알고리즘의 적용 예

• Factorial : n! = n * (n-1)! = n*(n-1)*...*2*1
• Fibonacci 수열 : 1, 1, 2, 3, 5, 8, 13, 21, ....
• BNF(Backus Naur Form) 
• 합계 계산(SUM) 
• 정렬, 탐색, 트리 문제 등 다양한 경우에 실제 적용된다. 

 

순환 알고리즘의 복잡도 

• 순환 알고리즘의 일반적인 단계
  • 분할, 정복, 결합 단계
• 순환 방정식(recurrence equation) 이용 
  • 예) 하노이 타워, T(n) = 2*T(n-1) + 1
  • 예) Merge_Sort, T(n) = 2*T(n/2) + O(n) – 예제 분석
• 주요 해법
  • 대입법 - 까다로움
  • 반복법 - 많이 사용
  • 일반법

 

Hannoi Tower 하노이 타워 문제 

10개의 원반을 A에서 C로 모두 옮기기

조건
1. 원반은 한번에 한 개씩 옮길 수 있다. 
2. 큰 원반이 작은 원반 위에 올라가서는 안된다.

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) 
{
	if (n == 1)
	{ 
		cout << "Move "<< A << " to " << C << endl;
	}
	else 
	{
		hanoi(n - 1, A, C, B);
		cout <<"Move "<< A << " to " << C << endl;
		hanoi(n - 1, B, A, C);
	}
}

int main(void)
{
	int n = 10; //원반 수
	char A = 'A', B = 'B', C = 'C';
	hanoi(n, A, B, C);

}