재귀2 하노이 탑 이번에 소개할 알고리즘은 하이노 탑입니다. 재귀를 이용한 알고리즘이며, 워낙 유명해서 재귀를 설명한다고 하면 이 하노이 탑을 예시로 드는 경우가 많습니다. 1. 하노이 탑 하노이 탑은 아래 사진과 같이 세개의 기둥에 원반을 꽂는 장난감입니다. 하지만 모든 기둥에는 반드시 큰 원반이 작은 원반보다 아래 와야한다는 규칙이 있습니다. 초기 상태는 첫 번째 기둥에 모든 원반이 차례대로 쌓여있으며 이 원반들을 세 번째 기둥에 차례대로 쌓아 놓는 것이 하노이 탑의 목표입니다. 2. 하노이 탑의 작동 다음과 같은 3개 원반을 1번 기둥에서 3번 기둥으로 옮기려고 합니다. 가장 작은 빨간 원반을 3번 기둥으로 보냅니다. 그리고 중간 크기인 주황 원반을 2번 기둥에 보냅니다. 이때, 빨간 원반을 2번에 보내고, 주황 원.. 2021. 11. 8. 재귀 알고리즘 - 유클리드 호제법 정렬에 이어 처음으로 소개할 알고리즘은 재귀의 유클리드 호제법입니다. 1. 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 구하는 수학 알고리즘입니다. 두 정수의 최대공약수는 두 정수에서 큰 값을 작은 값으로 나누었을 때, 나머지가 0으로 나누어 떨어지는 값이 최대공약수입니다. 하지만, 보통 한 번의 계산으로는 나누어 떨어지지 않죠. 그래서 큰 값을 다시, 이전에 나온 나머지값으로 나누어 계산합니다. 이 과정을 반복하면 두 정수의 최대공약수를 구할 수 있습니다. 예) 30, 12 30/12 = 2 ... 6 30/6 = 5 ...0 따라서, 두 수의 최대 공약수는 5 최대공약수 구하는 과정을 보니 어디를 재귀적으로 처리해야할지 감이 잡히시나요? 2. 유클리드.. 2021. 11. 8. 이전 1 다음 300x250
