[파이썬][알고리즘]다이나믹 프로그래밍

 

다이나믹 프로그래밍

연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야하는데 

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법의 대표적인 방법

 

 

피보나치 수열을 재귀 함수로 구현

def fibo(x):
	if x==1 or x==2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

 

1.큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

위의 두 가지 조건을 만족할 때 다이나믹 프로그래밍을 사용 할 수 있다.

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다.

 

메모이제이션기법이란?

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면

메모한 결과를 그대로 가져오는 기법을 의미한다.

메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 함

 

d=[0]*100

def fibo(x):
	if x==1 or x==2:
    	return 1
    if d[x] != 0:
    	return d[x]
    
    d[x]=fibo(X-1)+fibo(x-2)
    return d[x]

print(fibo(99))

 

요약

다이나믹 프로그래밍이란 큰 문제를 작게 나누고 

같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘

d=[0]*100

d[1]=1
d[2]=1
n=99

for i in range(3,n+1)
	d[i]=d[i-1]+d[i-2]

print(d[n])

->보텀업 다이나믹 프로그래밍 반복문으로 구현

 

일반적으로 재귀 함수보다 반복문을 이용한 경우가 오버헤드를 줄일 수 있고 다이나믹 프로그래밍 성능이 더 좋음

재귀 함수는 탑다운 방식;하향식

큰 문제를 해결하기 위해 작은 문제를 호출

반복문을 이용하는 보텀업 방식;상향식

작은 문제부터 차근차근 답을 도출

탑다운보다는 보턴 업 방식을 권장

 

 

코딩 테스트에서 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 

해결하고자 하는 부분 문제들의 중복 여부를 확인해보고 다이나믹프로그래밍을 고려

 

*'이것이 취업을 위한 코딩 테스트다 with 파이썬'을 보고 요약, 정리한 내용입니다.