🔊 주의사항
책에 있는 실습과 내용을 똑같이 적으면 저작권 문제가 될 수도 있기 때문에 약간의 변형을 하여 작성하였습니다. (특히, 실습 코드)
📚 05-1 재귀 알고리즘의 기본
재귀(Recursion) 알아보기
어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀(recursion)라고 한다.
📒 재귀 호출(recursice call)
함수 내부에서 함수 자기자신을 다시 호출하는 방식을 말한다.
팩토리얼 알아보기
🔎 참고자료
코딩도장 31.2 재귀호출로 패토리얼 구하기
재귀를 사용하는 대표적인 예시로 팩토리얼(Factorial)문제가 있다.
📒 팩토리얼 정의
- 0! = 1
- n > 0이면 n! = n * (n-1)!
def factorial(n):
if n > 0:
return n * factorial(n-1)
else:
return 1
print(factorial(3))
print(factorial(5))
print(factorial(7))📑 fatorial 재귀 함수 설명
math.factorial() 함수
🔎 참고자료
Python 3.10.1 문서 math 수학함수 math.factorial
wikidocs 파이썬 모듈 4 - Math
파이썬에서 팩토리얼값을 구하는 표준 라이브러리로 math 모듈에서 factorial()함수를 제공한다.
# factorial 함수를 사용하기 위해서 math를 import 해준다.
import math
print(math.factorial(3))
print(math.factorial(5))
print(math.factorial(6))유클리드 호제법(Euclidean algorithm) 알아보기
🔎 참고자료
wikipedia 유클리드 호제법
wikidocs 3. 최대공약수 구하기 - 유클리드 호제법
Lonpeach Tech 유클리드 호제법이란?
2개의 정숫값을 이용하여 최대 공약수(GCD: Greatest Common Divisor)를 재귀적으로 구하는 알고리즘이다.
Q. 직사각형 안을 정사각형 여러개로 가득 채줘 나갑니다. 이렇게 만들 수 있는 정사각형 가운데 가장 작은 정사각형의 변의 길이를 구하라.
▶ 정숫값 큰 값을 작은 값으로 계속 나누어 준다. 이때 가장 작은 값이 최대 공약수이다.
math.gcd() 함수
🔎 참고자료
Python 3.10.1 문서 math 수학함수 math.factorial
wikidocs 파이썬 모듈 4 - Math
파이썬에서 최대 공약수를 구하는 표준 라이브러리로 math 모듈에서 gcd()함수를 제공한다.
# gcd 함수를 사용하기 위해서 math를 import 해준다.
import math
print(math.gcd(22, 8))
print(math.gcd(123, 3))
print(math.gcd(50, 5))📚 05-2 재귀 알고리즘 분석
🔎 참고자료
세널리스트 하향식/상향식 분석
하향식(top-down)
가장 위쪽에 위치한 함수 호출부터 시작하여 계단식으로 조사해 가나는 분석 방법이다.
상향식(bottom-up)
하향식 분석과 반대로 아래쪽부터 쌓아 올라가가는 분석 방법이다.
📚 05-3 하노이의 탑(towers of Hanoi)
🔎 참고자료
wikipedia 하노이의 탑
Khan Academy 하노이의 탑
에포트 코딩 알고리즘 - 하노이의 탑 재귀적 접근
작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용하여 원반을 옮기는 문제이다.
📒 규칙
- 한 번에 한개의 원반만 옮길 수 있다.
- 큰 원반은 작은 원반 위에 있어선 안 된다.
📚 05-4 8퀸 문제(8-Queen problem)
분기 작업으로 문제 해결하기
🔎 참고자료
Steve Jack 8퀸 문제 -> C언어
📒 규칙
- 각 열에 퀸을 1개만 배치
- 각 행에 퀸을 1개만 배치
# 실습 파일 8queen_b.py
pos = [0]*8
def put() -> None:
for i in range(8):
print(f'{pos[i]:2}', end='')
print()
def set(i: int) -> None:
for j in range(8):
pos[i] = j
if i == 7:
put()
else:
set(i+1)
set(0)📑 설명
-
pos[i]:2
▶ 띄어쓰기 2칸을 하면서 pos[i]를 출력
▶ 띄어쓰기를 ^로 표시하면 다음과 같이 표시 된다. →pos[i] ^^ pos[i] ^^ pos[i] -
set(i+1)
▶ set(i: int)함수 내부에서 재귀 함수 호출
▶ 재귀 함수 호출을 그림으로 설명하면 다음과 같다.
📑 분기와 분할
- 분기(branching) 작업 : 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법
- 분할(divide and conquer) 작업 : 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법
한정 작업과 분기 한정법
- 한정(bounding) 작업 : 필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법
- 분기(branching and bounding) 한정법 : 분기 작업과 한정 작업을 조합하여 문제를 풀이하는 방법
