Master 펭귄
Limitless
Master 펭귄
전체 방문자
오늘
어제
  • 분류 전체보기 (16)
    • NLP (1)
    • Algorithm (9)
      • Mathematics (1)
    • Work Experience (5)
      • Python TA (1)
      • ETRI Intern (4)
    • Others (0)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • 자동번역
  • Quickselect
  • 파이썬
  • 선택알고리즘
  • 자동통역기
  • NLP #BERT #ROBERTA #PRETRAINING
  • 백준출력초과에러
  • 알고리즘 #에라토스테네스의 체 #소수 구하기 #파이썬
  • BFS #백준1697 #파이썬 #알고리즘
  • 데이터구축
  • 하노이탑파이썬
  • 셀레니움
  • 하노이탑이동횟수
  • 알고리즘 #백준알고리즘
  • 백준11004번
  • 하노이탑알고리즘
  • 하노이탑 #백준11729번
  • 인턴
  • 업무자동화
  • 하노이탑알고리즘 #알고리즘

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Master 펭귄
Algorithm

[분할정복] 하노이탑 알고리즘

[분할정복] 하노이탑 알고리즘
Algorithm

[분할정복] 하노이탑 알고리즘

2020. 7. 28. 15:24

1. 들어가며


재귀 알고리즘 중에 유명한 하노이탑 알고리즘을 이해해보겠습니다.

혼자서 오랜 고민 끝에 이해가 잘 되지 않아 유투브 영상과 블로그를 참고하여 이해했습니다!

 

2. 문제 소개


하노이 탑은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로, 아래 그림을 보시면 익숙할 것이라고 생각이 듭니다. 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수 없으며, tower 1에 있던 모든 원반이 tower 3으로 이동을 시키는 문제입니다. 

 

3. 아이디어


어떻게 정의해야할지 잘 떠오르지 않아서 실제로 원반을 하나씩 옮겨보았습니다.

문제를 작게 만드어 해결하고 이후에 확대하는 방법이 알고리즘 문제를 푸는데 도움이 될 수 있습니다.

 

일단 3개의 원반을 A에서 C로 이동을 한다고 가정합니다.

 

친절하게 설명이 되어있는 블로그를 참조했습니다.

세개을 원반을 이동할 때 얻을 수 있는 아이디어 세 가지가 있습니다.

 

1. 원반이 한 개 일때는 그냥 목표지점으로 이동을 하고 끝난다. 

2. 가장 큰 마지막 원반이 목표 지점에 도달하게 되면 그 원반을 더 이상 이동을 하지 않는다.

3. 시작과 목표 원반이 아닌 보조원반에 가장큰 원반을 제외하고 모든 원반이 이동이 되는 과정이 있다.

->이 때 재귀 함수를 사용할 수 있다. 재귀함수에서 시작지점의 원기둥을 바꾸는 조작이 필요하다. 

 

4. Pseudo Code


 

def hanoi(원반개수, 시작, 끝, 보조)

	if 원반이 하나일 때:
            #시작에서 끝으로 한 번 이동시킨다.
            print(시작, 끝)
            return 

  	else:
            #원반개수-1만큼 보조 원기둥으로 이동시켜야한다
            hanoi(원반개수-1, 시작, 보조, 목표)
            #이동시킨다.
            print(시작, 보조)

            #보조 원기둥에 있는 원반을 목표 원기둥으로 이동시켜야 하기 때문에 보조기둥을 시작기둥으로 변경한다. 
            hanoi(원반개수-1, 보조, 목표, 시작)

 

5. 간단 설명정리


 

하노이 탑 알고리즘은 3단계로 요약할 수 있습니다.

 

1. 원반(n)이 한 개일 때는 시작에서 목표로 간다.

2. n>1 일 때는 마지막 원반을 제외한 n-1 개의 원반을 보조기둥으로 옮긴다.

(+ 마지막원반은 (1)에 따라 목표기둥으로 이동한다)

3. n-1개의 원반을 목표기둥으로 옮긴다. 

 

이 세 가지만 염두한다면 하노이 탑 알고리즘을 이해하는데 도움이 될 것 같습니다ㅎㅎ

 

 

 

6. 출처


https://shoark7.github.io/programming/algorithm/tower-of-hanoi

https://www.youtube.com/watch?v=FYCGV6F1NuY

'Algorithm' 카테고리의 다른 글

[완전탐색] 백준 1476번: 날짜 계산  (0) 2021.01.01
[선택] 백준 11004번 K번째 수 시간초과 에러  (0) 2020.08.04
[분할정복] 백준 11729번 출력초과 에러 해결방법  (0) 2020.07.28
[분할정복] 백준 11729번 하노이탑 파이썬 풀이  (0) 2020.07.28
알고리즘 공부 시작!  (0) 2020.07.28
  • 1. 들어가며
  •  
  • 2. 문제 소개
  • 3. 아이디어
  • 4. Pseudo Code
  • 5. 간단 설명정리
  • 6. 출처
'Algorithm' 카테고리의 다른 글
  • [선택] 백준 11004번 K번째 수 시간초과 에러
  • [분할정복] 백준 11729번 출력초과 에러 해결방법
  • [분할정복] 백준 11729번 하노이탑 파이썬 풀이
  • 알고리즘 공부 시작!
Master 펭귄
Master 펭귄
대학원생 뒤뚱뒤뚱 생존 일기

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.