주차 태그를 떼고 그냥 코테 준비에 용이한 형식으로 바꾸기로 했다.
아마 백준 문제 > 단계별로 풀어보기에 있는 순서대로 그냥 풀면서 쓸 것 같음
동적 계획법 (Dynamic Programming)
동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 해결하고, 이미 계산한 결과를 저장해 같은 계산을 반복하지 않도록 하는 알고리즘 기법이다.
핵심은 부분 문제의 결과를 저장해 재사용하는 것.
예를 들어 피보나치 수열을 단순 재귀로 구현하면 같은 값을 계속 다시 계산하게 되어 쉽게 stack overflow가 난다.
값을 계산할 때마다 dp라는 리스트에 저장하고, 필요한 값을 불러와서 쓴다.
계속해서 호출하면서 다시 계산하지 않기 때문에 효율적이다.
ex) 피보나치 점화식
dp[i] = dp[i-1] + dp[i-2]동적 계획법 구현 방식
동적 계획법 구현 방식에는 크게 다음의 두 가지가 있다.
-
Top-Down (Memoization)
: 재귀를 사용하면서 계산한 값을 저장한다. 문제를 재귀적으로 정의하기 쉬울 때 사용하기 좋고, 필요한 상태만 계산한다는 특징이 있다. -
Bottom-Up (Tabulation)
작은 문제부터 순서대로 계산하면서 배열에 값을 채운다. 계산 순서가 명확한 문제에서 주로 사용하며, 재귀 호출이 없어 시간과 메모리 측면에서 더 안정적인 경우가 많다.
보통 바텀업 구조가 주로 사용되는데, DFS 구조로 트리나 그래프를 탐색할 때 탑다운 구조가 사용된다고 한다.
동적 계획법 문제 유형
코딩 테스트에서 등장하는 DP 문제는 몇 가지 대표적인 유형으로 나눌 수 있다.
1) 선형 DP
선형 DP는 현재 상태를 마지막 선택 기준으로 분해하여 이전 몇 개의 상태만으로 점화식을 구성하는 방식이다.
대표 문제
- 피보나치 수열
- 계단 오르기
- 1로 만들기
- 연속 부분 최대합
예시
dp[i] = dp[i-1] + dp[i-2]선형 DP에서 이전 상태만 고려해도 되는 이유
선형 DP 문제는 보통 현재 상태가 바로 이전 몇 개의 상태에 의해서만 결정되는 구조를 가진다.
예를 들어 포도주 시식 문제에서 i번째 잔까지 고려한다고 하면, 가능한 선택은 다음 세 가지뿐이다:
- i번째 잔을 마시지 않는 경우
- i번째 잔만 마시는 경우
- i-1번째와 i번째 잔을 연속으로 마시는 경우
이 경우 각각의 상태는 다음과 같이 이전 상태에서 만들어진다.
- i번째 잔을 마시지 않음 → dp[i-1]
- i번째 잔만 마심 → dp[i-2] + wine[i]
- i-1, i번째 잔을 마심 → dp[i-3] + wine[i-1] + wine[i]
따라서 점화식은 다음과 같이 구성된다.
dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])=> 3잔 연속으로 마시는 경우는 애초에 점화식에 포함되지 않는다.
MOD 연산
경우의 수를 계산하는 DP 문제에서는 값이 매우 빠르게 커지는 경우가 많다.
예를 들어 피보나치 형태의 점화식이나 경우의 수를 세는 문제에서는 값이 지수적으로 증가할 수 있다.
그래서 많은 문제에서 다음과 같이 특정 값으로 나눈 나머지를 출력하도록 요구한다.
dp[i] = (dp[i-1] + dp[i-2]) % MOD그런데 다 계산한 후 출력하려는 값만 나누면 중간에 계산되는 값들이 이미 커져서 범위를 벗어나게 되는 경우도 많은데, 다음과 같이 모든 값들에 대해 미리 나머지 연산을 처리해줘도 된다.
dp[i] = ((dp[i-1] % MOD) + (dp[i-2] % MOD)) % MOD모듈러 연산의 법칙에 의해, 위의 두개는 완전히 같다.
따라서 값이 커지기 전에 % MOD를 적용할 수 있고 메모리 초과나 큰 정수 연산을 방지할 수 있다.
2) 냅색 유형 (Knapsack)
제한된 용량 안에서 최대 가치나 가능한 경우의 수를 구하는 문제 유형이다. 보통 2차원 DP를 사용하며, 물건을 선택할지 말지 결정하는 구조.
대표 문제
- 0/1 Knapsack
- 동전 거스름돈
- 부분 집합 합
예시
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value)3) LIS 유형 (Longest Increasing Subsequence)
수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제다.
이전 원소들 (혹은 이후 원소들)과 비교하며, 수열 기반 DP를 진행한다.
대표 문제
- LIS (최장 증가 부분 수열)
- 전깃줄 문제
예시
dp[i] = max(dp[j] + 1) (j < i, arr[j] < arr[i])4) 문자열 DP
두 문자열을 비교하거나 편집하는 문제에서 자주 등장한다.
이것도 보통 2차원 DP이며, 문자열 prefix 기반으로 비교한다.
대표 문제
- LCS (최장 공통 부분 수열)
- Edit Distance
예시
dp[i][j] = max(dp[i-1][j], dp[i][j-1])5) 구간 DP
배열이나 문자열을 구간 단위로 나누어 해결하는 DP이다.
구간의 길이를 늘려가며 계산한다.
예시
dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost)