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

1. LIS란 무엇인가?

1.1 정의

• 주어진 배열에서 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.
• 부분 수열은 배열의 원소 중 일부를 선택하여 만든 수열이며, 원소의 순서는 유지되어야 합니다.

1.2 예제

입력 배열: [10, 20, 10, 30, 20, 50]

• 가능한 부분 수열:
  • [10, 20] (길이: 2)
  • [10, 20, 30] (길이: 3)
  • [10, 20, 30, 50] (길이: 4)
• 결과:
  • LIS: [10, 20, 30, 50]
  • LIS의 길이: 4

2. LIS 문제 해결 방법

LIS 문제를 해결하기 위해 두 가지 대표적인 접근법이 있습니다.

1. 동적 계획법 (Dynamic Programming, DP)
   • 시간 복잡도: O(N²)
   • 간단하고 직관적.
   • 작은 배열에 적합.
2. 이분 탐색 (Binary Search)
   • 시간 복잡도: O(N log N)
   • 더 효율적.
   • 큰 배열에 적합.

3.1 동적 계획법 (O(N²))

1) 아이디어

• 배열의 i번째 원소까지의 LIS를 구하고, 이를 활용해 전체 LIS를 구합니다.
• dp[i]를 정의: 배열의 i번째 원소를 포함하는 LIS의 길이.
• 이전 원소와의 관계를 통해 현재 상태를 갱신합니다.

2) 점화식

• dp[i] = max(dp[j] + 1) for all j < i and arr[j] < arr[i]
  • dp[j]는 j번째 원소를 포함하는 LIS의 길이.
  • arr[j] < arr[i]일 때, arr[i]를 추가하여 LIS를 확장.

3) 기저 조건

• 초기값: 모든 원소는 최소한 길이 1의 LIS를 가지므로 dp[i] = 1.

4) 알고리즘 동작

• 각 원소마다 이전 원소들과 비교해 LIS를 갱신.
• 최종적으로 dp 배열의 최대값이 LIS의 길이.

5) 구현 코드

def lis(arr):
    n = len(arr)
    dp = [1] * n  # 모든 원소는 최소 길이 1의 LIS를 가짐

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:  # 증가 조건
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # LIS의 최대 길이 반환

6) 예제

arr = [10, 20, 10, 30, 20, 50]
print(lis(arr))  # 출력: 4

7) 동작 과정

• 입력 배열: [10, 20, 10, 30, 20, 50]
• dp 배열 변화:
  1. 초기화: [1, 1, 1, 1, 1, 1]
  2. i=1: [1, 2, 1, 1, 1, 1] (10 -> 20)
  3. i=3: [1, 2, 1, 3, 1, 1] (10 -> 20 -> 30)
  4. i=5: [1, 2, 1, 3, 2, 4] (10 -> 20 -> 30 -> 50)

최종 dp: [1, 2, 1, 3, 2, 4]
LIS 길이: 4 (최대값).

8) 시간 복잡도

• 외부 루프: O(N)
• 내부 루프: O(N)
• 총 시간 복잡도: O(N²).

3.2 이분 탐색 (O(N log N))

1) 아이디어

• LIS를 구하는 대신, LIS 길이를 구하기 위해 임시 배열(LIS)을 유지.
• 각 원소를 LIS 배열에 삽입하거나 대체하면서 길이를 계산.

2) 동작 원리

1. arr[i]가 LIS 배열의 마지막 값보다 크면 추가:
   • LIS 배열에 arr[i]를 추가하여 길이를 늘림.
2. arr[i]가 LIS 배열의 값보다 작거나 같으면, 적절한 위치에 교체:
   • LIS 배열의 값 교체는 길이에 영향을 주지 않으며, 이후 확장을 준비.

3) 구현 코드

import bisect

def lis(arr):
    lis = []  # 임시 LIS 배열

    for num in arr:
        pos = bisect.bisect_left(lis, num)  # num이 들어갈 위치
        if pos == len(lis):  # 가장 큰 값보다 크면 추가
            lis.append(num)
        else:  # 적절한 위치의 값을 교체
            lis[pos] = num

    return len(lis)  # LIS의 길이 반환

4) 예제

arr = [10, 20, 10, 30, 20, 50]
print(lis(arr))  # 출력: 4

5) 동작 과정

• 입력 배열: [10, 20, 10, 30, 20, 50]
• LIS 배열 변화:
  1. 10: [10]
  2. 20: [10, 20]
  3. 10: [10, 20] (교체 X)
  4. 30: [10, 20, 30]
  5. 20: [10, 20, 30] (교체 X)
  6. 50: [10, 20, 30, 50]

최종 LIS 배열: [10, 20, 30, 50]
LIS 길이: 4.

6) 시간 복잡도

• 각 원소에 대해 bisect_left 호출: O(log N).
• 총 시간 복잡도: O(N log N).

4. 비교

                                 특징                                                       DP 방식 (O(N²))                                이분 탐색 방식 (O(N log N))

시간 복잡도	O(N²)	O(N log N)
직관성	상대적으로 쉬움	이분 탐색의 이해 필요
구현 난이도	간단	약간 복잡
LIS 길이 계산 가능 여부	가능	가능
LIS 자체 출력	추가 작업 필요	추가 작업 필요

5. LIS 자체를 출력하는 방법

LIS 자체를 출력하려면 DP 방식에서 추적 배열을 사용하거나, 이분 탐색 방식에서 경로 추적을 추가해야 합니다.

5.1 DP 방식으로 LIS 출력

코드:

def lis_with_sequence(arr):
    n = len(arr)
    dp = [1] * n
    prev = [-1] * n  # 이전 인덱스를 저장하는 배열

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j  # 경로 추적

    # LIS 길이와 마지막 인덱스 찾기
    max_len = max(dp)
    idx = dp.index(max_len)

    # LIS 수열 추적
    sequence = []
    while idx != -1:
        sequence.append(arr[idx])
        idx = prev[idx]

    return max_len, sequence[::-1]

# 테스트
arr = [10, 20, 10, 30, 20, 50]
length, sequence = lis_with_sequence(arr)
print("LIS 길이:", length)  # 출력: 4
print("LIS 수열:", sequence)  # 출력: [10, 20, 30, 50]

6. 연습 문제

1. 배열 [3, 10, 2, 1, 20]의 LIS를 구하세요.
2. LIS를 출력하는 코드를 작성해 보세요.
3. DP 방식과 이분 탐색 방식의 성능 차이를 실험해 보세요 (N이 큰 경우).

요약

• LIS 문제는 효율적인 알고리즘 학습에 적합한 문제로, DP와 이분 탐색 두 가지 접근법 모두 중요합니다.
• DP는 직관적이지만 느리고, 이분 탐색은 빠르지만 약간 복잡합니다.
• 연습을 통해 두 방법 모두 익혀야 합니다.