하노이 탑 분석

[성대아싸]

2011.03.28 00:31:29

조회 6467 추천 2 댓글 5

세개의 기둥이 있고 원판을 모두 세번째 기둥으로 옮기는게 목표죠

근데 반드시 큰것 위에 작은 것이 올라가야 하죠

재귀적으로 생각한다는게 첨엔 어려운데

익숙해지면 이것만큼 쉬운게 없어요,

그냥 "이놈은 어떻게든 돌고나서 이걸 반환하겠지" 하는 거죠

자세하게 어떻게 돌까 고민할 필요 없죠

원판이 하나 있으면

그냥 옮기면 되요

원판 개수가 1 이면 이동 횟수는 1

이를 H(1) = 1 로 나타내봐요

원판이 1개 이상이면?

먼저 제일 밑에 있는 놈 제외하고

나머지를 전부 가운데기둥에다 옮겨요

H(n-1) 번

그 뒤 제일 밑에 있는 놈을 세번째 기둥으로 옮기죠

1 번

그 뒤 가운데 기둥에 있는 원판들을 세번째 기둥으로 올려요

H(n-1) 번

식으로 풀어 쓰면

H(n) = H(n-1) + 1 + H(n-1) = 2 * H(n-1) + 1

중간에 어떻게 옮겨갈지 고민 안해도 되요

"어떻게든 옴겨가겠지" 가 핵심이죠

식을 정리하면

H(1) = 1

H(n+1) = 2 * H(n) + 1

이고요

H(n+1) - 2 * H(n) = 1

로 두면

동차 점화식의 해가 Hh 일때

비동차 점화식의 해는 H = Hh + Hp

라고 할 수 있고

Hh 는 보조방정식이 (lambda - 2)

일반해 Hh(n) = c1(상수) * 2^n 이고요

Hp(n) = K(상수), Hp(n+1) = K

이니까

식에 대입하면

K - 2K = 1 , K = -1

그래서 H(n)을 구하면

H(n) = c1 * 2^n - 1

근데 초기조건에서 H(1) = 1 이므로

c1 = 1 , 성립하고요

최종

H(n) = 2^n - 1 번 움직임

시간 복잡도는 O(2^n)

exponential 하죠

위 해법은 그냥 비동차 점화식 엄충 간단하게 푼거에요

다만 좀더 복잡해지면, 특성방정식의 해가 허수가 나오고

진짜 구하기 어려워질때가 많아요

시간복잡도는 더 "압도" 하는 쪽을 더 중요시 해요

충분히 큰 데이터에서는 나머진 무시할 만큼 작기 때문이죠

따라서 저렇게 정확하게 구할 필요는 없음

시간복잡도를 알아내는 더 좋은 방법이 \'마스터 방법\' 이란게 있어요

이건 반드시 마스터 하시길...

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	흡연때문에 이미지 타격 입은 것 같은 스타는?	운영자	24/07/15	-	-
244794	우리 교수님 너무하네 진짜.. 구조체도 안나갔는데 성적관리..과제로내줌. [11]	ㅋ(110.5)	11.04.14	149	0
244792	vbs 3시간 동안 안풀리는 문제 질문좀ㅠㅠ [3]	ㄴㄴㄴㄴ(203.244)	11.04.14	72	0
244791	이문제 푸는 사람 천재 [4]	하오추다봉	11.04.14	152	0
244790	앞으로의 api전망이 어둡나요? [5]	왕똘복(59.25)	11.04.14	148	0
244789	닌텐도형 이것도좀 ㅋ [2]	개살버거	11.04.14	59	0
244788	오늘도 입갤임다~ [2]	카레맛카레	11.04.14	48	0
244787	자바 질문좀 [7]	자질(219.251)	11.04.14	59	0
244785	이바닥 취업난이도가 어떻습니까?	RK(175.205)	11.04.14	41	0
244784	개살버거야 [1]	닌텐도DS	11.04.14	53	0
244783	횽들 나 오늘부터 일찍잘거야.	SODmaster	11.04.14	50	0
244782	닌텐도형 쌩유 이것도 이상해..	개살버거	11.04.14	33	0
244781	쓰레드랑 GUI간에 대용량 데이터 통신이 필요하면 어떻게? [8]	ㅋ(58.232)	11.04.14	111	0
244780	조공이 없어서 그런가?? 답이 없길래 조공탑재 질문. 휴학문제 [5]	형들아(14.41)	11.04.14	155	0
244779	게살버거 보긔 [1]	닌텐도DS	11.04.14	47	0
244778	공부하다 또 질문 ㅋㅋ [2]	개살버거	11.04.14	48	0
244777	횽들 욕먹을 각오하고 숙제올려요 제발봐주세요 머리터지겠네요 [3]	말코형	11.04.14	78	0
244774	농협이 입은 가시적,비가시적 손실은 최소 1000억원	잏힝(61.255)	11.04.14	98	0
244773	논리회로에 대해 잘설명되있는 곳 없을까염ㅠㅠ...	뇌자알	11.04.14	72	0
244772	아싸 퇴근이다!!	McHello	11.04.14	42	0
244771	이번 사고로인해 IBM시스템에 대한 불신으로 사업접어야 것다. [3]	잏힝(61.255)	11.04.14	81	0
244770	지금 c++셤공부중이라...좀 알려주긔 형들. [16]	개살버거	11.04.14	101	0
244769	회사 나갈까 하는데 [8]	aa(121.50)	11.04.14	92	0
244768	pdf 파일 암호좀 풀어주세요 [3]	깨갱	11.04.14	83	0
244767	XML DTD 모르겠음....	조청	11.04.14	43	0
244766	나 오른손만 독수리타자인데 [5]	워너투비(121.172)	11.04.14	83	0
244765	닌텐도형 이거 아가 밑에꺼 못찾겟으 ㅠ.ㅠ [8]	개살버거	11.04.14	62	0
244764	한국 IBM은 망했스욬ㅋㅋㅋㅋ [1]	잏힝(61.255)	11.04.14	123	0
244763	비주얼C로 애플 앱 개발 가능하면 좋겠다. [2]	ByunJa	11.04.14	116	0
244761	익스플로러 징징글 다시 올립니다 ㅠㅠㅠㅠ	HelloKu	11.04.14	224	0
244759	[질문] google Docs 에서의 A4, A3, 등 페이지 설정.. [2]	AutuMn(58.149)	11.04.14	101	0
244758	아냐 그냥 찾지마 ㅎㅎㅎ	ㅔㅕㅅㄷㄱ	11.04.14	41	0
244756	물리엔진甲.txt [2]	응슷응(210.102)	11.04.14	190	0
244754	형들 오늘부터 일끝나고.. [3]	열라멋진놈	11.04.14	78	0
244753	힘들때 왜 EE 라고 외쳐? [7]	캐닭(211.248)	11.04.14	160	0
244752	님들 이거 칼라로 계산좀 [5]	ㅁㄵㅇ(125.7)	11.04.14	83	0
244751	컴퓨터, 프로그래밍, XML, 잡지, 그래픽, 자바, 안드로이드 팝니다.	123(125.129)	11.04.14	71	0
244750	아마게임만드는 사람 있는가 [9]	t(121.143)	11.04.14	169	0
244749	구조체 변수의 내용을 파일로 출력할려면? [7]	뽀샤시(175.205)	11.04.14	158	0
244748	프갤에 새로 들어온 사람입니다 [8]	워너투비(121.172)	11.04.14	89	0
244747	형들 형들이 4학년 2학기에 휴학을 한다고 쳐봐. 그럼 뭐할래? [4]	형들아(14.41)	11.04.14	202	0
244746	프로그래밍 용자님들아 제발 도와주세요 [9]	HelloKu	11.04.14	84	0
244744	C언어기본문법 과제/질문 받습니다. [7]	닌텐도DS	11.04.14	97	0
244743	C언어 질문 받아줌 [26]	ㅁㅁ(220.116)	11.04.14	161	0
244742	이거 간단한건데 실행하면 한자가나와요..ㅠㅠ [9]	123123(122.34)	11.04.14	65	0
244741	dynasys.kr 리뉴얼 했다능 [2]	분당살람	11.04.14	64	0
244740	c++ 기초적인거 헷갈리는데 좀 알려주세요.. [8]	개살버거(122.34)	11.04.14	64	0
244739	어제부터 플갤을 눈팅중인데.. [3]	ByunJa	11.04.14	82	0
244738	형들아 칭구들이 슛이 약하다고 축구 안껴줌 [3]	듣보킹	11.04.14	118	0
244736	xmlhttp 관련해서 전혀 모르겠음.. [1]	ASP 초보..(203.173)	11.04.14	198	0
244735	컴프갤러들은 보통 어떤 순으로 공부함요? [5]	ㅁㅁ(220.116)	11.04.14	74	0