백준 14002번 [가장 긴 증가하는 부분 수열 4](C++) -yes6686- 티스토리

백준 문제 풀이: 14002 [가장 긴 증가하는 부분 수열 4]

---

문제 링크: https://www.acmicpc.net/problem/14002

문제 설명:

주어진 수열에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하고, 해당 수열을 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <stack>
using namespace std;

int arr[1001]; // 입력된 수열
int dp[1001];  // LIS의 길이를 저장하는 배열
stack s;  // LIS를 역추적하여 저장하는 스택

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 수열의 크기
    cin >> n;

    // 수열 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = 1; // 초기화: 각 원소는 자체로 길이 1의 LIS
    }

    int maxAns = 1;         // LIS의 최대 길이
    int maxLastIndex = 0;   // LIS의 마지막 원소의 인덱스

    // LIS 길이 계산
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
                if (maxAns < dp[i]) {
                    maxAns = dp[i];
                    maxLastIndex = i;
                }
            }
        }
    }

    // LIS 길이 출력
    cout << maxAns << '\n';

    // LIS 수열 추적
    s.push(arr[maxLastIndex]);
    for (int i = maxLastIndex - 1; i >= 0; i--) {
        if (arr[maxLastIndex] > arr[i] && dp[maxLastIndex] == dp[i] + 1) {
            s.push(arr[i]);
            maxLastIndex = i;
        }
    }

    // LIS 출력
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 가장 긴 증가하는 부분 수열(LIS)을 계산하고, 역추적을 통해 LIS의 원소를 추출합니다.
• 구현 세부사항:
  • dp[i]: i번째 원소를 포함했을 때의 LIS의 길이
  • 점화식: dp[i] = max(dp[i], dp[j] + 1) (j < i이고 arr[j] < arr[i]일 때)
  • 역추적: 최대 길이를 가지는 마지막 원소에서 시작하여 이전 원소를 스택에 저장
• 시간 복잡도 분석: O(n²)
  • 이중 루프를 통해 각 원소에 대해 이전 원소를 확인하므로 O(n²)

---

결과

가장 긴 증가하는 부분 수열(LIS)의 길이와 해당 수열을 정확히 출력합니다. 동적 프로그래밍과 역추적을 통해 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!