[알고리즘]Recursion(재귀) 알고리즘 - (2) Hanoi, Magic Index

Recursion(재귀)

문제 6: Hanoi Tower

이 동영상의 출저는 Program for Tower of Hanoi Algorithm이다. \(N=3\)일 때의 하노이 탑 문제를 보여준다.

• Base Case (기본 사례)
  • 하노이 탑 문제에서 기본 사례는 이동할 디스크가 없는 경우이다. \(n < 1\)일 때, 함수는 0을 반환한다.
  • 이는 더 이상 이동할 디스크가 없음을 의미하며, 재귀 호출이 종료되는 조건이다.
• Inductive Case (유도 단계)
  • 하노이 탑 문제에서 \(n\)개의 디스크를 다른 기둥으로 옮기는 문제는 세 단계로 나눌 수 있다.
    • 총 \(n-1\)개의 디스크를 첫 번째 기둥에서 두 번째 기둥으로 옮긴다.
    • 가장 큰 디스크(마지막 디스크)를 첫 번째 기둥에서 세 번째 기둥으로 옮긴다.
    • 두 번째 기둥에 있던 \(n-1\)개의 디스크를 세 번째 기둥으로 옮긴다.
  • 함수는 이러한 단계들을 재귀적으로 호출하여 문제를 해결한다.

def hanoi(n: int, a=1, b=2, c=3) -> int:
    if n < 1:
        return 0
    # n-1개의 디스크를 A에서 B로 이동
    numAToB = hanoi(n - 1, a, c, b)
    print("Move disk from {} to {}".format(a, c))
    # n-1개의 디스크를 B에서 C로 이동
    numBToC = hanoi(n - 1, b, a, c)
    return numAToB + 1 + numBToC

def test(n: int) -> int:
    print("Hanoi({})".format(n))
    return hanoi(n)

if __name__ == "__main__":
    # 테스트 실행: 디스크 3개
    test(3)

Hanoi(3)
Move disk from 1 to 3
Move disk from 1 to 2
Move disk from 3 to 2
Move disk from 1 to 3
Move disk from 2 to 1
Move disk from 2 to 3
Move disk from 1 to 3

문제 7: Magic Index

• Base Case (기본 사례)
  • 배열이 비어 있거나 검색 범위가 유효하지 않은 경우, Magic Index는 존재하지 않으며 None을 반환한다.
  • 예를 들어, 이진 검색에서 start > end인 경우가 이에 해당한다.
• Inductive Case (유도 단계)
  • 중간 인덱스 mid를 계산한 후, A[mid]가 mid와 같은지 비교한다.
    • A[mid] == mid: Magic Index를 찾았으므로 mid를 반환한다.
    • A[mid] < mid: 오른쪽 하위 배열에서 Magic Index를 찾는다 (start = mid + 1).
    • A[mid] > mid: 왼쪽 하위 배열에서 Magic Index를 찾는다 (end = mid - 1).

def find_magic_index(A, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    # A[mid]가 Magic Index인 경우
    if A[mid] == mid:
        return mid
    # A[mid] < mid인 경우, 오른쪽 하위 배열을 탐색
    elif A[mid] < mid:
        return find_magic_index(A, mid + 1, end)
    # A[mid] > mid인 경우, 왼쪽 하위 배열을 탐색
    else:
        return find_magic_index(A, start, mid - 1)

def magic_index(A):
    return find_magic_index(A, 0, len(A) - 1)

if __name__ == "__main__":
    # 예제 1
    arr1 = [0]
    print(f"Magic Index: {magic_index(arr1)}")  # 출력: 0

    # 예제 2
    arr2 = [-5, -2, 0, 1, 2, 5, 6]
    print(f"Magic Index: {magic_index(arr2)}")  # 출력: 5

Magic Index: 0
Magic Index: 5

Reference

[1] Program for Tower of Hanoi Algorithm
[2] Lecture: ITG6022 Computational Problem Solving

Algorithm 카테고리 내 다른 글 보러가기