최장 증가 부분 수열 - Longest Increasing Subsequence 알고리즘

최장 증가 부분 수열

 이 알고리즘을 접하게 된건 백준의 11053번으로 백준 내에서도 시리즈로 있을 정도로 유명한 알고리즘입니다. 영어로 LIS라고 줄여 말하기도 하는 이 알고리즘은 주어진 수열에서 수가 계속 증가하는 부분수열의 최대를 구하는 알고리즘으로 주의해야 할 점은 부분수열이니 순서를 지켜야 한다는 것입니다. 단순 정렬이라면 이렇게 따로 알고리즘이 나올 이유는 없겠죠.

 

다이나믹 프로그래밍으로 풀이하는 LIS  ( 시간복잡도 O(N^2) )

    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    for(int i = 0; i < n; i++){
        answer[i] = 1;
        for(int j = 0; j < i; j++){
            if(arr[i] > arr[j]){
                answer[i] = max(answer[i], answer[j] + 1);
            }
        }
        result = max(result, answer[i]);
    }

- 추후 설명 추가 예정

 

이분탐색을 이용한 LIS ( 시간복잡도 O(nlogn) )

 위 알고리즘의 경우 n^2 시간복잡도를 가지고 있기 때문에 인풋이 많아지면 시간초과가 날 가능성이 있습니다. 그래서 고안된게 이분탐색을 이용한 알고리즘입니다.

 

1) 수열 { 10 20 10 30 20 50 } 이 주어집니다. 그리고 벡터를 하나 선언해 둡니다.

 

2) 첫 입력값 10이 들어오고 이를 벡터에 넣어줍니다.

10 |

3) 이후 입력값 20이 들어오는데 이는 벡터의 맨 마지막 원소인 10보다 큰 값이므로 뒤에 넣었을 때 최장 증가 부분 수열을 만들 수 있으니 뒤에 넣어줍니다.

10 | 20 |

4) 이후 입력값 10은 맨 뒤 원소인 20보다 작습니다. 따라서 뒤에 넣어 수열 길이를 증가시킬 순 없습니다. 대신 이후 들어오는 수열위해 기존 값들과 비교, 해당되는 위치에 넣어줍니다.

10 | 20 |

5) 다음 값인 30은 맨 뒤 원소인 20보다 크므로 배열에 새로 넣어줍니다.

10 | 20 | 30 |

6) 그 다음 20의 경우 4번과 같은 과정을 거치며 기존 20을 대체하게 됩니다.

10 | 20 | 30 |

7) 그 다음 50은 맨 뒤 원소인 30보다 크므로 배열에 새로 넣어줍니다.

10 | 20 | 30 | 50 |

 

이렇게 되면 마지막에 나오는 벡터의 길이가 정답이 되게 됩니다. 각 입력값에 대한 연산들을 정리해보면

 

if ( 백터의 마지막 원소보다 큰 값이 들어옴 )
    벡터의 맨 뒤에 새로 넣어줌
else
    이분탐색을 통해 벡터에 들어갈 자리를 찾아 대체해줌

 

여기서 else에서 하는 일을 예시로 설명하자면 만일 10 30 60 이란 배열이 만들어져 있었을 때 35란 값이 들어온다면 이분탐색을 통해 35보다 큰 수중 가장 작은 수를 발견(=60) 이를 대체해 10 30 35란 배열을 만들어 주는 과정입니다. 이렇게 함으로서 이후 들어올 값들이 최장 부분 수열을 만들기 쉽게 해주는 것이죠.

 

(예: 만약 10 30 60에서 35, 40이 남았다면 60이 남는것 보다 35로 대체 후 40을 넣어주는게 정답이기 때문)

 

이제 이를 아래 코드로 나타내면 다음과 같습니다.

    vector<int> num;

    for(int i = 0; i < n; i++){
        scanf("%d", &input);

        if(num.empty() || num.back() < input)
            num.push_back(input);
        else {
            auto temp = lower_bound(num.begin(), num.end(), input);
            *temp = input;
        }
    }

C++에 있는 lower_bound를 이용해서 풀이한 모습으로 만약 lower_bound랑 비슷한 함수가 없다면 이분탐색을 직접 구현해야 한다는 단점이 있습니다.

 

---

 

추천 문제

11053번: 가장 긴 증가하는 부분 수열

- 위의 O(n^2) 알고리즘을 이용해도 될 정도로 테스트케이스가 작은 문제입니다.

12015번: 가장 긴 증가하는 부분 수열 2

- 테스트케이스가 많아 O(nlogn)알고리즘을 사용해서 풀이이해야 합니다.

12738번: 가장 긴 증가하는 부분 수열 3

- 위 문제에서 수열에 주어지는 값 범위가 다른 문제로 그 외 조건들이 같아 같은 코드로 통과가 가능합니다.