고정 헤더 영역
상세 컨텐츠
본문
#1 하노이탑
왼쪽 기둥에 있는 원판 n개를 가장 오른쪽 기둥으로 옮기는 수학적 게임이다.
가장 중요한 건 이동 횟수가 최소가 되어야 한다는 점!
원판은 위로 갈수록 지름이 작아진다.
-규칙
1. 한 번에 하나의 원판만 이동 가능하다.
2. 맨 위에 있는 원판만 이동 가능하다.
3. 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다.
-원리⭐⭐⭐⭐⭐
편의를 위해 기둥 이름을 가장 왼쪽부터 1, 2, 3으로 부르겠다.
1번 기둥에 있는 원판을 모두 3번 기둥으로 옮기기 위해서는
출발지인 1번 기둥의 맨 밑에 있는 가장 큰 원판을 목적지인 3번 기둥 맨 밑으로 깔아야 한다.
그러기 위해서는 1번 기둥에 있는 n개의 원판 중 가장 아래 있는 1개의 원판을 제외한
n-1개의 원판을 목적지가 아닌 경유지인 2번 기둥으로 옮겨야 한다.
n-1개의 원판을 2번 기둥에 옮기는 과정 또한 위와 마찬가지로
2번 기둥의 맨 밑에는 n-1개의 원판 중 가장 큰 원판이 밑으로 가야 하고
나머지 n-2개의 원판은 경유지 기둥을 이용해 이동돼야 한다.
이런 과정이 반복돼야 하기 때문에 하노이탑은 재귀 함수를 이용하는 가장 대표적인 알고리즘 문제이다.
//나는 하노이탑 알고리즘을 이해하기 위해 구글링도 하고 유튜브 설명 영상도 보았는데,
이해를 위해서는 유튜브 영상을 찾아보는 걸 추천한다.
#2 재귀함수 (recursive function)
사전 정의는 "주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하는 방식"이다.
말 그대로 함수 안에서 자신 함수를 계속해서 호출해내는 함수이다.
탈출 조건이 주어져야 한다. 그렇지 않으면 무한루프가 되므로...
재귀 함수를 for문이나 while문을 중첩 사용해 구현할 수 있다.
재귀 함수를 사용하면 코드가 간결해지고 단순해지지만 for문이나 while문과 달리 스택 메모리를 사용하기 때문에 속도도 느리고 메모리 차지도 많이 한다.
반대로 for문이나 while문을 사용하면 반복 회수가 정해지지 않았거나 사용해야 되는 변수도 많아지고 코드가 길어지므로 필요에 따라 잘 선택해서 쓸 수 있어야 한다.
#3 C++ 코드
워낙 유명한 알고리즘이라 코드는 정말 찾기 쉬웠다. 그럼 한 줄씩 뜯어보자.
먼저 main함수를 보겠다.
원판을 몇 개 쌓아 줄 건지 사용자가 입력할 수 있도록 cin을 통해 받아준다.
최소 이동 횟수 k를 계산해주었다.
k=2^n - 1이다.
pow(a, b)는 a^b을 계산해주는 함수로 cmath 헤더를 include 해줘야 한다.
지금 알았는데 cmath헤더 include를 안 해줬다. 근데 왜 잘 되지...? 얼른 해준다... 그러므로 아래부턴 코드가 한 줄씩 밀릴 예정이다.
pow는 double형 함수지만 내가 필요한 이동 횟수는 정수이기 때문에 int로 선언해준다.
그래서 컴파일할 때 데이터 손실이 있다고 안내문이 뜬다
hanoi함수를 호출하며 main함수는 할 일을 다 했다. 그럼 hanoi함수를 뜯어보자
사용자가 입력한 원판 개수 n과
출발지 from
경유지 by
목적지 to를 정수형인 int로 선언해줬다. 내가 기둥 이름을 1,2,3으로 붙였기 때문이다.
main함수 마지막 줄 코드가 hanoi(n, 1, 2, 3)이었는데 이는
출발지 from를 1번 기둥
경유지 by를 2번 기둥
목적지 to를 3번 기둥으로 설정했다는 것이다.
이 순서를 잘 기억하자 hanoi (원판 개수, 출발지, 경유지, 목적지)이다
hanoi 함수의 탈출 조건으로 아래의 재귀 함수를 다 거치고 마지막에 남은 원판의 개수가 1일 때 목적지로 마지막 기둥을 옮긴다.
코드의 1차적인 이해를 돕기 위해 주석에는 기둥의 숫자를 명시해놨지만 출발지, 경유지, 목적지 개념으로 생각하는 것이 편하다. 왜냐하면 단순히
출발지 from를 1번 기둥
경유지 by를 2번 기둥
목적지 to를 3번 기둥으로 이해한다면 위에 if 탈출 조건문을 봤을 때 from과 to를 출력하니
마지막 출력문은 당연히 1 3 이겠거니 하지만 실상은 아해 hanoi 재귀 함수를 여러 번 거치면
각 과정마다 출발지와 경유지, 목적지가 섞이게 된다. 그러므로
⭐⭐⭐hanoi (원판개수, 출발지, 경유지, 목적지)⭐⭐⭐ 로 생각하자.
그럼 다시 보면
기둥 1에서 맨 마지막 제일 큰 원판을 제외한 나머지 n-1개의 원판을
출발지 기둥1에서
경유지인 기둥 3을 사용해
목적지인 기둥 2로 옮긴다.
이다.
하지만 옮기는 과정에서 기둥2 가장 아래에는 n-1개의 원판 중 가장 큰 원판이 제일 아래로 와야 하고
나머지 n-2개의 원판은 경유지를 거쳐 기둥 2에 도달할 것이다.
그러므로 재귀 함수를 이용해 그 과정을 모두 계산해주는 것이다.
이 과정에서 출발지, 경유지, 목적지는 계속 달라진다.
위 설명을 이해했다면 다음 코드들도 이해할 수 있을 것이다.
11번 줄에서 기둥 1에서 맨 마지막 제일 큰 원판을 제외한 나머지 n-1개의 원판을 기둥2로 옮겼기 때문에
12번 줄에서 기둥1에서 기둥 3으로 제일 큰 원판을 옮기고
13번 줄에서 기둥 2에 있는 n-1개의 원판을 기둥 3으로 옮긴다.
출발지인 기둥 2에서
경유지인 기둥 1을 이용해
목적지인 기둥 3으로 옮긴다.
그리고 그 과정에서도 계속해 hanoi 함수를 이용한다.
이해를 돕기 위해 기둥 3개를 옮기는 과정을 손으로 한 번 써보는 걸 추천한다.
