99클럽 코테 스터디 22일차 TIL C++ DP, LDS, lower_bound

오늘의 학습 키워드

문제1: 가장 긴 감소하는 부분 수열 (BOJ 11722)

공부한 내용 정리

접근 방식

가장 긴 감소하는 수열을 찾기 위해서는 각 원소가 이전 원소들과의 관계를 확인하여, 그중 가장 긴 감소하는 길이를 찾아야 합니다. 단순히 원소들 간의 크기만 비교하는 것이 아니라, 현재 원소가 이전 원소들과 어떻게 연결되는지를 계산하여 가장 긴 감소하는 경로를 찾아야 합니다.

dp 배열은 각 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 각 원소를 순회하면서 자신보다 작은 이전 원소를 찾아, 그 원소를 기준으로 감소 수열의 최대 길이를 갱신합니다. 이를 통해 모든 원소에 대해 가능한 가장 긴 감소 수열을 구할 수 있습니다.

for (int j = 0; j < i; j++) {
    if (sequence[j] > sequence[i]) { // 감소 조건
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

이 코드의 핵심은 dp 배열이 현재 위치에서 만들 수 있는 가장 긴 감소 수열의 길이를 저장하는 것입니다. 각 원소를 순회하면서 자신보다 작은 이전 원소들과의 관계를 통해 최대 길이를 갱신합니다.

예를 들어, 수열이 1, 2, 10, 3, 8일 때, 8의 위치에서 앞의 값들과 비교하여 감소하는 수열의 최대 길이를 계산해야 합니다. 이 경우 8 앞에 있는 원소 중 감소 조건을 만족하는 원소는 10과 3입니다. 따라서 dp 배열에서 8의 값은 앞의 원소들 중 최대 길이를 가지는 값에 +1을 더해 계산됩니다.

즉, dp[4]는 dp[2]와 dp[3] 중 더 큰 값에 +1을 해서 최장 길이를 업데이트합니다.

단계별 dp 업데이트 과정

• 초기 수열: 1, 2, 10, 3, 8
• 초기 dp 배열: [1, 1, 1, 1, 1]

1. 첫 번째 원소 1은 시작점이므로 dp[0] = 1
2. 두 번째 원소 2:
   • 2보다 앞선 원소는 1이고, 1 < 2이므로 감소 조건을 만족하지 않음.
   • dp[1]은 그대로 1
3. 세 번째 원소 10:
   • 10보다 앞선 원소 1, 2 모두 10보다 작음.
   • 따라서 감소 조건을 만족하지 않음. dp[2]도 1
4. 네 번째 원소 3:
   • 앞선 원소 1, 2, 10 중에서 10 > 3이므로 감소 조건 만족.
   • dp[3] = dp[2] + 1 = 2
5. 다섯 번째 원소 8:
   • 앞선 원소 1, 2, 10, 3 중에서 10 > 8, 3 < 8이므로 감소 조건을 만족하는 원소는 10과 3.
   • dp[4] = max(dp[2], dp[3]) + 1 = 3

최종 dp 배열: [1, 1, 1, 2, 3]

잘못된 접근 방식과 그 문제점

처음 시도했던 잘못된 접근 방식은 각 원소보다 큰 값을 찾는 함수를 사용해 값을 계산하려는 것이었습니다. 예를 들어 1, 2, 10, 3, 8과 같은 예제에서 8의 위치에서 정확한 감소 수열의 최대 길이를 구하지 못하는 문제가 있었습니다.

 

이 접근 방식의 문제는 바로 직전 요소의 최대 길이만 확인하고 +1을 더하는 방식이었습니다. 예를 들어, 1, 2, 10, 3, 8의 경우 정답은 3이지만, 이 방법으로는 값 2만을 구하게 됩니다. 따라서 단순히 바로 직전 값만을 확인하는 것이 아니라, 수열의 모든 이전 원소들을 확인하여 각 원소가 만들 수 있는 감소 수열의 최대 길이를 비교하고 갱신해야 합니다.

 

각 이전 원소가 현재 원소보다 큰지 확인하고, 그중 가장 큰 길이에 +1을 더해야 정확한 결과를 얻을 수 있습니다. 예를 들어, 1, 2, 10, 3에서 마지막 3의 위치에서 가능한 모든 감소 수열을 확인하여 최종적으로 최대 길이를 갱신해야만 올바른 결과를 얻을 수 있습니다.

// vec에서 idx보다 왼쪽에 있는 값들 중 vec[idx]보다 큰 값을 찾아 인덱스를 반환
int findItemBiggerThen(int idx, const vector<int>& vec) {
    int item = vec[idx];
    for (int j = idx - 1; j >= 0; j--) {
        if (vec[j] > item) {
            return j;
        }
    }
    return -1;
}

// Longest Decreasing Subsequence (LDS)를 계산하는 함수
int calculateLDS(const vector<int>& sequence) {
    int n = sequence.size();
    vector<int> dp(n, 1); // DP 배열, 초기값 1

    // DP를 사용하여 LDS 계산
    for (int i = 1; i < n; i++) {
        // vec[i]보다 큰 값의 인덱스를 찾기
        int idx = findItemBiggerThen(i, sequence);

        if (idx != -1) {
            dp[i] = dp[idx] + 1;
        }
    }

    // dp 배열의 최댓값이 LDS의 길이
    return *max_element(dp.begin(), dp.end());
}

 

처음에 문제를 풀면서, 단순히 자기보다 작은 앞선 원소들의 수 + 1의 최댓값을 구하도록 접근했습니다. 하지만 이 방식은 테스트 케이스에서 실패를 경험하게 했습니다. 문제 해결 과정에서 다른 사람의 풀이와 해설을 참고하면서, 기존 접근 방법의 오류를 이해하고 코드를 수정할 수 있었습니다.

문제의 해결

아래는 제가 수정한 코드입니다. 이 코드에서는 각 원소를 순회하면서 자신보다 작은 이전 원소들과의 관계를 통해 dp 값을 업데이트합니다.

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

using namespace std;

// Longest Decreasing Subsequence (LDS)를 계산하는 함수
int calculateLDS(const vector<int>& sequence) {
    int n = sequence.size();
    vector<int> dp(n, 1); // DP 배열, 초기값 1

    // DP를 사용하여 LDS 계산
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sequence[j] > sequence[i]) { // 감소 조건
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // dp 배열의 최댓값이 LDS의 길이
    return *max_element(dp.begin(), dp.end());
}

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

    vector<int> inputSequence(numElements);
    for (int i = 0; i < numElements; i++) {
        cin >> inputSequence[i];
    }

    // Longest Decreasing Subsequence 계산
    int ldsLength = calculateLDS(inputSequence);

    // 결과 출력
    cout << ldsLength << endl;

    return 0;
}

lower_bound 함수 사용

추가로, lower_bound 함수를 사용하여 코드를 더 간결하게 작성할 수 있었습니다. lower_bound는 특정 값을 찾거나 범위 내에서 조건을 만족하는 첫 위치를 찾는 데 유용합니다. 이를 사용하면 더 효율적인 풀이가 가능합니다.

아래는 lower_bound를 사용한 풀이입니다. 이 코드는 감소하는 수열을 만들기 위해 현재 값보다 큰 값을 찾고, 그 위치를 사용해 dp를 업데이트합니다.

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

using namespace std;

// Longest Decreasing Subsequence (LDS)를 계산하는 함수
int calculateLDS(const vector<int>& sequence) {
    vector<int> lds; // LDS를 저장할 벡터

    for (auto currentValue : sequence) {
        // 현재 값보다 큰 값이 나오는 첫 번째 위치를 찾는다.
        auto it = lower_bound(lds.begin(), lds.end(), currentValue, greater<int>());

        if (it == lds.end()) {
            lds.push_back(currentValue);
        } else {
            *it = currentValue;
        }
    }

    return lds.size();
}

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

    vector<int> inputSequence(numElements);
    for (int i = 0; i < numElements; i++) {
        cin >> inputSequence[i];
    }

    // Longest Decreasing Subsequence 계산
    int ldsLength = calculateLDS(inputSequence);

    // 결과 출력
    cout << ldsLength << endl;

    return 0;
}

오늘의 회고

오늘 문제를 풀면서 처음에는 해결 방법이 쉽게 떠오르지 않아 어려웠습니다. 특히 감소하는 부분 수열을 구하는 방법에서 dp 배열의 의미와 역할을 제대로 이해하지 못해 많은 시행착오를 겪었습니다. 하지만 질문 게시판을 참고하고 다른 사람의 설명을 통해 문제 해결에 한 걸음 더 나아갈 수 있었습니다. 가장 큰 수확은 lower_bound 함수의 사용 방법을 새로 배운 것입니다.

lower_bound 함수 기초 사용법

lower_bound는 정렬된 범위에서 특정 값을 찾거나 그 값 이상이 처음 나타나는 위치를 반환하는 함수입니다. 일반적인 사용법은 다음과 같습니다:

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

using namespace std;

int main() {
    vector<int> vec = {1, 3, 5, 7, 9};
    int target = 5;

    // lower_bound를 사용하여 vec에서 target 이상의 값이 처음 나오는 위치를 찾음
    auto it = lower_bound(vec.begin(), vec.end(), target);

    if (it != vec.end()) {
        cout << "Found value: " << *it << " at index: " << distance(vec.begin(), it) << endl;
    } else {
        cout << "Value not found" << endl;
    }

    return 0;
}

 

이 코드는 정렬된 벡터 vec에서 target 값 이상이 처음 나오는 위치를 찾아 출력합니다. lower_bound는 일반적으로 이진 탐색을 이용하기 때문에 O(log n)의 시간 복잡도를 가지며 매우 효율적입니다.

이번 문제를 통해 dp의 의미와 lower_bound의 활용 방법을 더 명확히 알 수 있었습니다. 앞으로 더 많은 알고리즘 문제를 풀면서 배운 개념을 더 깊이 이해하고, 효율적인 풀이를 작성할 수 있도록 노력하겠습니다.