재귀와 분할 정복의 예시 문제

5.1 재귀 함수의 이해

예시: 팩토리얼

동작 원리

• 팩토리얼 n!은 n × (n-1)!로 정의됩니다.
• n이 1이거나 0이면 1을 반환(기저 조건).
• 그렇지 않으면 n × factorial(n-1)을 반환(재귀 호출).
• 호출 스택에 함수가 쌓였다가, 기저 조건에 도달하면 반환되며 결과가 계산됩니다.

코드 (Python)

def factorial(n):
    """
    n의 팩토리얼을 재귀적으로 계산합니다.
    기저 조건: n이 0 또는 1이면 1 반환
    재귀 호출: n * factorial(n-1)
    """
    if n == 0 or n == 1:
        return 1  # 기저 조건(Base case)# 재귀적으로 자기 자신을 호출
    return n * factorial(n-1)

# 예시 실행
print(factorial(5))  # 120 (5*4*3*2*1)

5.2 분할 정복 전략

예시: 이진 탐색

동작 원리

• 정렬된 배열에서 찾고자 하는 값(target)이 중간값과 같으면 인덱스 반환.
• target이 중간값보다 작으면 왼쪽 절반, 크면 오른쪽 절반에서 재귀적으로 탐색.
• 탐색 구간이 사라지면(왼쪽 > 오른쪽) -1 반환.

코드 (Python)

def binary_search(arr, target, left, right):
    """
    분할 정복의 대표 예시인 이진 탐색.
    배열을 반씩 나누며 target을 찾음.
    """
    if left > right:
        return -1  # base case: 못 찾은 경우
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 값을 찾은 경우
    elif arr[mid] < target:
        # 오른쪽 절반에서 재귀적으로 탐색
        return binary_search(arr, target, mid+1, right)
    else:
        # 왼쪽 절반에서 재귀적으로 탐색
        return binary_search(arr, target, left, mid-1)

# 예시 실행
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr)-1))  # 3

5.3 대표 문제 및 실습

1. 병합 정렬 (Merge Sort)

동작 원리

• 배열을 반씩 나누어 더 이상 쪼갤 수 없을 때까지 분할.
• 쪼개진 배열을 정렬하면서 병합.
• 각 병합 단계에서 두 정렬된 배열을 하나로 합침.

코드 (Python)

def merge_sort(arr):
    """
    분할 정복의 대표 예시: 병합 정렬
    배열을 반씩 나누고, 정렬하며 병합
    """
    if len(arr) <= 1:
        return arr  # base case: 원소가 1개 이하일 때
    mid = len(arr) // 2
    # 분할(Divide)
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # 정복 및 결합(Conquer & Combine)
    return merge(left, right)

def merge(left, right):
    """
    두 정렬된 배열을 하나로 합치는 함수
    """
    merged = []
    i = j = 0
    # 두 배열을 비교하며 작은 값부터 추가
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # 남은 원소 추가
    merged += left[i:]
    merged += right[j:]
    return merged

# 예시 실행
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]

2. 하노이의 탑 (Tower of Hanoi)

동작 원리

• n개의 원반을 A에서 C로 옮기려면
  1. n-1개의 원반을 A에서 B(보조)로 옮김
  2. 가장 큰 원반을 A에서 C로 옮김
  3. n-1개의 원반을 B에서 C로 옮김
• 이 과정을 재귀적으로 반복

코드 (Python)

def hanoi(n, start, end, via):
    """
    하노이의 탑: n개의 원반을 start에서 end로 via를 거쳐 옮김
    """
    if n == 1:
        print(f"원반 1: {start} -> {end}")
        return
    # 1단계: n-1개를 start에서 via로
    hanoi(n-1, start, via, end)
    # 2단계: 가장 큰 원반을 start에서 end로
    print(f"원반 {n}: {start} -> {end}")
   *# 3단계: n-1개를 via에서 end로
    hanoi(n-1, via, end, start)

# 예시 실행 (3개의 원반)
hanoi(3, 'A', 'C', 'B')
# 출력 예시:
# 원반 1: A -> C
# 원반 2: A -> B
# 원반 1: C -> B
# 원반 3: A -> C
# 원반 1: B -> A
# 원반 2: B -> C
# 원반 1: A -> C

3. 피보나치 수열 (비효율적 재귀, 메모이제이션 예시)

동작 원리

• f(n) = f(n-1) + f(n-2)
• 기저 조건: n==0이면 0, n==1이면 1
• 중복 호출이 많으므로, 메모이제이션 사용 시 효율적

코드 (Python, 메모이제이션 포함)

def fib(n, memo={}):
    """
    피보나치 수열: 메모이제이션을 활용한 재귀
    """
    if n in memo:
        return memo[n]  # 이미 계산한 값은 바로 반환
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 재귀적으로 계산
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

# 예시 실행
print(fib(10))  # 55

이처럼 재귀와 분할 정복은

• 문제를 쪼개고(분할)
• 작은 문제를 풀고(정복)
• 결과를 합쳐(결합)
• 전체 문제를 해결하는 강력한 도구입니다.