원판의 갯수가 주어진 하노이의 탑을 풀수 있는 최단 횟수의 방법을 돌려주는 문제.
우선 풀이법은 직관적으로 다가오진 않았다. 해서 작은 갯수의 원판을 사용 할때의 풀이법을 늘어놓고 고민해 보았다. 아래 주석들은 풀이를 할때 고민하면서 적어본 풀이법이다.
// n= 1 [1,3] s=1 m=2 e=3
// n= 2 [1,2] => [1,3] => [2,3]
// n= 3 [1,3] => [1,2] => [3,2] => [1,3] => [2,1] => [2,3] => [1,3]
// n= 4
// [1,2,3,4] [] []
// [2,3,4] [1] [] = [1,2]
// [3,4] [1] [2] = [1,3]
// [3,4] [] [1,2] = [2,3]
// [4] [3] [1,2] = [1,2]
// [1,4] [3] [2] = [3,1]
// [1,4] [2,3] [] = [3,2]
// [4] [1,2,3] [] = [1,2]
// [1,3]
위와 같이 늘어놓고 보니 풀이법의 길이가 원판이 늘어감에 따라 일정한 갯수로 늘어나고 있었으며 그 풀이법도 뭔가 유사해보이는 것을 확인할수 있었다. 그리고 조금더 생각 해본 결과 풀이법의 일부의 차이는 해당 풀이가 진행될때의 원판들의 위치와 움직여야할 장소의 차이라는 생각이 들었다.
해서 원판이 놓여야할 위를 시점, 종점, 중간점으로 구분하고 원판의 갯수까지 포함해서 입력값으로 받는 함수를 생각해보았다.
n 원판의 갯수, s 시점, m 중간점, e 종점
f(n,s,m,e)
그리고 원판의 갯수가 1개와 2개일때와 위에서 생각한 함수를 조합해보았다.
f(2,1,2,3) => f(1,s,e,m) [s,e] f(1,m,s,e)
=> [1,2], [1,3], [2,3]
f(3,1,2,3) => f(2,s,e,m) [s,e] f(2,m,s,e)
=> f(1,s,m,e) [s,m] f(1,e,s,m) [s,e] f(1,m,e,s) [m,e] f(1,s,m,e)
=> [1,3], [1,2], [3,2], [1,3], [2,1], [2,3], [1,3]
위와 같은 관계가 원판의 갯수와 무관하게 적용 되는것을 확인할수 있었고, 이를 통하면 문제풀이를 마무리 할수 있었다.
socket.io 서버로 하는 단순한 멀티 룸 채팅.
위의 결과를 server-side로 구현해보기.
firebase 사용법 배우기
serverless lambda 학습하기