[Step 9] 동적 계획법

동적 계획법

⇒ 복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법

⇒ 중복 계산을 줄이기 위해, 이전에 구한 해를 활용

이전의 해를 활용해야 효율적인 문제의 조건

• 최적 부분 구조
  • 문제의 최적 해결책이 하위 문제의 최적 해결책으로부터 구성되는 경우
• 중복 부분 문제
  • 동일한 하위 문제가 여러번 계산 됨

예시 1 : 팩토리얼

예시 2 : 피보나치 수

동적 계획법 적용하는 법

예시 1 : 계단 오르기

⇒N개의 계단이 존재하고, 한번에 1개 혹은 2개의 계단을 오를 수 있음. 계단을 오르는 방법의 총 수는?

1. 예제 입력으로 출력을 만드는 과정을 직접 손으로 작성

2. 과정을 일반화. 이때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인한다.

3. 2번의 과정에서 이전해를 구하는 과정이 중복되는지 확인

#include <iostream>
#include <vector>

// 최적 부분 구조:
// 현재 계단에 도달하는 방법은 이전 계단에서 한 계단 오르거나, 
// 두 계단 아래에서 두 계단 오르는 두 가지 방법으로 나뉩니다.
// 즉, f(n) = f(n-1) + f(n-2)의 형태로 나타낼 수 있습니다.

// 중복 부분 문제:
// 동일한 부분 문제(예: f(n-1), f(n-2))가 여러 번 반복되어 계산됩니다.
// 동적 계획법을 사용하면 이러한 중복 계산을 피할 수 있습니다.

int countWays(int n);

int main() {
    int n;
    std::cout << "계단의 수를 입력하세요: ";
    std::cin >> n;

    int result = countWays(n);
    std::cout << "계단을 오르는 방법의 총 수: " << result << std::endl;

    return 0;
}

// 계단을 오르는 방법의 총 수를 계산하는 함수
int countWays(int n) {
    // 동적 계획법을 위한 배열 선언
    std::vector<int> dp(n + 1);

    // 초기값 설정
    dp[1] = 1; // 계단 1개를 오르는 방법은 1가지
    dp[2] = 2; // 계단 2개를 오르는 방법은 2가지 (1+1 또는 2)

    // 동적 계획법을 이용한 계산
    // 점화식: dp[i] = dp[i - 1] + dp[i - 2]
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

 

예시 2 : 만들 수 있는 정사각형 갯수

⇒ 사각형이 주어질 때 만들 수 잇는 정사각형의 갯수 확인

1. 예제 입력으로 출력을 만드는 과정을 직접 손으로 작성

 

2. 과정을 일반화. 이때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int ROW = 3;
const int COL = 4;

// 최적 부분 구조:
// 현재 셀에서 만들 수 있는 정사각형의 크기는 
// 위쪽, 왼쪽, 왼쪽 위 대각선 셀에서 만들 수 있는 정사각형 크기의 최솟값에 1을 더한 값입니다.

// 중복 부분 문제:
// 동일한 부분 문제(예: 위쪽, 왼쪽, 왼쪽 위 대각선 셀)가 여러 번 계산됩니다.

// 점화식:
// dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

int countSquares();

int main() {
    int result = countSquares();
    cout << "만들 수 있는 정사각형의 총 개수: " << result << endl;
    return 0;
}

// ROW x COL 크기의 사각형에서 만들 수 있는 모든 정사각형의 개수를 계산하는 함수
int countSquares() {
    vector<vector<int>> dp(ROW, vector<int>(COL, 1)); // 모든 값을 1로 초기화

    // 동적 계획법을 이용한 계산
    for (int i = 1; i < ROW; ++i) {
        for (int j = 1; j < COL; ++j) {
            // dp[i][j]는 현재 셀에서 만들 수 있는 가장 큰 정사각형의 크기를 나타냄
            dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
								           //위             왼        왼쪽 대각선
        }
    }

    int totalSquares = 0;
    // 모든 dp 값 합산
    for (int i = 0; i < ROW; ++i) {
        for (int j = 0; j < COL; ++j) {
            totalSquares += dp[i][j];
        }
    }

    return totalSquares;
}

 

예시 3 : 최장 증가 부분 수열 (LIS)

• 부분 수열
  • 주어진 수열 중 일부를 뽑아 새로 만든 수열 → 순서는 유지

• 최장 증가 부분 수열
  • 주어진 수열 중 일부를 뽑아 새로 만든 부분 수열 중, 오름차순을 유지(같은 값이 있으면 안된다.)하면서 가장 긴 수열

1. 예제 입력으로 출력을 만드는 과정을 직접 손으로 작성

2. 과정을 일반화. 이때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 동적 계획법을 사용하여 최장 증가 부분 수열(LIS)을 계산하는 함수
int lis(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1); // 각 원소를 초기값 1로 초기화

    // LIS 계산
    for (int i = 1; i < n; ++i) { // arr[i]를 마지막 원소로 하는 LIS 계산
        for (int j = 0; j < i; ++j) { // arr[j] (0 <= j < i)를 마지막 원소로 하는 LIS 고려
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) { 
              //arr[i]가 arr[j]보다 크고
	            // dp[i]가 dp[j] + 1보다 작으면
                dp[i] = dp[j] + 1; // dp[i] 갱신
            }
        }
    }

    // dp 배열 중 최댓값이 LIS 길이
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80}; // 예시 배열
    cout << "LIS 길이: " << lis(arr) << endl;

    return 0;
}

 

출처

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런