프로그래머스__[문제풀이: lv3. 하노이의 탑(feat. 재귀함수)]

Jaewon Lee·2021년 8월 16일
0

Algorithm

목록 보기
35/36
post-thumbnail

On.


Algorithm


1. 수도코드

0) 문제 유형 파악: 하노이의 탑 처럼 비슷한 동작을 반복하는 것들은 재귀함수로 푼다!

  • 출발지의 가장 밑에 있는 판이 도착지의 가장 밑으로 이동하려면, 출발지에서 가장 밑의 판을 제외한 나머지 판들이 전부 보조에 있어야한다.
  • 재귀 함수 문제는 잘게 쪼개서 제일 작은 사이즈 부터 그려보며 규칙을 파악하는 것이 좋다.
  • 규칙을 찾았으면 식이든, 순서든 일반화를 시킨다.
  • 근데 그게 잘 안되니까 연습하자...ㅎㅎ

1) 출발지에 있는 판중에 가장 밑에 있는 판을 제외한 나머지 판들을 보조에 놓는다. (재귀함수)

  • 재귀함수가 돌면서 출발지에 있던 가장 밑의 판을 제외한 나머지 판들이 보조에 차례로 쌓이는 작업이 수행된다.
  • 그림 설명

2) 가장 밑 판을 도착지에 놓는다. (answer에 추가)

  • 그림 설명

3) 보조에 있는 판들을 도착지에 옮긴다. (재귀함수)

  • 재귀함수가 돌면서 보조에 있던 판들이 도착지에 차례로 쌓이는 작업이 수행된다.
  • 그림 설명

4) 종료 조건으로 n=1이 되면, 출발지에 있는 판을 도착지로 옮긴다.

  • 때에 따라 출발지가 보조가 될 수도 있고, 도착지가 될 수도 있다.
  • 때에 따라 도착지가 출발지가 될 수도 있고, 보조가 될 수도 있다.
  • 때에 따라 보조가 출발지가 될 수도 있고, 도착지가 될 수도 있다.
  • 위에 1, 2, 3번을 명확히 이해하면, 방금 한 소리가 무슨 말인지 이해가 된다...ㅎㅎ

2. 구현코드

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

3. 배운점

  • 재귀는 트리 형태로 코드를 직접 손으로 써가면서 풀자!

4. 참고


Off.


프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥

profile
Communication : any

0개의 댓글