[코딩 + 알고리즘 완주반] 17일차. 재귀용법, 동적계획법과 분할정복

# 재귀 용법

함수 안에서 동일한 함수를 호출

 

# 일반적인 형태

# 일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

# 일반적인 형태2
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

파이썬에서 재귀함수는 깊이가 1000회 이하가 되어야함

 

# 재귀용법을 활용한 프로그래밍 연습

# 숫자 리스트의 합
def sum_list(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum_list(data[1:])

# 팰린드롬 확인
def palindrome(string):
	if len(string)<=1:
    	return True
	if string[0]==string[-1]:
    	return palindrome(string[1:-1])
    else:
    	return False

def func(n):
	if n==1:
    	return n
    elif n%2==1:
        return func(3*n+1)
    else:
    	return func(n//2)
    
    	

# 정수 n을 1,2,3의 합으로 나타낼 수 있는 방법
def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return func(data -1) + func(data - 2) + func(data - 3)

# 동적계획법(Dynamic Programming)

입력 크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 해를 활용해서 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

상향식 접근법

Memoization (메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 증가

 

# 분할 정복

문제를 나눌수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

하향식 접근법 (일반적으로 재귀함수로 구현)

문제를 잘게 쪼갤때, 부분 문제는 서로 중복되지 않음

 

# 동적계획법과 분할 정복 공통점, 차이점

공통점 : 문제를 잘게 쪼개서 작은 단위로 분할

차이점 : 동적계획법 - 부분 문제는 중복되어 상위 문제 해결 시 재활용됨, Memoization 기법 활용

             분할정복 - 부분 문제는 서로 중복되지 않음 , Memoization 사용 안함

 

# 동적 계획법

피보나치 수열  - f(n) = f(n-1)+f(n-2)

# 재귀 용법 활용
def fib(num):
	if num <=1:
    	return num
    return fib(n-1)+fib(n-2)

# 동적 계획법 활용
def fib_dp(num):
	cache = [0 for index in range(num+1)]
    cache[0]=0
    cache[1]=1
    
    for index in range(2,range(num+1)):
    	cache[index] = cache[index-1]+cache[index-2]
    return cache[num]

동적 계획법 - 배열에 한번 저장된 값은 다시 계산할 필요없이 재사용

                     n이 크면 재귀 함수보다 속도가 빠름