프로그래머스 hanoi 문제

접근 방식(알고리즘 분류)

• 재귀

내 풀이

result = []

def hanoi(n, start, end, mid):
    global result

    # 옮기는 블럭이 1개일때까지
    if n == 1:
        result.append([start, end])
    else:
        hanoi(n-1, start, mid, end)
        result.append([start, end])
        hanoi(n-1, mid, end, start)
    return result

def solution(n):
    global result
    hanoi(n, 1, 3, 2)
    return result

풀이 설명

• 큰 덩어리가 작은 덩어리로 나뉘지만 덩어리 마다 하는 작업은 똑같다.
• 재귀를 단순 반복문으로 생각하기 보다는 일정한 규칙이 찾은 부분에서 똑같이 수행될때 재귀를 이용해야 된다

느낀점

• dfs와 백트래킹할때의 재귀랑은 약간 느낌이달랐다.
• 피보나치 수열과 비슷한 느낌이다.
• 나중에 한번더 보면 좋을거 같다.