하노이탑에 대하여

매우 standard한 하노이탑을 이해하기란 나의 머리로 쉽지 않았다.

솔직히 상상이 안갔던 것 같다.

나는 개인적으로 DP를 머리보단 유형으로 푸는 타입이었기에 이제는 DP를 생각하면서 푸는 페러다임을 마련해야함을

느꼈다.

 

가장 DP와 재귀의 기초라는 하노이탑을 풀 수 없는 골 1이라니, 수치스럽기도 하고 발전해야겠다는 강한 동기부여가 들었다.

 

하노이탑은 간단히 1번의 봉에 있는 원판을 크기가 큰 것이 밑으로 가도록 배열해 3번으로 모두 옮기면 된다.

 

다음은 원판 3개의 예시이고, 초기 상태에 1번 봉의 최상단에 있는 원판이 숫자 1번 원판이다.

 

우리가 원판을 옮기려면 어떻게 해야할까?

문제를 분해해보자

원판 n-1개를 어느 한 지점에 몰아둔 뒤, 원판 하나만 옮기는 방식으로 코딩을 진행하면 되지 않을까?

 

n-1개를 한 지점에 둔 뒤, 그 경로를 통해 경유하는 방식으로 점화식을 세울 수 있다.

2번째 케이스(else)를 면밀히보자.

n-1개를 mid로 옮긴 뒤 자신이 옮긴 위치를 출력하고, 경유지에 있던 n-1을 최종적으로 start를 통해 mid로 목적지로 옮긴다.

 

print(start, to)가 중간에 끼어있는 이유는, n-1개의 탑을 옮긴 뒤 최 하단 층 원판을 to로 옮기는 것을 의미한다.

 

 

풀이는 굉장히 간단한데 아이디어를 찾는게 힘든 문제인 것 같다.

DP 골드는 답 안보고 풀게 못 된다...

 

DP 팁을 개인적으로 찾고 싶었는데

1. 일단 무지성으로 그리고, 상상하라

무지성으로 가장 간단한 케이스를 찾아 노가다해보자

2. 하노이탑 문제처럼, 경유할 수 있는지를 찾아보자

엔트로피와 엔탈피가 상태함수인 것 처럼, 경유지만 찾고 그 합산만 계산하면 컴퓨터가 띡 결과만 뽑아내어준다.

3. 인자를 잘 잡아라

최대한 간단한 함수인자를 잡자, 그래야 코드가 직관적으로 이해하기 편하다

4. 점화식을 만들자

함수도 수학식처럼 공통된 형태가 묶인 것으로, 더한다는 것의 의미는 그 함수를 함께 수행한다는 의미이다.

5. 주석을 달자

전기낭비하지 않으려면 주석을 달아 코드를 편하게 수정할 수 있도록 하자

6. 재귀를 DP로 풀 수 있는지 생각해보라

DP로 보다 좋은 방법을 찾았다면 DP를 써라