C++ 코딩테스트 강좌, 시간 복잡도 활용하기

코딩 테스트를 준비하면서 가장 중요한 것 중 하나는 문제 해결 능력과 함께 시간 복잡도를 이해하고 최적화하는 것입니다. 이 글에서는 C++을 사용하여 시간 복잡도를 고려하여 문제를 해결하는 과정을 자세히 설명하겠습니다.

문제: 최장 증가 부분 수열 (Longest Increasing Subsequence)

주어진 정수 배열에서 최장 증가 부분 수열의 길이를 구하는 문제입니다.

문제 설명

정수 배열 nums가 주어졌을 때, 증가하는 부분 수열의 가장 긴 길이를 반환하시오. 부분 수열은 배열에서 선택된 원소들이 원래의 순서를 유지해야 하지만 연속적일 필요는 없습니다.

예제

    입력: nums = [10, 9, 2, 5, 3, 7, 101, 18]
    출력: 4
    설명: 최장 증가 부분 수열은 [2, 3, 7, 101]로, 길이는 4입니다.
    

접근 방법

이 문제는 동적 계획법(Dynamic Programming)과 이진 검색(Binary Search)을 조합하여 해결할 수 있습니다. 시간 복잡도를 고려하여 다음과 같은 접근 방법을 사용할 수 있습니다:

1. 동적 계획법을 이용한 접근

우선, 각 원소마다 자신을 마지막 원소로 하는 증가 부분 수열의 길이를 기록합니다. 그러면 각 요소를 순회하며 이전의 모든 요소와 비교하여 가능하면 부분 수열의 길이를 업데이트할 수 있습니다.

2. 이진 검색과 결합

최종적으로 우리는 부분 수열의 끝 원소를 기록하기 위한 배열을 사용하고, 이 배열에서 각 요소에 대해 이진 검색을 적용하여 현재 원소를 삽입할 위치를 찾습니다. 이 방법을 통해 더 최적화된 성능을 달성할 수 있습니다.

구현

다음은 C++로 이 문제를 해결하는 코드입니다:

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

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;

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

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

시간 복잡도 분석

이 문제의 시간 복잡도는 O(n log n)입니다. 각각의 원소에 대해 이진 검색을 수행하여 적절한 위치를 찾고, 이진 검색의 시간 복잡도는 log n입니다. 따라서 전체적인 시간 복잡도는 O(n log n)이고, 공간 복잡도는 O(n)입니다.

결론

이와 같은 문제는 배열에서 최장 증가 부분 수열을 찾는 것처럼, 시간 복잡도를 줄이기 위해 동적 계획법과 이진 검색을 조합하는 것이 중요합니다. C++의 STL에서 제공하는 유용한 함수와 자료구조를 잘 활용하면 더욱 효율적인 코드를 작성할 수 있습니다.

이 글에서는 C++를 사용하여 시간 복잡도 분석과 이를 활용한 알고리즘 문제 해결 방법을 설명했습니다. 앞으로의 코딩 테스트 준비에 도움이 되었기를 바랍니다!