[ALGOSPOT] 알고스팟 LIS Longest Increasing Sequence(C++, Python)

www.algospot.com

[ALGOSPOT] 알고스팟 LIS Longest Increasing Sequence

(C++, Python)

(글쓴날 : 2020.05.03)

 

---

* ALGOSPOT, 알고스팟 LIS 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 LIS Longest Increasing Sequence

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/LIS

algospot.com :: LIS

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

LIS(Longest Increasing Sequence)의 길이를 구하는 문제입니다.

 

저의 경우, 이분 탐색을 적용하여 문제를 해결하였고, C++과 Python을 사용했습니다.

너무 유명하고 기본적인 문제이며, 오직 동적 계획법으로 해결 시 O(n²)의 시간 복잡도가 걸리므로 조금 더 효율이 좋은 lower_bound 기반의 이분 탐색을 적용하여 O(n log n)의 시간 복잡도에 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
 
using namespace std;
 
int sequence[501];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int C = 0;
    cin >> C;
 
    int N = 0;
    vector<int> LIS;
    int length = 0;
    vector<int>::iterator low;
 
    while (C--)
    {
        cin >> N;
        length = 0;
        memset(sequence, 0, sizeof(sequence));
        LIS.clear();
        LIS.push_back(0);
 
        for (int i = 0; i < N; i++)
            cin >> sequence[i];
 
        for (int i = 0; i < N; i++)
        {
            if (sequence[i] > LIS[length])
            {
                LIS.push_back(sequence[i]);
                length++;
                continue;
            }
 
            low = lower_bound(LIS.begin(), LIS.end(), sequence[i]);
 
            LIS[low - LIS.begin()] = sequence[i];
        }
 
        cout << length << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    N = int(input())
    sequence = list(map(int, input().split()))
 
    LIS = [0]
    length = 0
 
    for num in sequence:
        if num > LIS[-1]:
            LIS.append(num)
            length += 1
            continue
 
        left = 0
        right = length
        while(left < right):
            mid = (left + right) // 2
 
            if num < LIS[mid]:
                right = mid
            else:
                left = mid + 1
        
        LIS[right] = num
    
    print(length)

---