[99클럽/코딩테스트 챌린지/C++] 가장 긴 감소하는 부분 수열 문제 해결 및 동적 계획법(DP) 활용

문제 링크

https://www.acmicpc.net/problem/11722

📝 문제 요약

문제: 주어진 수열에서 순서를 유지하면서 숫자가 점점 작아지는 부분 수열 중 가장 긴 수열의 길이를 구하는 문제.

입력:

• 수열 크기 N (1 ≤ N ≤ 1,000)
• 수열 A (1 ≤ Ai ≤ 1,000)

출력: 가장 긴 감소하는 부분 수열의 길이.

📌 접근법

1. DP 배열 정의

 

dp[i]: i번째 숫자를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다.

 

2. 점화식

• 조건: arr[j] > arr[i] (j < i)인 경우, arr[j]를 arr[i] 앞에 연결할 수 있습니다.
• 점화식: dp[i] = max(dp[i], dp[j] + 1)

3. 초기화

• 각 숫자는 혼자만으로 길이 1의 감소 수열을 만들 수 있으므로, dp[i] = 1로 초기화합니다.

4. 결과 계산

• DP 배열을 모두 계산한 후, 가장 큰 값이 가장 긴 감소하는 부분 수열의 길이입니다.

📌 예시 분석

입력

N = 6  
arr = [10, 30, 10, 20, 20, 10]

계산 과정

1, 초기 상태:

dp = [1, 1, 1, 1, 1, 1]

 

2, 첫 번째 반복 (i = 1):

- j = 0: arr[0] (10) > arr[1] (30) → 조건 불만족.

dp = [1, 1, 1, 1, 1, 1]

 

3, 두 번째 반복 (i = 2):

- j = 0: arr[0] (10) > arr[2] (10) → 조건 불만족.

- j = 1: arr[1] (30) > arr[2] (10) → dp[2] = dp[1] + 1 = 2.

dp = [1, 1, 2, 1, 1, 1]

 

4, 세 번째 반복 (i = 3):

- j = 0: arr[0] (10) > arr[3] (20) → 조건 불만족.

- j = 1: arr[1] (30) > arr[3] (20) → dp[3] = dp[1] + 1 = 2.

- j = 2: arr[2] (10) > arr[3] (20) → 조건 불만족.

dp = [1, 1, 2, 2, 1, 1]

 

5, 세 번째 반복 (i = 4):

- j = 0: arr[0] (10) > arr[4] (20) → 조건 불만족.

- j = 1: arr[1] (30) > arr[4] (20) → dp[4] = dp[1] + 1 = 2.

- j = 2: arr[2] (10) > arr[4] (20) → 조건 불만족.

- j = 3: arr[3] (20) > arr[4] (20) → 조건 불만족.

 

dp = [1, 1, 2, 2, 2, 1]

6, 세 번째 반복 (i = 5):

- j = 0: arr[0] (10) > arr[5] (20) → 조건 불만족.

- j = 1: arr[1] (30) > arr[5] (20) → dp[5] = dp[1] + 1 = 2.

- j = 2: arr[2] (10) > arr[5] (20) → 조건 불만족.

- j = 3: arr[3] (20) > arr[5] (20) → 조건 불만족.

- j = 3: arr[4] (20) > arr[5] (10) → dp[5] = dp[4] + 1 = 3.

dp = [1, 1, 2, 2, 2, 3]

 

 

 

7, 최종 결과

 

dp = [1, 1, 2, 2, 2, 3]

전체 코드

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

vector<int> arr;

int main()
{

	int N;
	std::cin >> N;
	arr = vector<int>(N);
	for (size_t i = 0; i < N; i++)
	{
		std::cin >> arr[i];
	}

	// DP를 1로 다 초기화 한다.
	vector<int> dp = vector<int>(N,1);
	
	// 입력 받은 배열을 순차적으로 순회한다.
	for (int i = 0; i < N; i++) {
		// 현재 배열의 인덱스를 기준으로 역순한다.
		for (int j = i; j >= 0; j--) {
			// 역순하면서 현재 배열보다 큰 배열이 존재할 경우 
			// 현재 배열의 순열의 갯수와 이전 순열의 갯수 + 1을 비교하여 
			// 더 큰 값을 가지는 값으로 갱신한다.
			if (arr[i] < arr[j]) {
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
	}

	// 현재 DP에서 가장 큰 값을 찾는다.
	int answer = *std::max_element(dp.begin(), dp.end());

	std::cout << answer << '\n';

    return 0;
}

📌 배운 점

1, 동적 계획법(DP)의 유용성:

• 현재 상태(dp[i])를 이전 상태(dp[j])와의 관계로 정의하여 문제를 해결할 수 있었습니다.
• 점화식 구성과 초기화가 핵심임을 느꼈습니다.

2, 문제를 작은 단계로 나누는 방법:

• 단순히 조건을 만족하는 값을 찾는 것이 아니라, 조건을 만족하는 모든 경우 중 최적의 값을 선택하는 사고방식이 중요했습니다.

3, DP 배열의 의미 이해:

• dp[i]가 "현재 숫자를 마지막으로 하는 가장 긴 감소 부분 수열의 길이"라는 정의를 명확히 이해해야 코드를 구현할 수 있었습니다.

4, 효율적인 계산:

• 이중 반복문을 사용하더라도 시간 복잡도가 O(N²) 이내로 해결 가능하며, 조건에 따라 최적화 여지가 있음을 확인했습니다.

📌 느낀 점

이번 문제를 통해 "부분 수열"을 다룰 때, 순서 유지라는 조건을 놓치지 않고 문제를 접근하는 법을 익혔습니다. 처음에는 점화식을 명확히 세우는 것이 어려웠지만, 반복적으로 작은 단계를 나누어 생각하면서 점화식을 도출할 수 있었습니다. 앞으로 DP 문제를 해결할 때, "현재 상태와 이전 상태의 관계"를 명확히 정의하는 연습을 더 해야겠다고 느꼈습니다! 😊