[JavaScript] Tower of Hanoi

HongBeen Lee·2022년 6월 20일
1

Algorithms

목록 보기
15/15

라이브 코테에서 하노이탑을 구현해보라는 요구를 받았다.

재귀연습에 아주 기초적인 문제인데 생각해보니 한번도 구현해보지 않았던.. 이 점이 실수였다.
항상 기초에 충실하자!


Solution

문제는 워낙 유명하니, 여기 프로그래머스 문제에서 확인할 수 있다.
전혀 감이 오지않는다면, 이 유튜브 영상을 추천한다.

가장 중요한 인사이트는 다음 두가지라고 생각한다.


1. 가장 큰 원판을 제외한 N-1개를 통째로 mid rod에 옮겨야한다.
2. 1번을 수행했다면, 가장 큰 원판을 end rod에 가져다두어야 한다.
3. mid rod에 옮겨둔 N-1개를 통째로 end rod에 옮겨야한다.

이 과정을 보면, 재귀적으로 구현해야하는 부분을 알 수 있다.
1번을 수행하기 위해서는 결국, N-1개의 하노이탑을 mid rod로 주어진 end rod에 가져다놓는 수행이 된다.

이 과정을 자바스크립트로 구현하면 다음과 같다.

function solution(n) {
    const answer=[];
    const start=1;
    const mid=2;
    const end=3;
    
    const hanoi= (curN, curS, curM, curE)=>{
        if(curN===1){
            answer.push([curS,curE])
            return;
        }
        hanoi(curN-1, curS, curE, curM);
        answer.push([curS,curE]);
        hanoi(curN-1, curM, curS, curE);
    }
    hanoi(n,start,mid,end)
    
    return answer;
}

시간 복잡도, 공간 복잡도

answer에 필요한 어레의 크기는 시간복잡도와 비례할 것이다.
옮기는 횟수만큼 저장되기 때문이다.

hanoi 함수를 재귀적으로 호출하는 방법또한 시간복잡도와 비례할 것이다.

그럼 이 함수가 몇번 호출되는지 생각해보면 된다.
우선 1개의 하노이탑이 주어지면 O(1)로 끝날것이다.

중요한 점은 T(n) = 2T(n-1) + 1 이다.

T(1)= 1
T(2) = 2T(1)+1 = 2 + 1
T(3) = 2T(2)+1 = 2(2+1)+1 = 2^2 + 2^1 + 2^0

이를 일반화해보면
T(N) = 2^(n-1) + 2^(n-2) + ... + 2^0 = 2^n -1 임을 알 수 있다.

즉, O(2^n-1)이므로 O(2^n)의 시간복잡도를 가진다.

따라서 이만큼의 정답어레이와 재귀 콜스택이 필요하므로 공간복잡도도 O(2^n)만큼 필요하다고 할 수 있다.

profile
🏃🏻‍♀️💨

0개의 댓글