99클럽 코테 스터디 7일차 TIL + 하노이의 탑(재귀)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "하노이의 탑" 문제를 풀었다.
- 학부생 때 배웠던 하노이의 탑, 재귀로 풀었던 건 기억이 났지만 그밖의 다른 건 기억이 삭제된 상태였다.^^;;
- 이것도 나름의 수학 공식이 존재하기 때문에 대학 교재를 참고했다.

[나의 코드]

def solution(n):
    answer = []
    
    def hanoi(n, start, end):
        if n == 1:
            answer.append([start, end])
            return
        
        hanoi(n - 1, start, 6 - start - end)
        answer.append([start, end])
        hanoi(n - 1, 6 - start - end, end)
    
    hanoi(n, 1, 3) 
    return answer

① 맨 아래 있는 가장 큰 원판이 다른 원판의 위로 올라올 수 없으므로 n - 1개의 원판을 보조 기둥(두 번째)으로 옮긴다.
② 첫 번째 기둥의 원판을 세 번째 원판으로 옮긴다.
③ 두 번째 원판에서 n - 1개를 마지막 판으로 다시 옮긴다.

이 개념을 알고 있어야 풀린다.
원판이 하나 밖에 없을 땐 경우의 수가 늘 1이니까 이를 종료 조건으로 잡아주었다.

참고로 수학 공식에 대한 설명을 덧붙이자면 6 - start - end 는 남은 보조 기둥의 위치를 뜻한다.
여기서 6은 기둥 번호의 총합이다. (1 + 2 + 3)
수학 공식을 모르면 매개변수를 하나 더 추가하면 된다. (n, start, end, aux) 이렇게 하면 된다. 

[오늘의 회고]
- 아~ 내가 싫어하는 하노이 탑 문제였다. 기본기가 중요하다는 느낌이 들었다. 
- 아마 다른 사람들도 나랑 코드가 똑같을 것 같다. 끝!