C++ 코딩테스트 강좌, 가장 길게 증가하는 부분 수열 찾기

문제 설명

주어진 정수 배열에서 가장 길게 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾아야 합니다.
부분 수열은 원본 배열에서 요소의 순서를 유지하며 선택된 요소들로 구성됩니다.
이 문제는 동적 프로그래밍(Dynamic Programming) 또는 이분 탐색(Binary Search)을 통해 해결할 수 있습니다.

예시

입력: [10, 9, 2, 5, 3, 7, 101, 18]
출력: 4 (가장 긴 증가하는 부분 수열: [2, 3, 7, 101])

문제 접근 방법

이 문제를 해결하기 위한 방법은 여러 가지가 있습니다. 가장 대표적인 방법은 동적 프로그래밍을 사용하는 것이며,
이 방법은 O(N^2)의 시간 복잡도를 가집니다. 그러나 이 문제는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로도 해결할 수 있습니다.

1. 동적 프로그래밍(Dynamic Programming) 접근법

동적 프로그래밍 접근법의 핵심은 ‘중간 결과’를 저장하여, 동일한 계산을 반복하지 않도록 하는 것입니다.
다음과 같은 단계로 진행합니다.

길이를 저장하기 위한 dp 배열을 초기화합니다. dp[i]는 i번째 인덱스의 원소를 끝으로 하는
증가하는 부분 수열의 최대 길이를 저장합니다.
이중 반복문을 통해 각 원소를 비교하고, dp 배열을 업데이트합니다.
i번째 원소가 j번째 원소보다 클 경우, dp[i]를 max(dp[i], dp[j] + 1)로 설정합니다.
최종적으로 dp 배열의 최대 값을 찾아 출력합니다.

코드 (동적 프로그래밍)


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    if (nums.empty()) return 0;
    vector dp(nums.size(), 1);
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "가장 길게 증가하는 부분 수열의 길이: " << lengthOfLIS(nums) << endl;
    return 0;
}

2. 이분 탐색(Binary Search) 접근법

이 방법은 더 효율적이며, O(N log N)의 시간 복잡도를 가집니다. 이 방법의 기본 아이디어는
‘부분 수열의 끝 요소들을 저장하는 배열’을 유지하는 것입니다.

결과를 저장할 배열을 초기화합니다.
각 원소에 대해 다음을 수행합니다:
- 현재 숫자가 result 배열의 마지막 원소보다 크면 배열에 추가합니다.
- 그렇지 않으면 이분 탐색을 통해 현재 숫자가 들어갈 위치를 찾은 후 대체합니다.
결과 배열의 크기가 가장 길게 증가하는 부분 수열의 길이가 됩니다.

코드 (이분 탐색)


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    vector tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "가장 길게 증가하는 부분 수열의 길이: " << lengthOfLIS(nums) << endl;
    return 0;
}

결론

“가장 길게 증가하는 부분 수열 찾기” 문제는 다양한 방법으로 해결할 수 있는 알고리즘 문제입니다.
문제 해결을 위한 접근 방법을 이해하고 구현하는 것은 코딩 테스트에서 큰 도움이 됩니다.
이 문제를 통해 동적 프로그래밍 및 이분 탐색의 기초를 익히고, 다양한 알고리즘 문제에 적용하는 능력을 키워보세요.