Python 재귀, 하노이의 탑, 병합 정렬, 퀵 정렬

1. 재귀 알고리즘

• 특정 함수가 함수 내에서 자기 자신을 다시 호출하는 것을 지칭

# 별 출력 프로그램
def recursion(num):

  if num > 0:
    print("*"*num)
    return recursion(num-1) # 1씩 감소하며 재귀 호출

  else:
    return None

recursion(5)

# 출력 예시
# *****
# ****
# ***
# **
# *

# 최대공약수 계산 프로그램
def gcd(num1, num2):
  
  if num2 > num1:
    num1, num2 = num2, num1
  
  if num1 % num2 == 0:
    return num2
    
  else:
    return gcd(num1, num1 % num2) # 유클리드 호제법

print(gcd(44, 64))

# 출력 예시
# 4

2. 하노이의 탑

• 퍼즐 게임의 일종으로, 세 개의 기둥을 활용하여 원판을 한 기둥에서 다른 기둥으로 옮기는 방식임
• 단, 한 번에 하나의 원판만을 옮길 수 있으며 큰 원판은 작은 원판 위에 올릴 수 없음

def hanoi_tower(disc_n, from_bar, to_bar, via_bar):
  """
  disc_n: 원판 수
  from_bar: 시작 기둥
  to_bar: 목표 기둥
  via_bar: 잉여 기둥
  """

  if disc_n == 1:
    print(f"{disc_n}번 원판을 {from_bar}에서 {to_bar}로 이동")

  else:
    hanoi_tower(disc_n - 1, from_bar, via_bar, to_bar)
    print(f"{disc_n}번 원판을 {from_bar}에서 {to_bar}로 이동")
    hanoi_tower(disc_n - 1, via_bar, to_bar, from_bar)

hanoi_tower(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. 병합 정렬

• 자료구조를 분할하고 각 분할된 자료구조를 정렬하며 병합하는 방식

def merge_sort(num_list):

  if len(num_list) < 2:
    return num_list

  else:
    mid_idx = len(num_list) // 2
    left_list = merge_sort(num_list[:mid_idx])
    right_list = merge_sort(num_list[mid_idx:len(num_list)])  
    merge_list = list()
    left_idx, right_idx = 0, 0

    while left_idx < len(left_list) and right_idx < len(right_list):
      
        if left_list[left_idx] < right_list[right_idx]:
          merge_list.append(left_list[left_idx])
          left_idx += 1

        else:
          merge_list.append(right_list[right_idx])
          right_idx += 1

    merge_list = merge_list + left_list[left_idx:]
    merge_list = merge_list + right_list[right_idx:]

    return merge_list

num_list = [8, 1, 4, 3, 2, 5, 10, 6]
print(merge_sort(num_list))

# 출력 예시
# [1, 2, 3, 4, 5, 6, 8, 10]

4. 퀵 정렬

• 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합쳐 정렬하는 방식
• 분할정복방식으로 여타 정렬방식보다 신속히 정렬할 수 있음

def quick_sort(num_list):
  
  if len(num_list) < 2:
    return num_list

  else:
    mid_idx = len(num_list) // 2
    mid_val = num_list[mid_idx]

    small_list, same_list, big_list = list(), list(), list()

    for num in num_list:
      if num < mid_val:
        small_list.append(num)
        
      elif num == mid_val:
        same_list.append(num)

      else:
        big_list.append(num)
           
    return quick_sort(small_list) + same_list + quick_sort(big_list)

num_list = [8, 1, 4, 3, 2, 5, 10, 6]
print(quick_sort(num_list))

# 출력 예시
# [1, 2, 3, 4, 5, 6, 8, 10]

*이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.