Jun 개발노트

This is Hanoi

2020-09-18

하노이 탑에 대한 이해

  1. 제약 조건

    • 한 번에 하나의 원판만 옮길 수 있다.
    • 큰 원판이 작은 원판 위에 있어서는 안 된다.
  2. 문제에 대한 이해

    • 5개의 원반을 원하는 위치에 옮기려면 마지막 원판이 목적지에 가야하는게 첫번쨰 목표
    • n을 A -> B로 옮기려면, n - 1의 원판들이 A -> C로 옮겨야 한다.
    • n - 1의 원판들이 다시 C -> B로 옮긴다.
    • 위에 과정을 다시 첫번째 과정을 다시 반복하면 된다.
  3. 코드

    function hanoi(num, from, to, other){
         // 제한 조건 
         if(num === 1) return;
         // n - 1 부터 1까지의 원판을 A -> C로 이동
         hanoi(num - 1, from, other, to);
         // n의 원판을 목적지로 옮긴다.
         console.log(`${from}번에서 ${to}로 옮긴다`);
         // n - 1부터 1까지의 원판을 C -> B로 이동 
         hanoi(num - 1, other, to, from);
       }
       hanoi(4, 0, 1, 2)
    
  4. 정리

    • 알고리즘 재귀함수를 이용한 기초문제라고 했지만, 이해하는데 .... 아직도 모르겠다.
    • 알고리즘을 풀려고 하면, 손으로 그려보고 하나의 조건을 구해야 한다
    • 하노이 탑은 n - 1 부터 1까지의 원판을 A -> C로 이동하는 것이 가장 큰 조건이었다.