하노이의 탑(Towers of Hanoi)
References
이번 글은 아래 자료들을 참고하여 작성하였습니다.
1. Towers of Hanoi on Khan Academy
2. [파이썬]알고리즘 이야기(01. 하노이 탑) by 파이썬 클래쓰 on Youtube
3. 무조건 이해시켜 드립니다. 비법 대방출! 재귀 알고리즘 Recursion - 하노이탑, 피보나치 수열 by 딩코딩 on Youtube
들어가며
하노이의 탑
을 풀기 위해서는 우선 재귀 함수
에 대한 이해가 필요하다. 재귀 함수
는 javascript
의 일반적인 동작 방식인 명령형(Imperative)
이 아니라 선언형(declarative)
으로 동작한다. 따라서 재귀 함수
를 온전히 이해하려면 declarative programming
에 대한 감각이 필요하다.
재귀 함수를 짤 때 중요한 것은 두 가지이다.
- 종료 조건
- 문제 정의
그럼 위 두 가지를 고려하여 하노이의 탑
의 pseudo code
를 나열해보자.
- 종료조건
1.원반이 하나 남으면 끝- 문제 정의 선언
1. N개의 원반을 옮기기 위해서는 N-1개의 원반을 temp기둥으로 옮겨야 함.
2. N번째 원반을 목적지 기둥으로 옮긴다.
3. temp기둥에 있는 N-1개의 원반을 목적지 기둥으로 옮긴다.
위의 pseudo code
를 바탕으로 코드를 짜면 아래와 같다.
Towers of Hanoi
const route = [];
function hanoi(num, from, to, temp) {
//원판이 한 개일 때에는 바로 옮기면 됨.
//종료조건
if (num === 1) {
route.push([from, to]);
return NaN;
}
hanoi(num - 1, from, temp, to); // n - 1개의 원반을 temp기둥에 옮김. 따라서 to -> temp, temp -> to 로 변경
route.push([from, to]); // n번째 원반을 from기둥에서 to기둥으로 옮김. n번째 원반을 막고 있던 n - 1개의 원반을 temp로 다 옮겼기 때문에 가능.
hanoi(num - 1, temp, to, from); // temp기둥에 있던 n - 1개의 원반을 to기둥으로 옮김. temp -> from, from -> temp 로 변경.
}
hanoi(3, "A", "B", "C");
console.log(route);
/*
[
[ 'A', 'B' ],
[ 'A', 'C' ],
[ 'B', 'C' ],
[ 'A', 'B' ],
[ 'C', 'A' ],
[ 'C', 'B' ],
[ 'A', 'B' ]
]
*/
console.log(route.length); // 7
위 코드는 아래와 같은 순서로 실행된다.
실행 과정(7단계)
hanoi(3, A, B, C); // 4. push A, B: 3번 원반 from(A)에서 to(B)로 이동 hanoi(2, A, C, B) // 2. push A, C: 2번 원반 from(A)에서 temp(C)로 이동 hanoi(1, A, B, C) // 1. push A, B: 1번 원반 from(A)에서 to(B)로 이동 hanoi(1, B, C, A) // 3. push B, C: 1번 원반 to(B)에서 temp(C)로 옮겨서 2번 원반 위에 쌓기 hanoi(2, C, B, A) // 6. push C, B: 2번 원반 temp(C)에서 to(B)로 이동 hanoi(1, C, A, B) // 5. push C, A: 2번 위에 있던 1번 원반 temp(C)에서 from(A)로 이동 hanoi(1, A, B, C) // 7. push A, B: 1번 원반 from(A)에서 to(B)로 이동하면서 완성.
위 실행 순서를 그림으로 나타내면 다음과 같다.
함께 보기
Author And Source
이 문제에 관하여(하노이의 탑(Towers of Hanoi)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mame-coder/하노이의-탑Towers-of-Hanoi저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)