EVI$ION 겨울방학 코테스터디 6주차 과제

동적 프로그래밍

동적 프로그래밍(DP)은 큰 문제를 작은 하위 문제로 나누고, 각 하위 문제의 해답을 저장하여 같은 문제를 반복해서 계산하지 않도록 하는 최적화 기법입니다.

핵심 개념

1. 문제의 중복성 (Overlapping Subproblems)
   • 하나의 문제를 여러 개의 작은 문제로 나누었을 때, 같은 하위 문제가 반복적으로 나타나는 경우를 의미합니다.
   • 예: 피보나치 수열 계산 (Fibonacci Sequence)
2. 최적 부분 구조 (Optimal Substructure)
   • 어떤 문제의 최적 해가 부분 문제의 최적 해를 이용하여 구할 수 있는 성질을 의미합니다.
   • 예: 최단 경로 문제 (Shortest Path)
3. 메모이제이션 (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) (추가 배열 없이 변수만 사용)

---

동적 프로그래밍이 사용되는 문제

1. 최적화 문제
   • 예: 최소 비용 경로(Minimum Cost Path), 배낭 문제(Knapsack Problem), 연쇄 행렬 곱셈(Matrix Chain Multiplication)
2. 경로 찾기 문제
   • 예: 최장 증가 부분 수열(Longest Increasing Subsequence), 최단 경로(Dijkstra, Floyd-Warshall)
3. 문자열 문제
   • 예: 최장 공통 부분 수열(Longest Common Subsequence, LCS), 편집 거리(Edit Distance)

---

동적 프로그래밍 문제 해결 방법

1. 문제를 작은 하위 문제로 나눌 수 있는지 확인한다.
2. 중복되는 하위 문제가 있는지 확인한다.
3. 최적 부분 구조를 만족하는지 확인한다.
4. 메모이제이션(Top-down) 또는 테이블화(Bottom-up) 방식 중 선택한다.
5. 가능하면 공간 최적화를 고려한다.

---

정리

• 동적 프로그래밍은 중복 계산을 줄여 연산 속도를 최적화하는 기법이다.
• 재귀 + 메모이제이션(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	200

1일날 상담을 하게되면 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;
}

 

 

 

참고: https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-14501%EB%B2%88-%ED%87%B4%EC%82%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-c-%ED%92%80%EC%9D%B4