[백준] 가장 긴 증가하는 부분 수열

서론

오늘의 코딩 테스트 문제는 '가장 긴 증가하는 부분 수열'이다. 백준 11053번 문제다. 이 문제를 통해 동적 프로그래밍(DP) 접근법을 복습하고 최적화 과정을 경험했다.

문제 분석

•

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾아야 한다.

•

핵심은 각 원소를 기준으로 이전 원소들과의 관계를 효율적으로 파악하는 것이다.

접근 방식

처음에는 모든 가능한 부분 수열을 생성하는 방식으로 접근했다. 하지만 이는 비효율적이었다. DP를 사용하면 문제를 더 효과적으로 해결할 수 있다는 걸 깨달았다.

각 인덱스까지의 최장 증가 부분 수열 길이를 저장하는 DP 배열을 사용한다.

현재 원소보다 작은 이전 원소들의 DP 값을 확인하며 최대값을 갱신한다.

구현

첫 번째 시도:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;

    cin >> n;

    vector<int> A(n);

    for (int i = 0; i < n; i++)
        cin >> A[i];

    vector<vector<int>> v;

    for (auto a: A)
    {
        for (auto& b: v)
            if (b.back()<a)
                b.push_back(a);
        v.push_back({a});
    }

    int answer = 0;
    for (auto& b: v)
        if (answer<b.size())
            answer = b.size();

    cout << answer << endl;

    return 0;
}
C++
복사

이 방식은 작동은 했지만, 메모리 사용량이 크고 시간 복잡도가 좋지 않았다.

최적화한 두 번째 시도:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    
    vector<int> dp(n, 1); // i까지의 원소를 사용했을 때 가장 긴 증가하는 부분 수열의 길이

    for (int i = 1; i < n; i++)
        for (int j = i; j >= 0; j--)
            if (A[j]<A[i])
                dp[i] = max(dp[i], dp[j]+1);
    
    int answer = 0;
    for (auto d: dp)
        answer = max(answer, d);
    cout << answer << endl;

    return 0;
}
C++
복사

DP를 사용해 공간 복잡도를 O(n)으로, 시간 복잡도를 O(n^2)로 개선했다.

회고

•

DP의 중요성을 다시 한 번 실감했다. 복잡해 보이는 문제도 적절한 접근법으로 단순화할 수 있다.

•

처음부터 최적화된 솔루션을 생각해내기 어려울 때는, 우선 작동하는 코드를 만들고 점진적으로 개선하는 것도 좋은 전략이다.