다이나믹 프로그래밍 - 파이썬

그래도 겁이 나던 코딩테스트가 하나씩 풀려가니까 기분이 좋기도 하다. 더 열심히 해야겠다.

---

 

아래 자료는 [이코테] 6.다이나믹 그래핑 강의를 참고했습니다.

https://www.youtube.com/watch?v=5Lu34WIx2Us 

---

다이나믹 프로그래밍 ⇒ 동적 계획법 

• 이미 계산된 결과(작은 문제)는 별도의 메모리에 저장하여 다시 계산하지 않도록 한다 
• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 탑다운과 보텀업으로 구성 

 

대표적인 문제 : 피보나치 수열 

1,1,2,3,5,8,13,21,34,55,89,...

#피보나치 함수를 재귀함수로 구현 
def fibo(x) : 
	if x == 1 or x ==2 :
    	return 
     return fibo(x-1) + fibo(x-2) 

print(fibo(4))

#실행결과 
3

---

메모이제이션 

: 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다 (이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 의미) 

 

■ 피보나치 수열 : 탑다운 dp 코드

#한 번 계산된 결과를 메모이제이션 하기 위해 리스트 초기화 
dp = [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(fibo(6)) 
#실행결과 
8

■ 피보나치 수열 : 보텀업 dp 코드 

#앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화 
d = [0] * 100

#첫번째 피보나치 수 와 두번째 피보나치 수는 1 
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[6])

---

 

< 문제1 > 개미전사 

 

내가 풀던 방식 (완전탐색)

n = int(input())
arr = list(map(int,input().split())) 

answer = 0

def recur(idx, k) :
    global answer

    if idx > n+1 :
        return 
    if idx >= n :
        answer = max(answer , k )
        return answer
    
    #만일 선택을 했을 경우 
    recur(idx+2 , k + arr[idx])
    #만일 선택을 안했을 경우 
    recur(idx+1 , k)

recur(0,0)
print(answer)

 

보텀업 DP

 

창고가 존재함에 따른 최적의 해 계산

 

창고 0 만 존재 할 때:  1 

창고 0,1 만 존재할 때 : 3 

창고 0,1,2만 존재할 때 : 3

창고 0,1,2,3까지 존재할 때 : 8  

 

왼쪽부터 식량찬고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정 

n = int(input())
arr = list(map(int,input().split()))


#앞서 계산된 결과를 저장하기 위해 dp 테이블 초기화 
d = [0]*100

d[0] = arr[0]
d[1] = max(arr[0],arr[1]) 

#다이나믹 프로그래밍 진행 
for i in range(2,n) :
	d[i] = max(d[i-1], d[i-2] + arr[i]) 

print(d[n-1])