알고스팟 Longest Increasing Sequence (LIS)문제 파이썬으로 풀기

문제 자체는 이해하기 매우 쉽다. 수열을 받아 가장 긴 부분 수열의 길이를 구하면 되는 문제이다.

하지만 푸는 것은 매우 힘들었는데, 순증가 하는 부분 배열을 어떻게 구해야할지 방법이 마땅히 떠오르지 않았기 때문이었다.

 

혼자서 삽질을 하다가, 인터넷에서 새로운 방법을 찾아 보았다.

출처: https://moonraker.tistory.com/22

메모이제이션을 이용해 뒤에서부터 증가수열의 길이를 구해나가는 방식이다.

이를 파이썬으로 구현했다.

#lis
import sys
 
 
def lis(pos):
    if dp[pos] != -1:  # -1이 아니라면 lis길이를 구한 것이므로 그 길이를 리턴
        return dp[pos]
    ret = 1  # lis 길이
    for l in range(pos, n):
        if lists[pos] < lists[l]:  # 기준점(pos)에서보다 큰 수가 온다면
            ret = max(ret, lis(l)+1)  # 뒤에 있는 수에서 검사
    dp[pos] = ret  # dp에 저장 후 리턴
    return ret
 
 
case = int(sys.stdin.readline())
for i in range(case):
    n = int(sys.stdin.readline())
    lists = list(map(int, sys.stdin.readline().split()))
    dp = [-1 for j in range(n)]  # lis 길이를 저장
    result = 0
    for k in range(0, n):
        result = max(result, lis(k))  # lists의 0번째부터 lis길이 탐색
    print(result)

중간에 lis(l)에 +1을 하는 이유는

이렇게 뒤를 검사하더라도 자신을 포함해야 하기 떄문에 1을 더해준다.

 

느낀점:

1. 알고스팟에서 제출횟수가 많은 문제 중 하나라 쉬울 줄 알았는데 매우 어려웠다. 동적계획법 자체는 이제 슬슬 감이 잡히는데(정확힌 메모이제이션이) 재귀함수랑 같이 쓰면 아직도 어렵다..

2. 

출처: https://gon109.tistory.com/54

이렇게 이진탐색으로 하는 방식도 있는거 같은데 파이썬으로 구형해보니 잘 되지도 않았고, 어떻게 작동되는지 잘 이해도 되지 않아서 그냥 안쓰고 풀었다.