코드노예

이번에는 LIS 에 대해서 알아보겠습니다.

LIS는 원소가 증가하는 순서대로 배치 했을 때, 가장 긴 배열의 길이를 구하는 문제입니다.

예를 들어 [1, 5, 2, 3, 10] 이라는 배열이 있다면,

증가 순서대로 배치 했을 때, 가장 길게 나오는 경우는 [1, 2, 3, 10]이 되므로, 이 경우의 답은 4가 됩니다.

기본적인 접근법은, 자신보다 작은 수의 원소를 카운트할 수 있는 버퍼(dp)를 생성하고, 중첩루프를 돌며 자신보다 작은 수의 원소에 대해서 현재 카운트와 작은 수의 원소의 카운트 + 1을 비교해서 큰 값을 취하고, 최종결과에서 최대값을 리턴하면 됩니다.

위의 예시에 대해서 과정을 살펴보면,

먼저 자기 자신은 모두 1로 세팅합니다.

[1, 1, 1, 1, 1]

1에 대해서 나머지 모든 원소들이 1보다 크기 때문에 dp[i] (= 1) 과 dp[0] + 1 (= 2)를  비교해서 더 큰 값인 2를 취합니다.

[1, 2, 2, 2, 2]

5에 대해서 같은 방법을 적용하면, 5보다 큰 10에 대해서만 dp[1] + 1 (= 3) 으로 바뀝니다.

[1, 2, 2, 2, 3]

2에 대해서 같은 방법을 적용하면, 10의 경우 이미 3이었는데, dp[2] + 1 (= 3) 이기 때문에 변화가 없습니다.

[1, 2, 2, 3, 3]

3에 대해서 같은 방법을 적용하면,

[1, 2, 2, 3, 4]

dp 의 최대 값은 4이기 때문에, 가장 긴 증가 순서의 길이는 4가 됨을 알 수 있습니다.

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [1] * arrLen
    ret = 0
    for i in range(arrLen):
        for j in range(i+1, arrLen):
            if (nums[i] < nums[j]):     
                dp[j] = max(dp[j], dp[i] + 1)
                if (dp[j] > ret):
                    ret = dp[j]
    return ret

이 경우 시간 복잡도는 O(n^2) 이 됩니다.

조금 더 효율적인 방법으로는 배열을 순회하며, 값이 증가하는 경우에는 그대로 값을 추가해주고, 값이 감소하면 그 값을 기존에 찾아둔 배열에서 해당 값보다 큰 수들 중에 가장 작은 값의 위치에 대입해주면서 추가된 개수를 리턴하면 됩니다.

위의 예시에 대해서 과정을 살펴보면,

배열의 첫번째 원소를 추가합니다.

[1]

다음 원소를 체크해 보면, 이전에 추가한 원소(1) 보다 크기 때문에 증가 순서에 추가 합니다.

[1, 5]

다음 원소는 2 인데, 2는 이전에 추가한 원소(5) 보다 작기 때문에, 리스트에 추가하지 않고, 기존 리스트에서 2보다 큰 수들 중에서 가장 작은 값(5)를 2로 대체합니다.

[1,2]

다음 부터 나오는 숫자들 (3, 10) 은 순서대로 증가하기 때문에 하나씩 추가해 주면 됩니다.

[1,2,3]
[1,2,3,10]

최종적으로 총 4번 추가했기 때문에, 길이는 4가 됩니다.

이 알고리즘은 길이를 구하기 위해서 최적화 된 알고리즘 이기 때문에, 배열에 들어가 있는 값은 실제 순서와는 다를 수 있습니다.

예를 들어, [1, 5, 6, 7, 8, 2, 3, 4] 라는 배열로 적용해 보면, 최종 수행 결과는 [1, 2, 3, 4, 8]가 되는데, 실제로 가장 긴 배열은 [1, 5, 6, 7, 8] 이기 때문입니다. 

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [nums[0]]
    dpLen = 1
    for i in range(1, arrLen):
        if (dp[-1] == nums[i]):
            pass
        elif (dp[-1] == nums[i]):
            dp.append(nums[i])
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (dp[mid] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            dp[l] = nums[i]
    return dpLen

이 알고리즘의 시간 복잡도는 O(n log n) 이 됩니다.

마지막으로 LIS의 길이가 아닌, 해당 원소들을 찾는 방법에 대해서 살펴보면, 기존 코드에서 dp에 값 대신 해당 원소의 인덱스를 저장하고, 값이 추가될 때, 해당 원소의 바로 앞이 어떤 값인지를 저장하는 버퍼(prevIdx)를 추가해서 처리하면 됩니다.

def lengthOfLISEx(nums):
    arrLen = len(nums)
    prevIdx = [-1] * arrLen
    dp = [0]
    dpLen = 1
    for i in range(1, arrLen):
        if (nums[dp[-1]] == nums[i]):
            pass
        elif (dp[-1] < nums[i]):
            prevIdx[i] = dp[dpLen - 1]
            dp.append(i)
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (nums[dp[mid]] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            prevIdx[i] = dp[l - 1]
            dp[l] = i

    currIdx = dp[-1]
    ans = [nums[currIdx]]
    while prevIdx[currIdx] != -1:
        ans.append(nums[prevIdx[currIdx]])
        currIdx = prevIdx[currIdx]
    return ans[::-1]