📚 재귀 (Recursion)

어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀라고 한다.
재귀를 효과적으로 사용하면 프로그램을 간결하고 효율성 있게 작성할 수 있다.

팩토리얼

• 0! = 1
• n > 0 이면 n! = n * (n-1)!

Python으로 팩토리얼 함수 구현

def factorial(n: int) -> int:
    if n > 0:
        return n * factorial(n-1)
    else:
        return 1

Python은 math 모듈의 factorial(n) 함수를 사용하여 팩토리얼 값을 얻을 수 있다.

유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘이다.

• 호제법 : 두 수를 서로의 상대방 수로 나누어 원하는 수를 얻는 알고리즘

일반적인 방법으로 최대공약수 구하기

수 A, B를 각각 소인수 분해하여 공통된 소수의 곱이 최대공약수가 된다.

18과 8의 최대 공약수를 구해보자!

1) 소인수 분해
36 = 2 2 3 3
42 = 2 3 * 7

2) 공통된 소수의 곱 찾기
2 * 3 = 6이 공통된 소수의 곱이므로, 두 수의 최대공약수는 6이 된다.

이 방법은 수가 커질수록 소인수 분해가 어려워진다는 단점이 있다.

유클리드 호제법으로 최대공약수 구하기

유클리드 호제법은 mod 연산을 사용하여 수 A, B의 최대공약수를 구한다.

1) 큰 수 A를 작은 수 B로 나눈 나머지를 C라고 하자.
A mod B = C

2) C가 0이 아니라면 B mod C 연산을 한다.
B mod C = C'

3) C'가 0이 아니라면 C mod C' 연산을 한다.
C mod C' = C"

4) 나머지가 0이 될 때까지 반복적인 mod 연산을 수행한다.

나머지가 0이 되었을 때, 나누는 수로 사용된 수가 A와 B의 최대공약수가 된다.

Python은 math 모듈의 gcd(x, y) 함수를 사용하여 두 수의 최대공약수를 구할 수 있다.

📚 재귀 알고리즘 분석

하향식 분석과 상향식 분석

def recur(n: int) -> int:
    if n > 0:
        recur(n-1)
        print(n)
        recur(n-2)
        
n = 4
recur(n)

위 재귀 함수를 분석해보자!
하향식 분석과 상향식 분석으로 분석할 수 있다.

• 하향식 분석(top-down) : 가장 먼저 호출된 함수부터 시작해 계단식으로 자세히 분석하는 방법
• 상향식 분석(bottom-up) : 가장 아래쪽부터 쌓아 올리며 분석하는 방법

📚 하노이의 탑

쌓아놓은 원반을 최소 횟수로 옮기는 알고리즘

import sys

input = sys.stdin.readline

n = int(input().strip())

def hanoi(num, start, dest):
    if num > 1:
        hanoi(num-1, start, 6 - start - dest)

    print(f'원반 {num} : {start} -> {dest}')

    if num > 1:
        hanoi(num-1, 6 - start - dest, dest)

hanoi(n, 1, 3)

📚 8퀸 문제

8개의 퀸이 서로를 잡지 못하도록 8*8 체스판에 배치

# i: 열, j: 행
import sys

pos = [0] * 8
flag = [False] * 8
flag_a = [False] * 15
flag_b = [False] * 15

def put() -> None:
    # 각 열에 배치한 퀸의 위치를 출력
    for i in range(8):
        for j in range(8):
            print('■' if pos[i] == j else '□', end='')
        print()
    print()


def set(i: int) -> None:
    # i열에 퀸을 배치
    for j in range(8):
        if (    not flag[j]     # j행에 퀸이 없을 때
                and not flag_a[i+j]  # 대각선 방향으로 퀸이 없을 때
                and not flag_b[i-j+7]):  # 대각선 방향으로 퀸이 없을 때
            pos[i] = j  # 퀸을 j행에 배치
            if i == 7:
                put()  # 모든 열에 퀸 배치를 끝내고 출력
            else:
                flag[j] = flag_a[i+j] = flag_b[i-j+7] = True
                set(i + 1)  # 다음 열에 퀸 배치
                flag[j] = flag_a[i+j] = flag_b[i-j+7] = False


set(0)  # 0 열에 퀸을 배치 시작