하노이의 탑

👉 사용 언어 : PYTHON3

 

✅ Solution

def hanoi(start, end, temp, num):
    if num == 1:
        return [[start, end]]
    if num > 1:
        return hanoi(start, temp, end, num-1) + [[start, end]] + hanoi(temp, end, start, num-1)
def solution(n):
    return hanoi(1, 3, 2, n)

 

👉 문제 설명 및 제한 사항

• 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여있다.
• 기둥의 개수는 3개 : 1번, 2번, 3번 기둥
• 게임의 목적 : 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것
  • 한 번에 하나의 원판만 옮길 수 있습니다.
  • 큰 원판이 작은 원판 위에 있어서는 안됩니다.
• 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나❗️
• 매개변수 : 1번 기둥에 있는 원판의 개수 n
  • n : 15이하 자연수
• 리턴값 : n개의 원판을 3번 원판으로 최소로 옮기는 방법 을 return > 2차원 배열

👉 아이디어

• 하노이 탑을 옯기려면 원반을 모두 (2^n) -1 번만큼 옮겨야 한다.
• n이 커지면 -1은 큰 의미가 없으므로 하노이탑 알고리즘의 계산 복잡도 는 O(2n)으로 표현할 수 있다.
• 케이스를 나누면 다음과 같다.
  1. 원반이 1개 : 그 1개만 3번 기둥으로 옮기면 끝이다. (= 종료 조건)
  2. 원반이 n개 
     1. (1) 1번 기둥의 n개 원반 중 n-1개를 2번 기둥으로 옮긴다.
     2. (2) 1번 기둥에 남아있는 가장 큰 원반 1개를 3번 기둥으로 옮긴다.
     3. (3) 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮긴다.
• 조건문으로 원반 개수(= n)가 1개일 경우와 1개 이상일 경우로 나누어 실행문을 작성한다.
• 즉, 점화식(= 재귀호출)은 아래와 같이 표현 가능하다.
  • (1) hanoi(start, temp, end, num-1)
  • (2) [[start, end]]
  • (3) hanoi(temp, end, start, num-1)

✅ 다른 사람 풀이 참고

 

: 위의 풀이와 유사함.

 

👉 깨달은 것 / 알게된 것

• 하노이탑 알고리즘의 계산(시간) 복잡도가 O(2n)이라는 것을 알게 되었다.
• 2개의 케이스에 대해 원반을 옮기는 공식을 재귀 호출로 적용하여 구현할 수 있다.
  • 규칙을 찾아서 점화식을 먼저 구해야 해당 점화식을 알고리즘을 적용하여 문제를 쉽게 풀이할 수 있다.

✅ 참고

• https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91
• https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91