LIS(Longest Increasing Subsequence)는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이를 찾는 문제입니다. 이때, 증가하는 부분 수열이란 수열에서 원소의 순서를 유지하면서 일부 원소를 선택한 부분 수열을 말합니다. LIS 문제는 동적 계획법(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다.

LIS 문제의 주요 아이디어:

1. DP 테이블: 길이 i까지의 LIS를 구하기 위해 DP 테이블을 만들고, 각 위치에서 최적의 LIS 길이를 업데이트합니다.
2. 이전 원소 검사: 현재 원소보다 이전 원소들을 검사하면서 현재 원소를 포함하여 LIS 길이를 갱신합니다.

LIS의 활용 예시:

• 가장 긴 증가하는 부분 수열 길이: 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾을 때 LIS를 사용합니다.
• 가장 긴 바이토닉 부분 수열 길이: 수열에서 어느 한 지점을 기준으로 증가하다가 감소하는 부분 수열 중 가장 긴 길이를 찾을 때 LIS를 사용합니다.

파이썬 코드를 통해 LIS를 예시로 살펴보겠습니다. 다음은 주어진 수열에서 LIS 길이를 구하는 동적 계획법(LIS DP) 코드입니다.

def lis_length(arr):
    n = len(arr)
    lis = [1] * n  # DP 테이블 초기화

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    return max(lis)

# 주어진 수열
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]

length = lis_length(sequence)
print("LIS의 길이:", length)

이 코드는 주어진 수열에서 LIS의 길이를 구하는 예시입니다. DP 테이블을 이용하여 각 위치에서 가장 긴 LIS 길이를 계산하고, 최종적으로 그 중 가장 큰 값을 선택합니다.