현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

하노이탑 문제

athxue의 이미지
글쓴이: 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: 
프로그래밍 QnA
vacancy의 이미지

글쓴이: vacancy / 작성시간: 금, 2006/02/24 - 1:13오후

점화식 푸는 거랑 비슷하다고 보시면 됩니다.
수학적 귀납법 -_-a 류랄까 ;;

solution(1) = alpha
solution(n) = solution(n-1) + beta

1개를 옮기는 방법을 안다는 가정 하에,
적어주신 3줄짜리 방법에 의해
'n-1 개를 옮길 수 있다면 n 개를 옮길 수 있다.' 라는 거죠.

오호라의 이미지

글쓴이: 오호라 / 작성시간: 금, 2006/02/24 - 1:20오후

우선 준비물이 필요합니다.

젓가락 3개. 색색씨디 3장( 색종이로 대체가능, 단 주의가 필요함)

한쪽에는 이재규씨의 책을, 다른 한쪽에는 젓가락에 씨디를 꽂아서 하노이의 탑을...

소스를 한줄한줄 보시면서 실제로 씨디를 옮겨보세요. 약간은 유치하고, 어설풀 것같지만...

실제로도 그렇습니다.

그러나, 효과는 만점입니다.

그리고, 다시 한번 해보세요.

이번에는 소스를 읽으면서 종이에 트리를 그려보세요.

트리를 그리시다보면 요넘이 터미날(자식없는 노드)까지 내려갔다. 올라갔다. 내려갔다...하면서 완전이진트리를 만들겁니다.

그리고, 각각 노드에 전달되는 파라미터값을 적어보시면 아시겠지만. 중복되는 파라미터값을 가지는 노드가 생겨납니다.

요기서 동적 계획법( Dynamic Progmming )으로 넘어갑니다. 요는, 함수의 내용은 변하지 않고, 파라미터값만 계속적으로 바꾸는 형태가 재귀적 호출( Recursive Function )인데...

여기서 문제가 들어갑니다. 구구단 2단 외우고, 3단 외울때 2단을 다시 외우나요?! 아니죠. 함수도 한번 수행했던 함수를 또 수행하지는 않죠. 요는 요거입니다.

노드를 보면 중복되는 노드가 있습니다. 요넘을 줄이면 계산량이 줄어든다 이거죠. 이게 동적계획법의 맥입니다...

그리고, 재귀호출을 비재귀호출로 바꾸는 방법은 LOOP를 쓰시던지, 스택을 이용하셔야 합니다. 책에는 LOOP만 나와있는데 개인적으로는 스택을 쓰실것을 추천합니다. 추가적인 자료구조 ( Data Structure ) 들어가지만...

프로그래머가 컨트롤(스택)할수 있다는 점이 강력합니다.

Stack based 최적화의 기회가 주어집니다.

※ Binary tree search ( 이진트리 검색 )에서 preorder (전위), inorder(중위), postorder(후위) 탐색을 같이 보심이 견문을 넓히시는 도움이...

= 이 내용을 너무 믿으시면 스킬에 해롭습니다. =

Hello World.

eezen의 이미지

글쓴이: eezen / 작성시간: 금, 2006/02/24 - 1:28오후

athxue wrote:
이재규님의 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를 실행하고 끝나고 이런식인가요?


N이 2보다 큰 경우에는 a와 c가 단번에 할 수 없는 일이 됩니다. a를 하기 위해서는 
a.a N-2개를 3번 기둥으로 옮긴다.
a.b 1개를 2번 기둥으로 옮긴다.
a.c N-2개를 2번 기둥으로 옮긴다.

는 식의 하위 과정이 필요하고
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개를 한번에 옮긴다거나 하는 일은 일어나지 않습니다)

athxue의 이미지

글쓴이: athxue / 작성시간: 금, 2006/02/24 - 1:52오후

eezen wrote:
athxue wrote:
이재규님의 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를 실행하고 끝나고 이런식인가요?


N이 2보다 큰 경우에는 a와 c가 단번에 할 수 없는 일이 됩니다. a를 하기 위해서는 
a.a N-2개를 3번 기둥으로 옮긴다.
a.b 1개를 2번 기둥으로 옮긴다.
a.c N-2개를 2번 기둥으로 옮긴다.

는 식의 하위 과정이 필요하고
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개를 한번에 옮긴다거나 하는 일은 일어나지 않습니다)

Quote:
a.a N-2개를 3번 기둥으로 옮긴다.
a.b 1개를 2번 기둥으로 옮긴다.
a.c N-2개를 2번 기둥으로 옮긴다.

N-2때 기둥의 위치가 바뀌는데 재귀적으로 될때 이 기둥이
바뀌는게 이해가 안가네요.. 머리가 딸리나 봅니다..
기둥이 바뀌는거를 어떻게 이해 해야 할까요??

Quote:
a.기둥 1에서 N-1개의 원반을 기둥 2로 이동
b.기둥 1에서 1개의 원반을 기둥 3으로 이동
c.기동 2에서 N-1개의 원반을 기둥 3으로 이동

a.a N-2개를 3번 기둥으로 옮긴다.
a.b 1개를 2번 기둥으로 옮긴다.
a.c N-2개를 2번 기둥으로 옮긴다.

athxue의 이미지

글쓴이: athxue / 작성시간: 금, 2006/02/24 - 5:12오후

원반 6개일때 가정해서 하는거는 이제 알겠어요. 근데 이걸
어떻게 재귀적으로 정립할수 있었는지 정말 이해가 안가는군요.

helloneo의 이미지

글쓴이: helloneo / 작성시간: 금, 2006/02/24 - 5:52오후

원반 6개 기둥1에서 기둥3으로 옮긴다는것은..

원반 5개를 기둥 2로 일단 옮겨놓고.. 젤 바닥원반을 기둥3으로 옮기고..
중간에 있던 5개를 기둥 3으로 옮겨놓으면 되죠..?

근데 원반 5개를 기둥 2로 옮기기 위해서..
우선 원반 4개를 기둥 3으로 옮기고 마지막원반을 기둥 2로 옮기고..
기둥3에 있던 원반을 다시 기둥2로 옮겨야하죠..?

근데 원반 4개를 기둥 3으로 옮기기 위해선..
우선 원반 3개를 기둥 2로 옮기고.. ..
...
...

이런식으로 재귀적으로 들어가는거죠.. ;

WHAT'S UP

athxue의 이미지

글쓴이: athxue / 작성시간: 금, 2006/02/24 - 7:25오후

역시 이 재미에 컴 공부 합니다.

재귀로 풀어도 이렇게 어려운걸 또 비재귀로 스택을 이용해 풀어놨더라고요
역시 대단한 분이 많으신거 같습니다.

그나저나 kldp BBS에서 어떤 글은 아이디가 있어야 답글을 달수있고
어떤건 없어도 달 수 있는데 제가 정할수 있는건가요? 아님 게시판에
따라 다른가?

이한길의 이미지

글쓴이: 이한길 / 작성시간: 금, 2006/02/24 - 8:04오후

비재귀라...

제가 예전에 대학교 2학년때 아직 비 재귀를 제대로 이해하지 못하고 있던 때...
교수님이 이거 풀어오면 플러스 점수 준다길래... 스택에다가 풀어간 기억이 있습니다.. 그땐 그게 최선이라 생각했는데... 나중에 재귀를 배우면서 보니까.. 아.. 저럴수도 있겠구나 싶더라구요...

암튼 하노이.. 에는 잼있는 추억이 있지요.. ^^;;

----
먼저 알게 된 것을 알려주는 것은 즐거운 일이다!
http://hangulee.springnote.com
http://hangulee.egloos.com

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.