하노이탑 문제
글쓴이: athxue / 작성시간: 금, 2006/02/24 - 12:44오후
이재규님의 C로 배우는 알고리즘이라는 책을 보고 있습니다.
하노이탑 문제풀이에 관해 재귀적으로 정의를 해 놓았는데
읽으면 읽을수록 아 이거다 느낌이 아니고 완전 뜬 구름 잡고
있는 상태입니다.
Quote:
a.기둥 1에서 N-1개의 원반을 기둥 2로 이동
b.기둥 1에서 1개의 원반을 기둥 3으로 이동
c.기동 2에서 N-1개의 원반을 기둥 3으로 이동
이걸 단순히 말로만 보게되면 5개의 원반중 4개를 2번째 기둥
으로 옮기고 마지막껄 3번째 기둥으로 옮긴다음 나머지 4개를
3번째 기둥으로 옮기면 끝.. 이긴 한데, 이걸 재귀적으로 이해
해야 하는데 도대체 무슨 말인지를 모르겠습니다. 솔직히
이런 심정입니다. 차라리 원반 5개를 한번에 다 들고 3번으로
옮겨라! ㅠㅠ
재귀적으로 이해하려면 일단 1번에서 원반의 수가 1개가 될때
까지 계속 처음으로 반복되다가 1개가 되면 b를 실행하고 c를
실행한 다음 끝나고, 원반 2개일때로 가서 다시 b를 실행하고
c를 실행하고 끝나고 이런식인가요?
Forums:
점화식 푸는 거랑 비슷하다고 보시면 됩니다.수학적 귀납법 -_-a 류
점화식 푸는 거랑 비슷하다고 보시면 됩니다.
수학적 귀납법 -_-a 류랄까 ;;
solution(1) = alpha
solution(n) = solution(n-1) + beta
1개를 옮기는 방법을 안다는 가정 하에,
적어주신 3줄짜리 방법에 의해
'n-1 개를 옮길 수 있다면 n 개를 옮길 수 있다.' 라는 거죠.
우선 준비물이 필요합니다.젓가락 3개. 색색씨디 3장( 색종이로
우선 준비물이 필요합니다.
젓가락 3개. 색색씨디 3장( 색종이로 대체가능, 단 주의가 필요함)
한쪽에는 이재규씨의 책을, 다른 한쪽에는 젓가락에 씨디를 꽂아서 하노이의 탑을...
소스를 한줄한줄 보시면서 실제로 씨디를 옮겨보세요. 약간은 유치하고, 어설풀 것같지만...
실제로도 그렇습니다.
그러나, 효과는 만점입니다.
그리고, 다시 한번 해보세요.
이번에는 소스를 읽으면서 종이에 트리를 그려보세요.
트리를 그리시다보면 요넘이 터미날(자식없는 노드)까지 내려갔다. 올라갔다. 내려갔다...하면서 완전이진트리를 만들겁니다.
그리고, 각각 노드에 전달되는 파라미터값을 적어보시면 아시겠지만. 중복되는 파라미터값을 가지는 노드가 생겨납니다.
요기서 동적 계획법( Dynamic Progmming )으로 넘어갑니다. 요는, 함수의 내용은 변하지 않고, 파라미터값만 계속적으로 바꾸는 형태가 재귀적 호출( Recursive Function )인데...
여기서 문제가 들어갑니다. 구구단 2단 외우고, 3단 외울때 2단을 다시 외우나요?! 아니죠. 함수도 한번 수행했던 함수를 또 수행하지는 않죠. 요는 요거입니다.
노드를 보면 중복되는 노드가 있습니다. 요넘을 줄이면 계산량이 줄어든다 이거죠. 이게 동적계획법의 맥입니다...
그리고, 재귀호출을 비재귀호출로 바꾸는 방법은 LOOP를 쓰시던지, 스택을 이용하셔야 합니다. 책에는 LOOP만 나와있는데 개인적으로는 스택을 쓰실것을 추천합니다. 추가적인 자료구조 ( Data Structure ) 들어가지만...
프로그래머가 컨트롤(스택)할수 있다는 점이 강력합니다.
Stack based 최적화의 기회가 주어집니다.
※ Binary tree search ( 이진트리 검색 )에서 preorder (전위), inorder(중위), postorder(후위) 탐색을 같이 보심이 견문을 넓히시는 도움이...
= 이 내용을 너무 믿으시면 스킬에 해롭습니다. =
Hello World.
Re: 하노이탑 문제
N이 2보다 큰 경우에는 a와 c가 단번에 할 수 없는 일이 됩니다. a를 하기 위해서는
는 식의 하위 과정이 필요하고
c를 위해서도 역시 같은 과정이 필요하게 됩니다.
N이 3보다 크면
a.a와 a.c도 한번에 할 수 없는 일이 되어서 .....
a.a.a a.a.b a.a.c / a.c.a a.c.b a.c.c 의 과정이 필요하게 됩니다.
(혹시나 해서 적지만 하노이탑에서는 한번에 하나의 원반만 옮길 수 있고 작은 원반은 항상 큰 원반 위에 있어야 하므로 4개를 한번에 옮긴다거나 하는 일은 일어나지 않습니다)
Re: 하노이탑 문제
N-2때 기둥의 위치가 바뀌는데 재귀적으로 될때 이 기둥이
바뀌는게 이해가 안가네요.. 머리가 딸리나 봅니다..
기둥이 바뀌는거를 어떻게 이해 해야 할까요??
이제 하노이탑가져다가 하는거는 알겠는데ㅠㅠ
원반 6개일때 가정해서 하는거는 이제 알겠어요. 근데 이걸
어떻게 재귀적으로 정립할수 있었는지 정말 이해가 안가는군요.
원반 6개 기둥1에서 기둥3으로 옮긴다는것은..원반 5개를 기둥
원반 6개 기둥1에서 기둥3으로 옮긴다는것은..
원반 5개를 기둥 2로 일단 옮겨놓고.. 젤 바닥원반을 기둥3으로 옮기고..
중간에 있던 5개를 기둥 3으로 옮겨놓으면 되죠..?
근데 원반 5개를 기둥 2로 옮기기 위해서..
우선 원반 4개를 기둥 3으로 옮기고 마지막원반을 기둥 2로 옮기고..
기둥3에 있던 원반을 다시 기둥2로 옮겨야하죠..?
근데 원반 4개를 기둥 3으로 옮기기 위해선..
우선 원반 3개를 기둥 2로 옮기고.. ..
...
...
이런식으로 재귀적으로 들어가는거죠.. ;
WHAT'S UP
이제야 이해 됐어요
역시 이 재미에 컴 공부 합니다.
재귀로 풀어도 이렇게 어려운걸 또 비재귀로 스택을 이용해 풀어놨더라고요
역시 대단한 분이 많으신거 같습니다.
그나저나 kldp BBS에서 어떤 글은 아이디가 있어야 답글을 달수있고
어떤건 없어도 달 수 있는데 제가 정할수 있는건가요? 아님 게시판에
따라 다른가?
비재귀라...제가 예전에 대학교 2학년때 아직 비 재귀를 제대로
비재귀라...
제가 예전에 대학교 2학년때 아직 비 재귀를 제대로 이해하지 못하고 있던 때...
교수님이 이거 풀어오면 플러스 점수 준다길래... 스택에다가 풀어간 기억이 있습니다.. 그땐 그게 최선이라 생각했는데... 나중에 재귀를 배우면서 보니까.. 아.. 저럴수도 있겠구나 싶더라구요...
암튼 하노이.. 에는 잼있는 추억이 있지요.. ^^;;
----
먼저 알게 된 것을 알려주는 것은 즐거운 일이다!
http://hangulee.springnote.com
http://hangulee.egloos.com
댓글 달기