c++ LIS (최장 증가 부분 수열 찾기)

[참조]

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 (rebro.kr)

---

LIS

순서를 바꾸지 않고 랜덤 숫자 수열이 있을 때, 증가하는 불연속적인 부분 요소 집합을 찾는 방법.

길이 또는 집합 배열을 구해야 한다.

 

예) { 3, 5, 2, 6, 1 }

 

답 : 3, {3,5,6}

 

방법

• 2중 for문, DP 방식으로 풀기 (O(N^2))
• 1개 for문, lower_bound 이용하여 풀기 (O(NlogN))

*참고로 lower bound를 이용한 방법은 원리를 정확히 모르겠음......

 

1개 for문, lower_bound 이용하여 풀기

• lower_bound 란, 목표 값보다 [같거나 큰 요소]의 iter를 찾는 함수. (없으면 .end() )

 { 3, 5, 2, 6, 1 }

 

새 배열 한개 추가(lower_bound 진행 용) 후,

1개 for문으로 탐색하며 현재 값을 새 배열에 대한 lower_bound가 반환 한 iter 에 갱신.

새 배열의 크기가 곧 최장 증가 부분 수열 크기가 됨.

 

1. {3}

2. {3,5}

3. {2,5}

4. {2,5,6}

5. {1,5,6} 3개

 

진짜 답은 {3,5,6} 이지만 크기 만 구하는 문제라면 상관 없음.

 

진짜 부분수열을 구하기 위해선

처음 for문 돌릴 때, iter 갱신 시 교체되는 {인덱스와 값}을 배열에 저장 하고 모든 로직이 끝나면,

해당 배열을 뒤에서 부터 차례대로 탐색하면서 정답 크기가 k 라면 인덱스가 k인 값을  뽑아 내고, k-- 하며 k가 1일 때 까지 찾아 뽑아낸다.

 

- 처음 3, lower bound 할때 첫 요소라서 {인덱스,값} 은 {1,3}

- 다음 5, lower bound 할때 맨 뒤에 들어가므로 {2,5}

- 다음 2, lower bound 할때 첫 요소와 교체 되므로 {1,2}

- 다음 6, 은 {3,6}

- 다음 1, 은 {1,1}

 

따라서 {1,3} {2,5} {1,2} {3,6} {1,1} 이 저장되고  이 배열을 뒤에서부터 탐색하면서 인덱스가 차례대로 3,2,1 인 값을 뽑고 reverse 하면된다.

 

인덱스가 처음엔 3, 그 다음 2, 그 다음 1 인 값을 찾으면 {6,5,3} 이며 반전 하면 {3,5,6} 이다.

 

 

코드 작성

    vector<int> sequen{ 8,2,9,1,4,6,7,10 }; //전깃줄 예제
    //vector<int> sequen{ 3, 5, 2, 6, 1 };
    vector<int> answer_s;               //정답 수열 경로 저장용

    vector<int> lower;                  //lower_bound 저장용
    vector<pair<int, int>> LIS_paths;   //실제 요소 찾는 용 (뒤에서 탐색 할 용도)

    //lower_bound로 넣을 위치를 찾고 바꾼 후, 인덱스와 값 저장
    for (int i = 0; i < sequen.size(); ++i)
    {
        auto iter = lower_bound(lower.begin(), lower.end(), sequen[i]);
        if (iter == lower.end())
        {
            lower.push_back(sequen[i]);
            LIS_paths.push_back({ lower.size(),sequen[i] });
        }
        else
        {
            int idx = distance(lower.begin(), iter);
            *iter = sequen[i];
            LIS_paths.push_back({ idx+1, sequen[i] });
        }
    }

    //진짜 수열 찾기
    int checkidx = lower.size();
    for (int i = LIS_paths.size()-1; i >= 0; --i)
    {
        if (LIS_paths[i].first == checkidx)
        {
            --checkidx;
            answer_s.push_back(LIS_paths[i].second);
        }
        if (checkidx == 0)
            break;
    }
    reverse(answer_s.begin(), answer_s.end());

    cout << "최대 부분 수열 길이 : " << lower.size() << endl;
    cout << "수열 : ";
    for (int i = 0; i < answer_s.size(); ++i)
        cout << answer_s[i] << ", ";
    cout << endl;