티스토리 뷰

이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다.


LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다.


쉬운 이해를 위해서 예를 들어보겠습니다.


다음과 같은 수열이 존재한다고 해봅시다.


여기서 LIS를 찾는다면 


다음과 같이 빨간 부분으로 색칠된 부분이 LIS가 됩니다.


눈치 빠르신 분들은 벌써 알아채셨을겁니다. 


LIS는 앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대 길이가 되도록 숫자를 선택하는 경우입니다.


보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이됩니다.


즉, 그 수열에서 존재하는 모든 부분 증가 수열 중 길이가 최대인 수열의 길이가 답이 되는거죠.


이것을 구현하기 위해서 가장 쉽게 생각 할 수 있는건 O(N^2)의 시간복잡도를 가지는 DP로 구현하는 것입니다.


DP 테이블 dp[x]의 정의를 하자면 


dp[x] : x번째 수를 마지막 원소로 가지는 lis의 길이 


가 됩니다.


이런 방식으로 구현할 경우 


dp[x]가 이미 채워져 있다면 x보다 큰수의 y의 수열값 arr[y]도 arr[x]보다 크다면 dp[y]는 dp[x]+1이 될 수 있음을 고려해 볼 수 있습니다.


이러한 아이디어를 기반으로 2중 포문을 채워나가면서 O(N^2)의 시간 복잡도에 LIS를 해결 할 수 있습니다.


2중 포문 부분의 소스를 공개하자면 다음과 같이 되겠군요.

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < n; i++) {
    if (dp[i] == 0)dp[i] = 1;
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j]) {
            if (dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }
}



하지만 N이 10만이 넘는다면 ..?


우리는 O(N^2)의 방법으로 LIS 문제를 해결할 수 없게 됩니다.


그렇기 때문에 우리는 O(NlogN)의 방법으로 LIS를 해결하는 방법을 배워야 합니다.


O(NlogN)으로 LIS를 구현하는 방법은 대표적으로 두가지가 있는데


하나는 세그먼트 트리를 이용하여 arr[x]의 위치에 x번째 수를 마지막 원소로 가지는 lis의 길이를 업데이트하여 


매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값+1을 업데이트하는 방식으로 처리를 한다면


N번을 확인하면서 최댓값을 찾는데 O(logN)시간이 걸리니 총 O(NlogN)의 시간이 걸릴 것입니다.


하지만 이 방법을 소개하려던건 아니고 좀 더 간단한 방법을 소개해 드리려고 합니다.


바로 이분 탐색을 이용하는 방법입니다.


이번에도 O(N)의 방법으로 수열을 처음부터 확인할건데 이번에는 이분탐색을 이용하여 LIS를 유지하기 위한 최적의 위치에다가 수를 삽입하는 방식입니다.


자리를 찾는데 lower_bound를 이용하기 때문에 O(logN)의 시간복잡도를 가지게 되어 총 O(NlogN)의 시간복잡도를 가지게 됩니다.


최적의 위치를 찾는방법은 생각보다 간단한데요.


벡터를 하나 생성 한 뒤 -INF(나올 수 없는 가장 작은 값)를 삽입해 줍니다.


이후 매번 수열을 볼때마다 벡터의 맨 뒤 원소와 현재 보고있는 수열의 원소를 비교하여 수열의 원소가 더 클 시 벡터에 push_back해준 뒤 LIS의 크기(답)을 1증가 시켜줍니다.


만약 수열의 원소가 벡터의 맨 뒤 원소보다 작을 경우 lower_bound를 이용하여 최적의 자리를 찾은 뒤 그 자리의 값을 해당 수열의 원소로 교체해 버립니다.


정당성에 대한 이해를 돕기 위하여 한가지 예를 들어보겠습니다.


만약 벡터에 현재 10 40 70 이라는 값이 들어있다고 할 때 50이 들어갈 위치를 찾기 위하여 lower_bound로 50을 찾는다면 이터레이터는 70의 위치를 가리키게 되어 70을 50으로 갱신할 것 입니다.


그러면 벡터에는 10 40 50 이라는 값이 들어가게 될 것입니다.


자, 이 다음 55라는 값이 들어온다면 우리는 70이라는 값이 50으로 갱신되지 않았다면 55라는 값을 벡터에 추가하지 못하여 손해를 봤을 것입니다.


우리가 lower_bound를 이용하여 x라는 값을 찾으면 x보다 크거나 같은값중 최솟값의 위치를 return하기 때문에


현재 구성된 lis구조를 유지하면서 앞으로 보게 될 수열들을 최대한 벡터가 많이 수용할 수 있도록 적절한 위치에 값이 갱신이 됩니다.


자, 이제 그림과 함께 보겠습니다.

빨간부분은 지금 보는 위치이고 파란칸을 벡터라고 하겠습니다. 10의 경우 첫번째 수이기 때문에 우선 벡터에 넣어줍니다.


3번째 인덱스까지는 벡터의 끝값이 항상 수열의 값보다 작기 때문에 전부 삽입해 줍니다. 


이후 4번째 인덱스의 값이 벡터의 끝값보다 작기 때문에 lower_bound로 탐색한 뒤 40을 25로 갱신해줍니다.

5번째 인덱스의 값또한 벡터의 끝값보다 작기 때문에 lower_bound로 탐색한 뒤 20을 20으로 갱신해줍니다.


6번째 인덱스의 값은 벡터의 끝값보다 크기 때문에 50을 추가해 줍니다.


7번째 인덱스의 값은 벡터의 끝값보다 작기 때문에 lower_bound로 탐색 한 뒤 50을 30으로 갱신해줍니다.


자 이때 만약에 뒤에 40이라는 값이 온다면 벡터의 끝값을 30으로 갱신하지 않았다면 40을 추가하지 못할것입니다.


하지만 매 순간 증가수열을 유지할 수 있는 최적의 장소를 찾아서 갱신하기 때문에 다음에 40이 올 경우 추가할 수 있게됩니다.


자 다시 돌아와서 70과 85를 벡터에 추가해준다면 우리는 이 수열에서의 LIS의 길이는 6이라는 사실을 알 수 있게됩니다.


쉬운 이해를 이해 소스코드를 첨부하겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
vt.push_back(-INF);
for (int i = 0; i < n; i++) {
    scanf("%d"&x);
    if (vt.back() < x) {
        vt.push_back(x);
           ans++;
    }
    else {
        auto it = lower_bound(vt.begin(), vt.end(), x);
        *it = x;
    }
}




한가지 주의 할 점은 벡터에 들어있는 값이 LIS를 이루는 요소와 무관하다는 것입니다.


수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색 된 최적의 위치가 앞에 있을 수도 있기 때문입니다. 


자 이제 O(NlogN)의 시간복잡도로 LIS 문제를 해결하실 수 있겠나요?


이제 LIS를 이용하는 여러가지 문제들을 풀어봅시다.


TAG
댓글
  • 프로필사진 hoon222y O(NlogN)의 시간복잡도로 LIS 설명을 아주 꿀같이 해주셨네염 감사합니당 ㅎㅎ 2017.03.06 14:52 신고
  • 프로필사진 JASON 자손9319 ㅎㅎ 2017.03.06 14:55 신고
  • 프로필사진 JASON 자손9319 스벅이냐 2017.03.06 14:56 신고
  • 프로필사진 hoon222y 예얍 ㅋㅋ
    2017.03.06 15:14 신고
  • 프로필사진 감사 DP 코드에서
    if (dp[i] == 0)dp[i] = 1; 로 할 필요없이 dp[i] = 1 해도 되는 것 같은데... 맞나요?
    2017.06.04 00:18
  • 프로필사진 JASON 자손9319 네 그렇게하셔도 될 것 같습니다 ㅎㅎ 2017.06.04 23:33 신고
  • 프로필사진 NEwBie 그럼
    저벡터의 가장앞에는
    (엄청 작은 값의 이름을 MIN_INF라고 한다면)
    MIN_INF가 들어있는거맞나요
    2018.03.07 00:49
  • 프로필사진 JASON 자손9319 네 맞습니다~ 2018.03.07 00:57 신고
  • 프로필사진 NEwBie vt벡터요 2018.03.07 00:49
  • 프로필사진 NEwBie 질문하나만 하겠습니다
    백준 2491번 <수열> 문제 를 이코드를 활용해서 풀수는없나요? (lower_bound의 인덱스처리과정에서 답이틀려지는거같은데..)
    저문제가 최대증가수열(같은수포함가능),최대감소수열(같은수포함가능)의 맥시멈을 구하는 문제라
    저코드에서 vt.back()하고 비교할때 등호만 넣어주면 될줄알았는데 안되네요
    혹시 뭐가 문제인지 가르쳐주실수있나요
    2018.03.07 22:20
  • 프로필사진 NEwBie 죄송합니다
    눈을 빼서 씻고 오겠습니다..
    좋은하루되세요
    2018.03.07 22:22
  • 프로필사진 JASON 자손9319 답글 다려고 했는뎁 ..ㅋㅋ 좋은 하루 되세욥!! 2018.03.07 22:23 신고
  • 프로필사진 NEwBie vector 와 lower_Bound를 쓰는 nlgn풀이로
    같거나 증가하는 수열의 경우는 구할수 없나요
    예를 들어
    1 2 1 2 2 3 1 3 4 4 5

    1 2 2 2 3 3 4 4 5 답: 9.. 이런식의 문제요
    2018.04.09 11:36
  • 프로필사진 이정우 정당성에 대한 설명이 부족한 것 같습니다.
    손해를 봤다는 표현을 쓰셨는데, 해당 case의 손해를 보지 않았다고 알고리즘이 정당하다고 볼 순 없습니다.
    해당 알고리즘이 정당한 이유는 vector 인덱스 i번 째 원소가 의미하는 바를 생각해보시면 됩니다.
    해당 vector에서 i번째 원소가 의미하는 바는
    현재까지의 만들 수 있는 i개의 원소를 가진 IS (증가 수열)들 중 i 번째 원소가 가장 작은 수열의 i번째 원소로 보시면 됩니다.
    만일 현재 value가 x 번째 인덱스로 들어가게 된다면, x-1 인덱스의 원소는 x-1개의 IS중 가장 작은 x-1번째 원소기 때문에 value 보다
    순서상 먼저 나타났고 value보다 값이 작기 때문에 x번째 인덱스로 value가 들어가는 것이 타당하며
    lowerbound의 값(value이상)을 value로 대체했기 때문에 value= x개의 원소를 가진 IS중 x번째 원소가 가장 작은 IS의 x번째 원소
    를 만족합니다.
    따라서 벡터의 마지막 원소 는 현재까지 의 LIS 중 vector의 size개의 원소를 가진 LIS 중 가장 마지막 값이 작은 값을 만족하므로
    보다 큰 값이 나타났을 때, push 되는 것이 타당합니다.
    원소가 새롭게 중간의 위치로 들어가거나, push 될 때, 바로 이전 index의 값은 자신이 만들 수열의 바로 이전 값임은 타당하므로 이 값을 저장하면 백트래킹을 통해 LIS의 원소들을 구할 수 있습니다.
    2018.07.12 16:12
  • 프로필사진 codenstory 늦었지만 궁금한 점이 생겼습니다.
    각각의 case에 대한 손해를 보지 않았다고 해서 무조건 알고리즘이 정당하다고 할 수 없는 이유가 궁금합니다.
    2019.07.20 08:56
  • 프로필사진 23DOTORY 퍼가요~♡ 2018.07.17 16:36 신고
  • 프로필사진 123 힝 어려워용 ㅠㅠ감사합니다 잘보고 갑니다 2018.11.10 23:26
  • 프로필사진 123 궁금한게 있어요 ㅠㅠㅠ이러한 방법으로 그럼 LIS의 배열 요소를 다시 복구는 하지 못하는 가요????즉 1624537 을 입력했을때 이 방법을 통해 구현한다면 12357 이 나오는데 사실은 12457 이 나와야 정상이죠.이걸 어떻게 해결할 방법이 존재할까요? 2018.11.14 17:34
  • 프로필사진 Question 혹시 수열 배열이
    4 5 6 1 2 3 4 경우에도 적용되는거 맞나요..
    2019.07.17 15:10
  • 프로필사진 lower bound 사용... 10 20 30 1 2 3 4 이러면 1234가 더 긴 수열인데 10 20 30 이 되지 않나요 ... 2019.11.28 21:37
  • 프로필사진 본인 제가 잘못이해했었네요 좋은글 감사합니다 2019.11.28 21:52
  • 프로필사진 clucle 좋은 글 감사합니당 2019.12.13 18:41 신고
  • 프로필사진 감사합니다 벡터에 들어 있는 값은 실제 LIS와 같지 않다는 말 덕분에 이해가 깔끔하게 됐습니다! 감사해요~ 2020.04.08 15:48
  • 프로필사진 민트초코 감사합니다 많이 알았습니다. 2020.08.14 10:18
  • 프로필사진 와 미치겠다 이걸 진짜 너무 많이 찾고 있었어요! 감사합니다 2020.08.17 17:11
  • 프로필사진 ㅇㅇ 와 진짜 쉽게 설명해주셨네요 감사합니다 2020.08.27 22:40
댓글쓰기 폼