0919 알고리즘

재귀

- 핵심 : 문제를 유사한 형태의 작은 조각으로 나누기

- 활용 : 분할 정복 또는 동적계획법 등의 다양한 알고리즘 활용됨. 반복문 대체

 

문제1. factorial 구하기

f(n) = n!

f(n) = n * f(n-1) (f(n) = 1, if <= 1)

1) 내장함수

import math

math.factorial(20)

for i in range(1, 20) :
	print(math.factorial(i))

2) 재귀

def factorial(n) :
	if n <= 1 :
    	return 1
    else :
    	return n * factorial(n-1)
        
n = 50 <<!!

for i in range(1, n) :
	print("factorial of ", i, factorial(i))

* 시스템에서 최대 재귀 호출은 얼마나 될까? : 999

 

3) 반복문

def factorial(n) :
	result = 1
    for i in range(2, n+1) :
    	result *= i
    return result
    
n = 50
for i in range(1, n) :
	print("factorial of ", i, factorial(i))

 

4) Reduce 함수 (Python)

from functools import reduce

def factorial_reduce(n):
	return reduce(lambda x,y : x*y, range(1, n+1))
    
for i in range(1, 20) :
	print(factorial_reduce(i))

 

5) 재귀 방법 개선

cache = {}

def factorial_recursive(n) :
	global cache
    
    if n in cache :
    	return cache[n]
    elif n <= 1 :
    	return 1
    else :
    	cache[n] = n*factorial_recursive(n-1)
        return cache[n]
        
    return n * factorial_recursive(n-1) if n>1 else 1
    
for i in range(1, 100) :
	print(factorial_recursive(i))

* 이미 계산한 값 기억하기

=> 동적 프로그래밍 기법

 

 

문제2. 피보나치 수열

fibo(n) = fibo(n-1) + fibo(n-2)

(fibo(0) = 0, fibo(1) = 1)

1) 재귀

# 내가 쓴 코드
def fibo(n) :
    if n <= 2 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)

n = int(input())

print(fibo(n))


# 깔끔한 코드
def fibo(n):
return fibo(n-1) + fibo(n-2) if n >= 2 else n

for n in range(1, 11):
print(n, fibo(n))

* 재귀 이용 시 문제점

예를 들어 fibo(4)를 구할 때,

fibo(4) = fibo(3) + fibo(2)

fibo(3) = fibo(2) + fibo(1) = fibo(1) + fibo(0) + fibo(1)

fibo(2) = fibo(1) + fibo(0)

fibo(2) 즉, fibo(1) + fibo(0)을 필요할 때 마다 구한다.

 

2) 반복문

# 내가 쓴 코드
def fibo(n) :
    pre_sum = 0
    cur_sum = 1
    for _ in range(1, n) :
        tmp = cur_sum
        cur_sum += pre_sum
        pre_sum = tmp

    return cur_sum

n = int(input())
print(fibo(n))

# 바람직한 코드
def fibo(n) :
    if n < 2 :
        return n

    a, b = 0, 1
    for i in range(n-1) :
        a, b = b, a+b

    return b

for n in range(1, 11) :
    print(n, fibo(n))

3) 재귀 개선

def fibo(n) :
    if n <= 2 :
        return n
    
    cache = [0 for _ in range(n+1)]
    cache[1] = 1

    for i in range(2, n+1) :
        cache[i] = cache[i-1] + cache[i-2]

    return cache[n]

n = int(input())

print(fibo(n))

-> 동적 프로그래밍

 

 

문제3. 순열 찾기