[알고리즘] 동적계획법 - LIS (Longest Increasing Sequence)

 

 

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

 

 

LIS (Longest Increasing Sequence)

 

Sequence : 1  9  2  5  7

 

부분 수열 : 일부 숫자를 지우고 남은 수열

• ex. 1  2  5
• ex. 1  9  5  7

순 증가 부분 수열

• ex. 1  2  5

LIS : 제일 긴 '순 증가 부분 수열'의 길이

• ex. 1  2  5  7 = 길이 4

---

 

 

LIS 연습 문제

 

Q) 숫자 1, 9, 2, 5, 7 를 순서대로 가지는 시퀀스가 주어진다. 이 때 제일 긴 '순 증가 부분 수열'의 길이를 구하여라. 최대 길이는 100을 넘지 않는다.

 

---

 

LIS 문제 풀이

 

#include <iostream>
#include <vector>
using namespace std;
 
int cache[100]; // 캐시 max값 설정
vector<int> seq;
 
int LIS(int pos)
{
    // 기저 사항
    if (pos == seq.size() - 1)
        return 1;
    // 캐시 확인
    int& ret = cache[pos];
    if (ret != -1)
        return ret;
 
    // 구하기
 
    // Seq : 1 9 2 5 7
    // 1 9 = 2         LIS(0) -> 1 + LIS(1) 
    // 1 2 5 7 = 4     LIS(0) -> 1 + LIS(2) -> 1 + LIS(3) -> 1 + LIS(4)
    // 1 5 7 = 3       LIS(0) -> 1 + LIS(3) -> 1 + LIS(4)
    // 1 7 = 2         LIS(0) -> 1 + LIS(4)
 
    // 최소 seq[pos]는 있으니 1부터 시작
    ret = 1;
 
    // 구하기
    for (int next = pos + 1; next < seq.size(); next++)
        if (seq[pos] < seq[next])
            ret = max(ret, 1 + LIS(next));
 
    return ret;
}
 
int main()
{
    ::memset(cache, -1, sizeof(cache));
    seq = vector<int>{ 1, 9 ,2, 5, 7 };
 
    //int ret = LIS(0); //seq의 첫 숫자가 최솟값이면 맞다. 하지만 시작 숫자가 최솟값이 아니면 안 된다.
 
    // 루프를 돌아 시작하는 위치를 다르게 계산해본다. 
    // 1 시작인 경우, 9 시작인 경우, 2 시작인 경우, 5 시작인 경우, 7 시작인 경우
    // 계산한 값 중에서 '순 증가 부분 수열'이 가장 긴 값을 ret한다.
    int ret = 0;
    for (int pos = 0; pos < seq.size(); pos++)
        ret = max(ret, LIS(pos));
}

 

 

---