라이브 코테에서 하노이탑을 구현해보라는 요구를 받았다.
재귀연습에 아주 기초적인 문제인데 생각해보니 한번도 구현해보지 않았던.. 이 점이 실수였다.
항상 기초에 충실하자!
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)만큼 필요하다고 할 수 있다.
