동적 프로그래밍(Dynamic Programming): 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘
DP의 사용 조건
1) Overlapping Subproblems(겹치는 부분 문제)
재활용!!!!
2) Optimal Substructure(최적 부분 구조)
부분의 최적 결과로 전체의 최적 결과를 구하는 것
피보나치 수열을 예시로 들어보자
무난한 피보나치 수열이다. 시간복잡도는 2^n이다.
여기 재귀적인 동적 프로그래밍을 적용해보자. 한번 계산한 값을 재활용하는 것이다!!
이렇게 풀면 시간복잡도는 n이다.
과정
1.변수 구하기
2.점화식 세우기
3.메모하기
4.기저 상태 파악
방식
Bottom-Up 방식:아래부터 반복문,점화식으로 전이시켜 구하는 것
Top-Down 방식:위부터 전부 호출한 후 재귀로 전이시켜 구하는 것
예제를 풀어보자
백준 1932번 정수 삼각형,프로그래머스 레벨 3
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
코드가 좀 난잡한 것 같다...
동적프로그래밍은 처음이라서 그런 것 같다.
이차원 배열을 쓰면 더 좋을 것 같다.
map함수로 배열의 요소를 int로 바꾸었다.
i번째 줄과 i+1번째 줄을 연산하고 그대로 배열에 다시 저장했다가 다음 줄에 사용하였다.
index는 i번째 줄의 요소를 가리키고 j는 i+1번째 줄의 요소를 가리킨다.
맨 처음,맨끝,중간을 조건문으로 분기하였다.
checkEnd를 쓴 이유는 index값이 바뀌기 때문이다.
다른 예제도 풀어보자
백준 1149번 RGB거리
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
정수 삼각형 쉬운 버전같다. 거의 같은 방식이다.
+파이썬 리스트 마이너스?? 다루는게 너무 헷갈린다.
ex) [1,2,3]
[::-1] -> 3,2,1
[-2:] -> 2,3
[-1:-3:-1] -> 3,2
좀 더 심화된 예제를 풀어보자
백준 11053번 가장 긴 증가하는 부분 수열
Long Increase Series,LIS라고 부른다.
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
너무 어렵다...
못 풀고 그냥 풀이를 봤는데 생각보다 간단해서 아쉬웠다..
그냥 dp 배열을 만들고 어떤 수 n이 있으면 n 보다 작은 수의 이전 dp 배열 중 가장 큰 값을 찾아 1을 더해주면 되는거였다.
파이썬에서 그냥 숫자 한개는 iterable이 아니지만 1,2는 iterable인 것 같다. 그래서 max(1,2,3)하면 3이 나오지만 max(1)하면 int는 안된다고 오류가 난다.
마지막으로 하나만 더 풀어보자
백준 2579번 계단 오르기
https://www.acmicpc.net/problem/2579
혼자 못풀겠어요..
dp 배열에다가 '이전 상태',즉 그 인덱스까지의 최댓값을 저장해놓고 bottom-up으로 풀 수 있다... 점화식 두개가 나오고 둘 중에 큰걸로 선택해 dp배열에 저장하는 방식이다.
4문제 풀면서 느낀점
1.dp는 '이전 상태의 저장 및 재활용'이 핵심인 것 같다.
2.어려운 문제여도 경우를 나눠 각각 점화식을 세우면 풀 수 있는 것 같다.
3.많이 풀어보자
