다른 재귀문제를 몇몇 개 풀어봤지만 하노이탑은 그냥 형태를 기억해... - 인프런

하노이탑 문제가 어떻게 재귀의 기본문제일까요.. 다른 재귀문제 많이 풀어봤지만, 하노이탑은 정답 안 본 상태에서 며칠이고 고민해도 못풀었었고 지금도 사실 잘 모르겠네요.

그냥 아래 항목들을 외워서 재귀 함수 호출하면 된다고 암기했습니다.

영상으로 보면 코드 한 줄 한 줄 실행되는 과정 보여주시면 "되니까 신기하네"라고 생각은 하지만, 1번 과정 중에 3번도 간헐적으로 일어나고, 3번하다가 1번도 계속 일어나면서 얼기설기 엉켜있어서 이해하기 힘드네요.

다들 대략적인 형태를 기억해서 푸는것일뿐 정확히 탑이 이동하는 절차 순서에 대해서 파악하고 쓰는건 아니겠죠?!

안녕하세요 HLM NT님.

하노이 타워를 공부하다가 너무 어렵게 느껴지셨나보군요... 😥

사실 HLM NT님이 질문하신 것 처럼 재귀로 문제를 해결할 때 영상에서 설명한 것 처럼 모든 함수를 호출해보며 콜스택을 따라가보는 경우는 거의 없을겁니다. 다만 어떤 원리로 동작하는지 알아보기 위해서 전부 따라가본 것이죠~

재귀적인 사고가 쉽지 않아서 답답하셨을 거라고 생각합니다.

재귀 문제를 해결하기 위한 접근 방식을 설명해보려고 하는데 도움이 되셨으면 좋겠습니다. 😊

재귀의 강력함은 '하위 문제가 해결됐다고 가정하고' 현재 문제를 풀 수 있다는 것입니다. 그리고 이렇게 해결했다면 문제가 복잡해져도 해결되죠.

따라서 하노이 타워도 하위 문제(n-1개의 원반을 목적지가 아닌 다른 기둥으로 옮기기)가 해결됐다고 가정하고 현재 문제에만 집중한 것입니다.

하노이 타워에서 재귀적인 사고는 HLM NT님께서 암기하신 3단계입니다.

만약 가장 큰 원반을 목표 기둥에 옮기는 하나의 문제만 생각한다면 n-1의 원반을 옮기는 문제는 이미 해결됐다고 가정합니다.

그러면 가장 큰 원반 하나를 옮기는 건 아주 쉽죠.

이렇게 현재 문제를 해결했다면 다음 하위 문제인 n-1 원반을 다시 목표 기둥으로 옮기는 걸 생각해야합니다.

재귀로 문제를 풀기 위해서는 하위 문제와 현재 문제를 잘 구분하는게 핵심이라고 볼 수 있습니다.

재귀적 사고는 사람 일반적인 사고방식과는 많이 다르므로 익숙해지려면 시간과 연습이 필요합니다.

지금 이해가 안가서 조금 답답하시더라도 여러번 접하다보면 실력이 느실거라고 생각합니다 ㅎㅎ

도움이 됐을까요? 😊

인프런 커뮤니티 질문&답변