Longest Increment Subsequence

오늘 추가로 풀어본 알고리즘 문제는 최장 증가 수열이다.

 

예젠에도 백준에서 매우 유사한 문제를 풀어봤었다. DP 문제를 빠르게 푸는 방법은 정확한 의미의 점화식을 세우는 것이다. 처음 문제를 풀 때 세웠던 점화식은 i 번째 원소를 시작점로 하면서 j 번째 원소를 끝점으로 하는 최장 증가 수열의 길이라고 정의하고 풀려고 노력해 보았다.

잘못된 점화식을 세웠을 때 가장 빠르게 알 수 있는 문제가 i - 1 또는 j -1 과 현재 dp[i][j]와의 관계를 찾는 것이 불가능하거나 가능하더라도 매우 복잡해진다.

 

따라서 구글 검색을 통해 내가 생각한 점화식이 틀린지 확인해 보았는데, 역시나 틀린 점화식이었다. 알맞은 점화식은 dp[k], k 번째 원소를 끝으로 하는 최장 증가 수열의 길이이다. 배열 dp는 1로 초기화 되었다고 생각하자.

arr[i] > arr[j]이면 dp[i] = max(dp[j] + 1, dp[i]) (단 j  < i 를 만족할 때 ) 이 DP 방법으로 풀 수 있다. 다만 이 풀이 방법의 단점은 O(n^2)만큼의 시간복잡도를 가지기 때문에 n 이 10만 이상인 경우에는 TLE(시간 초과 오류)가 발생한다는 점이다.

 

from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int])->int:
        dp = [1 for _ in range(len(nums))]

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    
        return max(dp) if len(nums) > 0 else 0

두 번째 풀이방법은 이진 탐색을 사용하는 방법이다.

최장 증가 수열의 길이를 구하는 배열 lis 와 실제 구하는 최장 수열을 구하기 위한 ans 배열을 이용합니다. lis 배열에는 nums의 첫 번째 원소를 넣은 후에 시작한다.

만약에 lis 배열의 마지막 원소보다 nums[i]가 크다면 lis 배열에 nums[i]를, ans 배열에는 (len(lis), nums[i])을 추가한다.

하지만 lis 배열의 마지막 원소보다 nums[i]가 작다면 이진 탐색을 이용해 lis 배열에 nums[i]를 탐색할 위치(insertPos)를 찾고, lis[insertPos] 를 nums[i]로 변경하고,  ans에는 (insertPos, nums[i])를 추가한다. 이렇게 모든 원소에 대해 마치고 나면 lis 배열의 길이를 통해 최장 증가 수열의 길이를 알 수 있지만, lis 배열에 있는 원소들이 실제 최장 증가 수열의 원소이지는 않다. 그래서 ans 배열의 0번째 값을 lis 배열의 길이 -1 부터 해서 0까지로 역순으로 내려오면 실제 최장 증가 수열을 알 수 있다.

from typing import List
import bisect
class Solution:
    def lengthOfLIS(self, nums: List[int])->int:
        # DP 방법을 이용한 풀이방법
        # 두 가진 단점이 존재한다고 생각됨
        # 첫 번재는 사소하지만, 최장 증가 수열이 무엇인지 이 풀이만으로는 알 수가 없음.
        # 두 번째 시간복잡도가 n^2임.
        dp = [1 for _ in range(len(nums))]
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp) if len(nums) > 0 else 0


    def lengthOfLIS2(self, nums: List[int])->int:
        # 두 번째 풀이방법은 이분 탐색(Binary Search)를 이용한 방법입니다.
        # 두 번째 풀이의 장점은 첫 번째 풀이의 단점 두 가지 모두를 없앨 수 있습니다.
        lis = [nums[0]]
        ans = [(0, nums[0])]
        for i in range(1, len(nums)):
            if lis[-1] < nums[i]:
                ans.append((len(lis), nums[i]))
                lis.append(nums[i])
            elif lis[-1] > nums[i]:
                # 이진탐색을 통해 nums[i]를 집어넣을 위치를 찾은 후에
                # lis[insertPos]를 nums[i]로 치환한다.
                insertPos = bisect.bisect_left(lis, nums[i])
                lis[insertPos] = nums[i]
                ans.append((insertPos, nums[i]))
        print(ans)
        print(lis)
        ans.reverse()
        t = len(lis) - 1
        s = []
        for i in range(len(ans)):
            if ans[i][0] == t:
                s.append(ans[i][1])
                t -= 1
        print(s.reverse())
        return len(nums)


if __name__ == '__main__':
    s = Solution()
    # nums = [10,20,40,25,15,16,17,18,20]
    nums = [10,20,40,25,15,50,30,70]
    s.lengthOfLIS2(nums)

 

깃헙 주소 github.com/papayetoo/StudyinPython/blob/master/AlgoReview/LIS.py