[Python]동적계획법
동적계획법
- 다이나믹 프로그래밍(Dynamic Programming,DP)라고도 불리며, 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정
동적계획법 접근방법
- Bottom Up 방법 : 작은 문제에서 큰 문제로 반복문 호출
- Top Down 방법 : 큰 문제에서 작은 문제로 재귀 호출
동적계획법 활용
피보나치 수열
- Bottom Up
def fib(n):
fibList=[1,1]
for i in range(2,n+1):
fibList.append(fibList[i-2]+fibList[i-1)
return fbList[-1]
- Top Down
def fib(n):
if n==0 or n==1:
return 1
else:
return fib(n-1)+fib(n-2)
메모이제이션(memoization)
- 앞에서 한 계산을 어딘가에 저장해두고 필요한 경우 불러와서 사용할 수 있도록하여 중복된 계산이 발생 하는것을 방지하는 기법
- 배열 혹은 해시를 활용하는 것이 핵심
memo={0:1,1:1}
def fib(n):
if n in memo:
return memo[n]
else:
result=fib(n-1)+fib(n-2)
memo[n]=result
return reslt
동적계획법 예시
data[3,4,5,6,1,2,5]
이웃하지 않는 숫자들의 합의 최댓값은?
def solution(data):
if len(data)==1:
return data[0]
result= [data[0],max(data[0],data[1]) #메모이제이션할 배열 선언
for i in range(2,len(data)):
result.append(max(result[i-1],result[i-2]+data[i])
return result[-1]
Author And Source
이 문제에 관하여([Python]동적계획법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sxxzin/Python동적계획법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)