EVI$ION 겨울방학 코테스터디 6주차 과제
동적 프로그래밍
동적 프로그래밍(DP)은 큰 문제를 작은 하위 문제로 나누고, 각 하위 문제의 해답을 저장하여 같은 문제를 반복해서 계산하지 않도록 하는 최적화 기법입니다.
핵심 개념
- 문제의 중복성 (Overlapping Subproblems)
- 하나의 문제를 여러 개의 작은 문제로 나누었을 때, 같은 하위 문제가 반복적으로 나타나는 경우를 의미합니다.
- 예: 피보나치 수열 계산 (Fibonacci Sequence)
- 최적 부분 구조 (Optimal Substructure)
- 어떤 문제의 최적 해가 부분 문제의 최적 해를 이용하여 구할 수 있는 성질을 의미합니다.
- 예: 최단 경로 문제 (Shortest Path)
- 메모이제이션 (Memoization) 또는 테이블화 (Tabulation)
- 메모이제이션: 하향식(Top-down) 접근 방식으로, 이미 계산된 값을 저장하여 필요할 때 재사용하는 기법
- 테이블화: 상향식(Bottom-up) 접근 방식으로, 작은 문제부터 차례로 해결하여 최종 해답을 구하는 방식
예제: 피보나치 수열
피보나치 수열을 DP 없이 재귀로 구현하면 중복 계산이 많아 비효율적입니다.
1. 단순 재귀 (비효율적)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
- 시간 복잡도: O(2n)O(2^n) (지수 시간)
- 중복 계산: 동일한 값이 여러 번 계산됨
2. 동적 프로그래밍 - 메모이제이션 (Top-down)
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
- 시간 복잡도: O(n)O(n) (선형 시간)
- 공간 복잡도: O(n)O(n) (재귀 호출로 인한 스택 사용)
3. 동적 프로그래밍 - 테이블화 (Bottom-up)
def fib_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
- 시간 복잡도: O(n)O(n) (선형 시간)
- 공간 복잡도: O(n)O(n) (배열 사용)
4. 공간 최적화
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
- 시간 복잡도: O(n)O(n)
- 공간 복잡도: O(1)O(1) (추가 배열 없이 변수만 사용)
동적 프로그래밍이 사용되는 문제
- 최적화 문제
- 예: 최소 비용 경로(Minimum Cost Path), 배낭 문제(Knapsack Problem), 연쇄 행렬 곱셈(Matrix Chain Multiplication)
- 경로 찾기 문제
- 예: 최장 증가 부분 수열(Longest Increasing Subsequence), 최단 경로(Dijkstra, Floyd-Warshall)
- 문자열 문제
- 예: 최장 공통 부분 수열(Longest Common Subsequence, LCS), 편집 거리(Edit Distance)
동적 프로그래밍 문제 해결 방법
- 문제를 작은 하위 문제로 나눌 수 있는지 확인한다.
- 중복되는 하위 문제가 있는지 확인한다.
- 최적 부분 구조를 만족하는지 확인한다.
- 메모이제이션(Top-down) 또는 테이블화(Bottom-up) 방식 중 선택한다.
- 가능하면 공간 최적화를 고려한다.
정리
- 동적 프로그래밍은 중복 계산을 줄여 연산 속도를 최적화하는 기법이다.
- 재귀 + 메모이제이션(Top-down) 또는 반복 + 테이블화(Bottom-up) 방식으로 해결할 수 있다.
- 최적 부분 구조와 중복 부분 문제가 존재하는 경우에 사용할 수 있다.
2579, 계단 오르기, C++
계단 오르기 규칙
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오른다.
2. 연속된 세개의 계단 밟는 거x(시작점 계단 포함x)
3. 마지막 도착 계단은 반드시 밟아야 한다.
총 점수의 최댓값을 구하기
stair[i] : i번째 계단의 점수
dp[i] : i번째 계단까지 올라왔을때 얻을 수 있는 최대 점수 저장
#include <iostream>
#include <algorithm> // max() 함수 사용
using namespace std;
int n;
int stair[301]; // 계단 점수 저장 배열
int dp[301]; // DP 배열
void solution() {
// 예외 처리 (계단이 하나만 있을 경우)
if (n == 1) {
cout << stair[1] << endl;
return;
}
// DP 초기값 설정
dp[1] = stair[1]; // 첫 번째 계단 점수
dp[2] = stair[1] + stair[2]; // 첫 번째 계단 + 두 번째 계단 점수
// 점화식 적용 (3번째 계단부터)
for (int i = 3; i <= n; i++) {
dp[i] = max(dp[i-3] + stair[i-1] + stair[i], dp[i-2] + stair[i]);
}
// 최댓값 출력
cout << dp[n] << endl;
}
int main() {
// 입력
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> stair[i];
}
// 연산 및 출력
solution();
return 0;
}일단 첫번째 계단(10점)을 밟고,
두번째 계단을 밟을지, 세번째 계단을 밟을지 결정하기 위해 두 개의 계단의 점수 중 큰 것을 선택.(마지막 계단까지)
11053, 가장 긴 증가하는 부분 수열, C++
수열 A가 주어졌을때, 가장 긴 증가하는 부분 수열(LIS)
부분 수열은 원래 배열에서 순서를 유지하면서 일부 원소를 골라 만든 수열이라서 연속일 필요가 없음!
증가하는 부분 수열은 선택한 숫자들이 오름차순이어야함.
DP로 해결할 수 있다.
배열 dp[i]를 i번째 숫자를 마지막 원소로 하는 LIS(가장 긴 증가하는 부분 수열)의 길이라고 정의한다.
ex) dp[3]=2라면, arr[3]을 끝으로 하는 증가하는 부분 수열의 최대 길이가 2라는 뜻이다.
dp[i]값을 구할 때, i보다 앞에 있는 j 중에서 arr[j]<arr[i]를 만족하는 것들을 찾으려면
그 중에서 dp[j]값이 가장 큰 값을 선택해서 +1를 해준다.
모든 원소는 최소 자기자신만 선택해서 길이가 1이 되어서 dp[i]=1로 초기화시키고 앞의 숫자들을 보면서 dp[i]값을 갱신하면 된다.
| i | arr[i] | dp[i] |
| 1 | 10 | 1 |
| 2 | 20 | 2 |
| 3 | 10 | 1 |
| 4 | 30 | 3 |
| 5 | 20 | 2 |
| 6 | 50 | 4 |
i=1일때, {10}인 자기자신 하나만 있어서 부분 수열 값은 1
i=2일때, {10, 20} dp[2]=2
i=3일때, {10}보다 더 작은 값이 없기때문에 만들어지지 않음 dp[3]=1
i=4일때, {10, 20, 30} dp[4]=3
i=5일때, {10,20} dp[4]=2
i=6일때, {10,20,30,50} dp[6]=4
#include <iostream>
#include <algorithm> // max() 함수 사용
using namespace std;
int n;
int arr[1001]; // 주어진 수열 (최대 1000개)
int dp[1001]; // dp[i]: i번째 원소를 마지막으로 하는 LIS의 길이
void solution() {
int max_length = 1; // LIS 최대 길이
// DP 초기값 설정
for (int i = 1; i <= n; i++) {
dp[i] = 1; // 최소 길이는 1 (자기 자신만 포함)
}
// LIS 점화식 적용
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i]) { // 앞의 값이 현재 값보다 작다면
dp[i] = max(dp[i], dp[j] + 1); // 최댓값 갱신
}
}
max_length = max(max_length, dp[i]); // 최대 길이 갱신
}
// 최댓값 출력
cout << max_length << endl;
}
int main() {
// 입력
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 연산 및 출력
solution();
return 0;
}퇴사
오늘부터 N일동안 상담을 할 수 있음.
각 상담은 T[i] (걸리는 일수)와 P[i] (얻는 금액)이 주어짐.
상담을 하는 동안 다른 상담을 진행불가
1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 2001일날 상담을 하게되면 2일, 3일은 상담불가.
DP 사용
마지막날부터 생각하면 됨.
6,7일은 진행불가.
5일은 2일 걸리니까 6, 7일 삭제, 15
4일은 1일 걸림, 4일 하루만 해두됨, 15+20
3일은 1일 걸림, 3일 하루만 해두됨, 15+20+10
2일은 5일 걸림, 해도 되긴하는데, 그러면 2,3,4,5,6일 삭제됨..., 20
1일은 3일 걸림, 1,2,3일 삭제됨, 10 그럼 4일 (20) 5일(15) 가능, 10+20+15 / 안하면 3일(10)+4일(20)+5일(15)
1일은 하나 안하나 똑같음
10+20+15=45
최대 이익 45
#include <iostream>
using namespace std;
#define MAX 16
int N;
int Ti[MAX]={0,};
int Pi[MAX]={0,};
int res[MAX]={0,};
int Max(int a, int b){
return a>b ? a : b;
}
void Input(){
cin >> N;
for (int i=1; i<=N; i++){
cin >> Ti[i] >> Pi[i];
}
}
void Dp(){
int deadline;
for (int i=N; i>0; i--){
deadline = i + Ti[i];
if (deadline > N+1){
// 상담 불가
res[i] = res[i+1];
}
else {
// 상담 가능, 최대 이익 판별 필요
res[i] = Max(res[i+1], res[deadline] + Pi[i]);
}
}
}
int main() {
Input();
Dp();
cout << res[1] << endl;
return 0;
}