자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 5장. 재귀 알고리즘

5-1. 재귀 알고리즘 기본

재귀함수란

• 자기 자신을 호출하는 함수 ex) 점화식, n!(팩토리얼)
• 1개 이상의 base case(종료상황) 존재, 수렴하도록 작성
• base case에 도달할때까지 함수 호출
• 재귀시작은 n 부터지만 반환, 계산은 1부터
• 메모리 스택이 넘치면 (stack overflow) 프로그램 동작x
• 파이썬에서는 최대 재귀 깊이가 1000번, 이를 넘어가면 recursion error 발생

• 반복문 vs 재귀
  • 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 재귀함수 사용
  • 재귀 호출은 변수 사용을 줄여줌
  • 재귀 호출은 입력 값이 커질수록 연산속도 오래 걸림

• ex) 팩토리얼 구하기

  def factorial(n: int) -> int:
      """양의 정수 n의 팩토리얼을 구하는 과정"""
      if n > 0:
          return n * factorial(n - 1)  # 재귀호출
      else:
          return 1
  
  if __name__ == '__main__':
      n = int(input('출력할 팩토리얼 값을 입력하세요.: '))
      print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')

  (math 모듈에서 math.factorial() 함수 제공)
  

• 직접재귀: 함수 내부에서 자신과 똑같은 함수 호출
• 간접재귀: 함수 a에서 다른 함수 b 호출하고 b에서 다시 함수 a호출

• 유클리드 호제법

  • 최대공약수 최소공배수 구하는 알고리즘
  • 최대공약수: x, y의 최대공약수는 y, r의 최대공약수와 같다

  

  • 최소공배수: x * y를 최대공약수로 나눈 몫이 최소공배수

     ex) 10, 12의 최대공약수: 2
     10 * 12 //2 =60
     
     10, 12의 최소 공배수는 60

  • 재귀로 유클리드 호제법 사용

        def gcd(x: int, y: int) -> int:
            """정숫값 x와 y의 최대 공약수를 반환"""
            if y == 0:
                return x
            else:
                return gcd(y, x % y)

    math 모듈에서 math.gcd() 함수 제공

• 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법을 분기 작업
• 필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법을 한정 작업
• 분기 + 한정 = 분기 한정법
• 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법을 분할 정복법

---

5-2. 재귀 알고리즘 분석

• 하향식 분석
  • 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 조사해 나가는 분석
  • 같은 함수 여러번 호출하여 효율적 x
• 상향식 분석
  • 하향식과 반대로 아래쪽부터 쌓아 올리며 분석

• 재귀 알고리즘 비재귀적 표현

  from stack import Stack  # stack.py의 Stack 클래스를 임포트
  
  def recur(n: int) -> int:
      """재귀를 제거한 함수 recur"""
      s = Stack(n)
  
      while True:
          if n > 0:
              s.push(n)         # n 값을 푸시
              n = n - 1
              continue
          if not s.is_empty():  # 스택이 비어 있지 않으면
              n = s.pop()       # 저장하고 있는 값을 n에 팝
              print(n)
              n = n - 2
              continue
          break
  
  x = int(input('정수값을 입력하세요.: '))
  
  recur(x)
  
  # 4 push -> 3 push -> 2 push -> 1 push -> n = 0, 1 pop -> n= -2, 2 pop ->
  # n= 0, 3 pop -> n= 1, 1 push -> n= 0, 1 pop -> n= -1, 4 pop ->
  # n= 2, 2 push -> n= 1, 1 push -> n= 0, 1 pop -> n= -1, 2 pop -> n= 0, break

---

5-3. 재귀 관련 대표문제

하노이의 탑

• 쌓아놓은 원반 최소 횟수로 옮기는 알고리즘
• 항상 작은원반이 위에, 큰 원반이 아래에
  

def move(no: int, x: int, y: int) -> None:
    """원반을 no개를 x 기둥에서 y 기둥으로 옮김"""
    if no > 1:
        move(no - 1, x, 6 - x - y)

    print(f'원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.')

    if no > 1:
        move(no - 1, 6 - x - y, y)

print('하노이의 탑을 구현하는 프로그램입니다.')
n = int(input('원반의 개수를 입력하세요.: '))

move(n, 1, 3)

---

N-queen

• NxN 체스판에서 퀸들이 서로 공격하지 않도록 놓을 수 있는 경우의 수 구하는 알고리즘
• 백 트래킹으로 탐색
  

import sys

input = sys.stdin.readline


def dfs(num):
    global ans
    # N행까지 왔다면 완료
    if num == N:
        ans += 1
        return

    for j in range(N):
        # 열, 대각에 퀸 없다면
        if v1[j] == 0 and v2[j+num] == 0 and v3[j-num] == 0:
            # 체크하고 아래 행으로 재귀호출
            v1[j] = v2[j+num] = v3[j-num] = 1
            dfs(num + 1)
            # 탐색 끝났으면 체크 해제하고 다음 칸으로 이동
            v1[j] = v2[j + num] = v3[j - num] = 0


N = int(input())
ans = 0
# 열, 왼쪽 대각, 오른쪽대각 퀸 있는지 체크 배열
v1, v2, v3 = [[0] * (N * 2) for _ in range(3)]

dfs(0)
print(ans)