알고리즘 기초 입문을 위해 공부한 DO IT! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬편을 통해 새로 알게 된 내용을 정리한다.

1. 재귀란

1-1. 직접 재귀 vs 간접 재귀

• 직접 재귀 : a() -> a()

[팩토리얼] 

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


[유클리드 호제법]

(나의 첫 구상)
def gcd(a : int, b : int) -> int : 
  if a % b == 0 :
    return b
  else :
    return gcd(b,a%b)
-----------------------------------
> 0과 자연수의 최대공약수는 무조건 '자연수' 그대로
> 첫 매개변수로 b에 0이 들어가면, a%0이 계산이 안된다는 부분 놓침 

(정답)
def gcd(a : int, b : int) -> int :
  if b == 0 :
    return a
  else :
    return gcd(b, a%b)   

* math.gcd(a,b), math.factorial(a)ㅊㅍ ㅌ

• 간접 재귀 : a() -> b() -> a()

2. 분석

2-1. 하향식 분석

: 재귀 함수 실행 트리의 가장 위에서부터 하나하나 실행시켜 내려옴 -> 비효율

2-2. 상향식 분석

: 최소 매개변수부터 최대 매개변수까지 밑에서 계산하며 올라옴

2-3. 재귀 알고리즘의 비재귀적 표현

3. 하노이의 탑

3-1. 중요 포인트

• n : 원반의 총 갯수
• x : 시작 막대(1)
• y : 목표 막대(2)
  ** 중간 막대 : 6-x-y

def move(no : int, x:int, y:int) -> int:
  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)

4. 8퀸 문제

이해도 60%