DataStructure (2) 썸네일형 리스트형 [자료구조] 재귀 - 하노이 타워 (The Tower of Hanoi) 하노이 타워는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다. 하노이 타워 문제는 '하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법'에 관한 것이다. 다음 제약 조건을 만족하면서 A의 원반을 C로 옮겨야 한다. 원반은 한 번에 하나씩만 옮길 수 있다. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다. 이를 해결하기 위한 과정은 3가지가 있다. 작은 원반 n-1개를 A에서 B로 이동 큰 원반 1개를 A에서 C로 이동 작은 원반 n-1개를 B에서 C로 이동 + 여기에 탈출조건이 더해져야 한다. => 이를 재귀적으로 활용하면 하노이타워 문제를 해결할 수 있다. #include void HanoiTowerMove(int num, char from, char by, char t.. [자료구조] 시간복잡도(time complexity)와 공간복잡도(space complexity) #시간복잡도(time complexity) : 알고리즘을 프로그램으로 실행하여 완료하기까지 소요되는 시간(속도) : 컴파일타임과 런타임의 합 1) Big-Oh 표기법 "n>=0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) =0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) >= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 Big-Omega는 Ω(g(n))이다." 즉, 시간의 하한선을 표현한다. (best case) 해당 알고리즘은 Big-Omega보다 빠를 수 없다. Ω(2ⁿ) < Ω(n³)< Ω(n²) 이전 1 다음
