동적 프로그래밍(다이나믹 프로그래밍)의 목적은?
메모리를 사용해서 중복 연산을 줄이고, 수행 속도를 개선하는 것
여기서 메모리를 사용한다는 것은! 배열 혹은 자료구조를 만든다는 것이다.
이를 통해 중복 연산을 줄인다는 것은 연산한 결과를 배열에 담는다는 것이다.
자꾸 다이나믹 프로그래밍이라는 이름이 와닿지 않아서 모호해지고, 응용이 어려워지는 것 같다.
한 교수님은 이것을 기억하기 알고리즘이라고 말했는데 그렇게 생각하고 풀어보자.
동적 프로그래밍 알고리즘 문제를 알아보고 구분하는 방법
이 풀이법은 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화할 때 고려될 수 있는 알고리즘이다.
그렇다면 코딩테스트 문제를 보고 dp로 풀어야겠다고 어떻게 알아볼까?
1. dfs/bfs 로 풀 수는 있지만 경우의 수가 너무 많은 문제
2. 경우의 수들에 중복 연산이 많은 경우
위에 해당한다고 했을 때, 각 위치까지 올 수 있는 최적의 값을 기록해가며 활용해보는 것이다. 그렇게 되면 안될 조합들은 미리미리 버려서 중복 연산을 줄일 수 있다.
3. 문제 해결 접근 방법
어떻게 하면 뒤로 돌아가지 않을 수 있을까, 현재까지 잘한 연산을 또 하지 않으려면 어떤 정보를 남겨야지? 어떤 식으로 정보를 남겨야하지?
30분동안 고민해보고, 풀이만 참고해서 풀어보자.
자료 구조가 아니라, 수행 시간을 단축할 수 있는 기법이기 때문에 구현하는 방법은 무궁무진하다.
그러므로 최대한 많은 문제들을 풀어보고 풀이들을 참고하면서 dp 식의 사고방식을 길러가자!
백준 2579번 - 계단 오르기
문제 링크 - https://www.acmicpc.net/problem/2579
즉 문제는 정해진 수열에서 특정 패턴을 가지고 선택해가는 여러 경우의 수 중 점수가 최대값이 되는 경우를 찾아라.
조건
1. +1 혹은 +2 칸 선택
2. 연속으로 3개 선택 불가
3. 마지막 칸 선택해야 함. --> 1번 혹은 2번 칸에서 시작, 마지막 칸에 도착하도록!
그렇다면 dp[n] = dp[i-3] + s[i-1] + s[i] 혹은
dp[n] = dp[i-2] + s[i] 가 될 것이다.
최대값이 되는 방향으로 채워간다.
처음 코드를 작성했을 때는 n=1,n=2 의 경우를 고려하지 않아 인덱스 에러가 계속 발생했다.
그 케이스를 해결하기 위해 문제 조건으로 주어진 최대 개수를 적용해 길이 301의 배열로 각각 정의해주고 시작했다.
import sys
n = int(input())
s = [0] * 301
for i in range(n):
s[i]= int(sys.stdin.readline())
dp = [0] * 301
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n-1])