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