LIS(Longest Increasing Subsequence, 최장 증가 부분 수열

LIS 문제는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다.

 

예를 들어, 수열 [10, 20, 30, 5, 15, 25, 35, 40]이 주어졌을 때, 최장 증가 부분 수열은 [10, 20, 30, 35, 40]이며 길이는 5입니다.

 

상어의 크기를 수열로 보면, 연속적으로 먹히는 관계를 가진 상어들의 최대 마리 수는 그 수열에서 최장 증가 부분 수열의 길이와 같습니다.

 

다만, 주어진 문제에서는 순서가 중요하므로 단순히 LIS 알고리즘을 적용하기는 어렵습니다.

 

 

LIS 문제와 관련된 유명한 다른 문제들로는 다음과 같은 것들이 있습니다:

 

가장 긴 공통 부분 수열(Longest Common Subsequence, LCS) 문제

가장 큰 증가 부분 수열의 합(Maximum Sum Increasing Subsequence) 문제

비트마스크를 이용한 LIS 문제

변형 LIS를 이용한 최장 경로 문제(도로 건설, 전기 케이블 등)

 

이러한 문제들은 동적 계획법(Dynamic Programming)이나 분할 정복(Divide and Conquer) 기법을 사용하여 해결할 수 있습니다.

 

https://chanhuiseok.github.io/posts/algo-49/

 

예제를 파이썬으로

for i in range(n):
    for j in range(j):
        if(arr[j] < arr[k]):
            length[i] = max(length[i], length[j] + 1)

 

뒤쪽 상어가 더 작은 상어를 잡아먹는 문제

import sys

n = int(sys.stdin.readline())
shark = [int(i.rstrip()) for i in sys.stdin.readline().split()]

ans = [1] * n 

# print(shark)
for i in range(1, n):
    for j in range(i):
        if shark[i] > shark[j]:
            # print(shark[i],shark[j])
            ans[i] = max(ans[i], ans[j] + 1)
    # print(ans)

print(max(ans))

 

 

이분탐색과 함께 사용(n이 높을 떄. O^n은 사용 못함)

import bisect

n = int(input())
arr = list(map(int, input().split()))
lis = [0] * (n+1)

# LIS를 유지하기 위해 숫자가 들어갈 위치를 이분탐색으로 찾는 함수
def binarysearch(left, right, target):
    # lis 배열에 들어갈 target=arr[i]의 위치를 이분탐색으로 찾기
    while left < right:
        mid = (left + right) // 2  # 중간값 설정
        if lis[mid] < target:
            left = mid + 1
        else:
            right = mid
    return right

j = 0
lis[0] = arr[0]  # lis 배열의 맨 첫번째 값은 arr[0]으로 초기화
i = 1

# arr의 두번째부터 마지막까지 하나씩 lis와 비교하면서 넣어준다.
while i < n:
    # lis 배열의 맨 뒤의 값보다 arr[i]가 더 크면 그것을 lis 배열 맨 뒤에 넣어준다.
    if lis[j] < arr[i]:
        lis[j+1] = arr[i]
        j += 1
    # arr[i]값이 더 작으면, arr[i]의 값이 lis 배열 중 어느 곳에 들어올지 이분탐색한다.
    else:
        # 0부터 j까지 탐색하면서 arr[i]가 들어갈 수 있는 위치를 찾아서 idx에 반환
        idx = binarysearch(0, j, arr[i])
        lis[idx] = arr[i]
    i += 1

print(j+1)