[알고리즘] DP

DP

• Dynamic Programing(동적 계획법)
• 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용
• 반복되는 과정을 줄여서 효율적으로 문제 해결 가능
• DP에서 가장 중요한 것은 점화식을 구하는 것!!
  • DP가 적용 가능한지 판단하는 것이 중요(보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많음)
  • 차근차근 규칙을 찾기!

DP 알고리즘의 성립 조건

• 겹치는 부분 문제
  • 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능
• 최적 부분 구조
  • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우

시간 복잡도

• for문으로 전체 탐색하는 경우 : O(N)

자료 구조

• 방법의 수 배열 : int[]

예시 코드

n=int(input())
count=[0,1,2]

for i in range(3,n+1):
    count.append((count[i-2]+count[i-1])%10007)

print(count[n])