Dynamic Programming

Heath_Jeong·2021년 3월 4일

특징

우리는 컴퓨터의 연산 속도와 메모리 공간을 잘 활용해야 하는 가운데, 메모리 공간을 더 사용하면 연산 속도를 비약적으로 증가시키는 것이 가능!
→ DP (다이나믹 프로그래밍) or 동적 계획법
인접한 항들 사이의 관계식인 점화식을 이용
조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션 (Caching, 캐싱)
- 다이나믹 프로그래밍을 구현하는 한 방법
- 한 번 구한 결과를 메모리 공간에 기록하고 같은 식을 호출하면 기록한 결과를 사용함
큰 문제를 작게 나눈다는 점은 분할 정복과도 같으나, 다이나믹 프로그래밍에서는 문제들이 서로 영향을 준다는 점이 다르다.
→ 퀵 솔트에서 분할 정복 중 피벗을 한 번 잡으면 더이상 그 피벗은 잡지 않음
탑다운 방식 : 재귀로 푸는 DP, 큰 문제를 해결하기 위해 작은 문제를 호출, 메모이제이션 방식
바텀업 방식 : 반복문으로 푸는 DP, 작은 문제부터 차근차근 답을 호출, DP 테이블 (메모이제이션 아님) 에 저장
일반적으로 반복문을 이용한 DP 가 재귀보다 성능이 더 좋음, 전형적인 방법도 바텀업임
시간복잡도 O(N)
: 한 번 본 작은 문제는 더이상 풀지 않고 그대로 사용하기 때문

: 메모이제이션은 계산된 결과를 기록한다는 뜻으로 저장만 하고 다이나믹 프로그래밍에 활용 안 할 수도 있음

일직선 상에 창고들이 있고 창고에는 식량 개수가 적혀있음. 한 창고를 털면, 인접한 창고는 털 수 없음. 털 수 있는 식량의 최댓값을 구하라.

ex)
4 → 8

1 3 1 5

초기값 설정에서 memo[0] = foods[0] 으로 솔루션과 같게 했지만, memo[1] = foods[1] 로 솔루션인 memo[1] = max(foods[0], foods[1]) 과 다르게 구현했다.
⇒ 5 1 2 4 라는 리스트가 주어졌을 때, 나처럼 하면 메모에는 5 1 7 7 로 정답 메모인 5 5 7 9 가 안나옴. 즉, 4번째 칸을 선택할 때 1번째 칸과 4번째 칸의 조합을 선택할 수 없게 되므로 솔루션대로 하는게 맞다.

2xN 바닥을 1x2, 2x1, 2x2 타일로 완전히 채울 수 있는 경우의 수를 구하라. N (1 ≤ N ≤ 1,000)

ex)

3 → 5

점화식을 a(1) = 1, a(2) = 3, a(i) = 2a(i-1) - 1 로 생각했다. 올바른 점화식은 a(i) = a(i-1) + 2a(i-2) 이다.
올바른 접근법은 왼쪽부터 채워나간다고 생각하고, i-1 번째까지 채워진 경우에는 2x1 타일 하나 쓸 수 있고 i-2 번째까지 채워진 경우에는 1x2 타일 두개를 쓰거나 2x2 타일 하나를 쓸 수 있다.
⇒ a(i) = a(i-1) + 2*a(i-2)
사용할 수 있는 타일로 채울 수 있는 크기가 2x2 이기 때문에 i-2 이전에 대해서는 고민할 필요가 없다.