하노이탑 게임 : 한 수학자가 개발한 게임으로 세개의 기둥과 서로 다른 크기의 원반이 있으며 이 원반은 위로 갈수록 작은 원반으로 이루어져 있다. 하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야하는데 이때 아래의 규칙을 준수해야한다. 1. 한 번에 하나의 원반을 움직일 수 있다. 2. 가장 위에 있는 원반만 옮길 수 있다. 3. 아래에 작은 원반이 올 수 없다. 하노이탑을 하향식 방식으로 접근 후 계산 (순서대로 스택에 하나씩 쌓인다.) 기둥 A에 있는 원반 1,2,3을 기둥 c로 옮기려고 함. 스택1 : 원반3을 기둥 C로 옮김 스택2 : 원반2,1을 기둥 B로 옮김(하위문제) 스택3 : 원반 2,1을 기둥 B로 옮기기 위해서는 원반1이 기둥 C로 이동해야함. -> 바로 C로 이동시킬 수 있으므로 더..
자료구조와 알고리즘 인강 정리 : 재귀-하노이탑
하노이탑 게임 : 한 수학자가 개발한 게임으로 세개의 기둥과 서로 다른 크기의 원반이 있으며 이 원반은 위로 갈수록 작은 원반으로 이루어져 있다. 하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야하는데 이때 아래의 규칙을 준수해야한다. 1. 한 번에 하나의 원반을 움직일 수 있다. 2. 가장 위에 있는 원반만 옮길 수 있다. 3. 아래에 작은 원반이 올 수 없다. 하노이탑을 하향식 방식으로 접근 후 계산 (순서대로 스택에 하나씩 쌓인다.) 기둥 A에 있는 원반 1,2,3을 기둥 c로 옮기려고 함. 스택1 : 원반3을 기둥 C로 옮김 스택2 : 원반2,1을 기둥 B로 옮김(하위문제) 스택3 : 원반 2,1을 기둥 B로 옮기기 위해서는 원반1이 기둥 C로 이동해야함. -> 바로 C로 이동시킬 수 있으므로 더..
2023.04.12