(Week2)[재귀] 하노이의 탑

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 15분 (풀었던 문제)

1. 문제 설명

https://programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

하노이의 탑 N번을 수행할 때, 얼마나 움직여야하는 지 구하는 문제

2. 접근 방식

• 전형적인 재귀 문제라고 생각한다.
• Start, Goal, Assist의 역할을하는 기둥이 n이 바뀔 때마다 
• 재귀이다보니 이해가 직관적으로 안 돼서 보통 공식을 외워서 문제를 풀었었다. [hanoi (1, 3, 2) , (a, c, b), (c, b, a)]
• 스터디를 진행하면서 제일 밑에 있는 n번째 기둥을 먼저 Goal 기둥에 옮겨놓고 시작한다고 생각하니 이해가 쉬웠다. 

3. 코드

def solution(n):
    answer = []
    def hanoi(n, a, b, c): # (n, start, goal, assist)
        if n == 1:
            answer.append([a, b])
            return
        else:
            hanoi(n-1, a, c, b)
            answer.append([a, b])
            hanoi(n-1, c, b, a)
    hanoi(n, 1, 3, 2)
    return answer

4. 코멘트

• 재귀는 확실히 이해하기가 조금 어려운 것 같다...조금 더 알고리즘 공부를 하거나 손으로 그려보는 방법이 제일 직관적으로 이해하기는 쉬운 듯 싶다.
• 그래도 스터디를 하면서 내가 생각하지 못했던 접근 방식을 생각해 볼 수 있게 되어서 좋다.