DP (Dynamic Programming) 알고리즘

00 개요

• 목표: 코딩테스트 뽀개기!

01 DP

1. DP란

• Dynamic Programming
• 이전의 값을 재활용하는 알고리즘
• 예) 1 ~ 10 숫자 중 각각 이전 값들을 합한 값 구하기
• 이전의 값을 활용해서 시간복잡도 축소 가능

2. 연습 문제: 백준 11726

• 2×n 타일링
• 링크: https://www.acmicpc.net/problem/11726

1) 문제

• Q:
  • 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 
  • 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

• 입력:
  • 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
• 출력:
  • 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
• 예제 입력 1:

2

• 예제 출력 1:

2

• 예제 입력 2:

9

• 예제 출력 2:

55

2) 사전 계획 수립

• 아이디어
  • A1= 1이고, A2= 2이고, A3= 1+2
  • An = A(n-1) + A(n-2)
  • for문으로 3부터 n까지 반복
  • 이전값과 그 이전값을 더한 후 10007로 나눈 값 저장
• 시간 복잡도
  • for: n > O(n)
• 자료구조
  • 경우의 수 배열 (An): int[]
    • 최댓값: 10006 > INT 가능

3) 실습

# input이 있을 경우
# import sys
# input = sys.stdin.readline
# n = int(input())

n = 9

result = [0, 1, 2] # 초기값 설정
for i in range(3, n+1):
    result.append((result[i-1] + result[i-2])%10007)

print(result[n])

• 결과값 (n = 2)

• 결과값 (n = 9)

Tip

• 어떻게 할지 모르겠을 땐, 하나씩 그려보면서 규칙 찾기 (i.e., 점화식, 위 코드에서 result의 초기값 설정한 것)
• 점화식을 명확하게 세우고 코드 짜기
  • 점화식 (recurrence relation): 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식
• DP는 비교적 코드 길이가 짧음

 

참조

1. 개발자 장고, https://www.youtube.com/watch?v=qLkFBk5-HrY&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=9
2.  
3.