5-10. DP: LIS (최장 증가 부분 수열) - 심화

1. 최장 증가 부분 수열 (LIS) 문제 복습

최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 문제는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다. 예를 들어, 수열 [1, 3, 2, 4, 5]가 주어졌을 때, LIS는 [1, 2, 4, 5] 또는 [1, 3, 4, 5]이며, 길이는 4입니다. LIS는 컴퓨터 과학 분야에서 다양한 알고리즘 문제 해결의 기초가 되며, 동적 프로그래밍 (DP)과 같은 중요한 기술을 익히는 데 매우 유용합니다.

1) 문제 정의와 목표

LIS 문제의 목표는 주어진 수열 내에서 가장 긴 증가하는 부분 수열을 찾는 것입니다. 여기서 "증가하는 부분 수열"이란, 부분 수열의 각 원소가 이전 원소보다 큰 값을 가지는 것을 의미합니다. 문제의 핵심은 가능한 모든 부분 수열을 고려하면서, 증가 조건을 만족하고 길이가 가장 긴 부분 수열을 효율적으로 찾는 것입니다.

2) LIS 문제의 중요성

LIS 문제는 단순한 알고리즘 문제 이상으로, 다양한 분야에서 응용될 수 있는 핵심적인 아이디어를 담고 있습니다. 예를 들어, 데이터베이스 쿼리 최적화, 생물 정보학에서의 서열 분석, 그리고 운영 체제의 작업 스케줄링 등에서 LIS의 개념이 활용될 수 있습니다. LIS 알고리즘을 이해하면, 이러한 문제들을 해결하는 데 필요한 사고방식과 기술을 습득할 수 있습니다.

2. LIS 문제 해결 방법: $O(n^2)$ 동적 프로그래밍

가장 기본적인 LIS 해결 방법은 동적 프로그래밍 (DP)을 사용하는 것입니다. 이 방법은 각 i번째 원소를 마지막 원소로 하는 LIS의 길이를 계산하며, 시간 복잡도는 $O(n^2)$입니다.

1) 알고리즘 개요

DP를 이용한 LIS 알고리즘은 다음과 같은 단계를 거칩니다.

1. dp 배열 초기화: 각 원소를 마지막 원소로 하는 LIS의 길이를 저장하는 dp 배열을 생성합니다. dp[i]는 i번째 원소를 마지막 원소로 하는 LIS의 길이를 나타냅니다. 모든 dp[i]를 1로 초기화합니다. (각 원소 자체는 길이가 1인 LIS를 형성할 수 있습니다.)
2. 반복 계산: 수열의 각 원소 i에 대해, i보다 앞에 있는 원소 j들을 순회하면서 다음을 수행합니다. 만약 arr[j] < arr[i]라면, 즉 j번째 원소가 i번째 원소보다 작다면, dp[i] = max(dp[i], dp[j] + 1)로 갱신합니다. 이는 j번째 원소를 마지막 원소로 하는 LIS에 i번째 원소를 추가하여 더 긴 LIS를 만들 수 있는 경우를 의미합니다.
3. 결과 반환: dp 배열에서 가장 큰 값을 찾아 반환합니다. 이는 전체 수열의 LIS의 길이를 나타냅니다.

2) 코드 예시

다음은 Python으로 작성된 $O(n^2)$ LIS 알고리즘의 예시 코드입니다.

def lis_n2(arr):
    n = len(arr)
    dp = [1] * n  # 각 원소를 마지막 원소로 하는 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)

3) 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 $O(n^2)$입니다. 이는 중첩된 두 개의 for 루프에 기인합니다. 외부 루프는 n번 실행되고, 내부 루프는 최악의 경우 i번 실행됩니다. 따라서 총 연산 횟수는 대략 $\sum_{i=1}^{n} i = \frac{n(n-1)}{2}$ 이므로, 시간 복잡도는 $O(n^2)$가 됩니다.

3. LIS 문제 해결 방법: $O(n \log n)$ 알고리즘

$O(n^2)$ 알고리즘은 간단하지만, 수열의 크기가 커질수록 성능 저하가 발생합니다. 더 효율적인 알고리즘으로, 시간 복잡도 $O(n \log n)$으로 LIS를 해결할 수 있습니다. 이 알고리즘은 이진 탐색을 사용하여 LIS를 구성하는 데 필요한 값을 효율적으로 관리합니다.

1) 핵심 아이디어: tails 배열

$O(n \log n)$ 알고리즘의 핵심은 tails라는 배열을 사용하는 것입니다. tails[i]는 길이가 i+1인 증가하는 부분 수열의 마지막 원소들 중 가장 작은 값을 저장합니다. tails 배열은 항상 오름차순으로 정렬된 상태를 유지합니다.

2) 알고리즘 단계

1. tails 배열 초기화: tails 배열은 비어있는 상태로 시작합니다.
2. 수열 순회: 입력 수열의 각 원소 x에 대해 다음을 수행합니다.
   • 이진 탐색: tails 배열에서 x보다 크거나 같은 첫 번째 원소의 위치를 이진 탐색을 통해 찾습니다.
   • 갱신:
     • 만약 x가 tails 배열의 모든 원소보다 크다면, x를 tails 배열의 맨 뒤에 추가합니다. (LIS의 길이가 1 증가)
     • 만약 x가 tails 배열의 어떤 원소보다 작거나 같다면, 해당 위치의 원소를 x로 대체합니다. (기존 LIS의 마지막 원소보다 작은 값으로 갱신하여, 더 긴 LIS를 만들 가능성을 열어둠)
3. 결과: tails 배열의 길이가 LIS의 길이가 됩니다.

3) 코드 예시

다음은 Python으로 작성된 $O(n \log n)$ LIS 알고리즘의 예시 코드입니다.

import bisect

def lis_nlogn(arr):
    tails = []
    for x in arr:
        # x보다 크거나 같은 첫 번째 원소의 위치를 찾음
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)  # x가 tails의 모든 원소보다 크면 tails에 추가
        else:
            tails[i] = x  # x가 tails의 어떤 원소보다 작거나 같으면 갱신
    return len(tails)

4) 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 $O(n \log n)$입니다. 입력 수열의 각 원소에 대해 이진 탐색을 한 번 수행하므로, 이진 탐색의 시간 복잡도 $O(\log n)$이 각 원소에 적용됩니다. 따라서 전체 시간 복잡도는 $O(n \log n)$이 됩니다. tails 배열의 삽입/수정 연산은 $O(1)$ 시간에 수행됩니다.

4. LIS 알고리즘의 응용

LIS 알고리즘은 다양한 문제를 해결하는 데 응용될 수 있습니다.

1) 응용 예시: "Building Bridges" 문제

"Building Bridges" 문제는 LIS의 전형적인 응용 사례입니다. 두 개의 강둑에 위치한 도시들을 연결하는 다리를 건설하는 문제입니다. 각 다리는 강을 가로지르며, 다리들이 서로 교차하지 않도록 건설해야 합니다. 이 문제는 LIS를 사용하여 해결할 수 있습니다.

• 문제: 각 도시의 위치 정보가 주어졌을 때, 교차하지 않도록 건설할 수 있는 다리의 최대 개수를 구하는 문제
• 해결: 한쪽 강둑의 도시들을 기준으로 정렬하고, 다른 쪽 강둑의 도시들의 위치 정보를 LIS 문제로 변환하여 해결

2) 응용 예시: "Longest Bitonic Subsequence" 문제

"Longest Bitonic Subsequence" 문제는 LIS와 LDS (Longest Decreasing Subsequence, 최장 감소 부분 수열)을 결합한 문제입니다. Bitonic 수열은 먼저 증가하다가 감소하는 수열을 의미합니다.

• 문제: 주어진 수열에서 가장 긴 Bitonic 부분 수열의 길이를 구하는 문제
• 해결: 각 원소를 중심으로 LIS와 LDS를 계산하고, LIS와 LDS의 길이를 더한 값에서 중복되는 원소 하나를 뺀 값이 Bitonic 부분 수열의 길이가 됩니다. 모든 원소에 대해 이 값을 계산하여 최댓값을 찾습니다.

3) 응용 문제 풀이 전략

LIS 알고리즘을 응용하는 문제들을 해결하기 위한 일반적인 전략은 다음과 같습니다.

1. 문제 이해: 문제에서 요구하는 사항을 정확히 이해하고, LIS와 어떻게 관련되는지 파악합니다.
2. 문제 변환: 주어진 문제를 LIS 문제로 변환할 수 있는지 검토합니다. 도시 위치, 물건의 크기, 작업의 우선순위 등, LIS의 적용 가능성을 확인합니다.
3. 알고리즘 선택: $O(n^2)$ 또는 $O(n \log n)$ 알고리즘 중 적절한 알고리즘을 선택합니다. 입력 크기에 따라 알고리즘의 효율성을 고려합니다.
4. 구현 및 테스트: 선택한 알고리즘을 구현하고, 다양한 테스트 케이스를 통해 정확성을 검증합니다.

5. LIS 알고리즘의 주의사항 및 개선

1) 메모리 사용량

$O(n^2)$ 알고리즘은 dp 배열을 사용하며, $O(n)$의 메모리 공간을 필요로 합니다. $O(n \log n)$ 알고리즘은 tails 배열을 사용하며, 최악의 경우 $O(n)$의 메모리 공간을 필요로 합니다. 대부분의 LIS 문제에서는 메모리 사용량이 큰 문제가 되지 않지만, 매우 큰 입력에 대해서는 메모리 사용량을 고려해야 합니다.

2) 실제 사용 팁

• 입력 크기: 입력 데이터의 크기에 따라 적절한 알고리즘을 선택해야 합니다. n의 크기가 작다면 $O(n^2)$ 알고리즘도 괜찮지만, n이 큰 경우에는 $O(n \log n)$ 알고리즘을 사용하는 것이 좋습니다.
• 구현 최적화: 코드의 효율성을 높이기 위해, 이진 탐색 구현 시 bisect 모듈을 사용하는 것이 좋습니다. (Python 기준)
• 예외 처리: 입력 데이터의 예외 상황 (예: 빈 배열, 모든 원소가 같은 값)에 대한 처리를 고려해야 합니다.

3) 추가 개선

• LIS 복원: LIS의 길이뿐만 아니라 LIS 자체를 복원해야 하는 경우, $O(n^2)$ 알고리즘에서는 dp 배열과 함께 각 원소의 이전 원소를 저장하는 배열을 추가하여 LIS를 추적할 수 있습니다. $O(n \log n)$ 알고리즘에서는 LIS의 각 원소의 이전 원소를 저장하기 위해 추가적인 자료 구조가 필요합니다.
• 병렬 처리: LIS 알고리즘은 병렬 처리가 가능합니다. 특히 $O(n^2)$ 알고리즘은 각 dp[i]를 계산하는 과정이 서로 독립적이므로, 병렬 처리를 통해 성능을 향상시킬 수 있습니다.

6. 결론

최장 증가 부분 수열 (LIS) 문제는 동적 프로그래밍과 이진 탐색을 활용하여 효율적으로 해결할 수 있는 중요한 알고리즘 문제입니다. $O(n^2)$ 알고리즘과 $O(n \log n)$ 알고리즘의 원리를 이해하고, 응용 문제에 적용하는 연습을 통해 문제 해결 능력을 향상시킬 수 있습니다. LIS 알고리즘은 다양한 컴퓨터 과학 문제 해결의 기초가 되며, 문제 해결 능력 향상에 기여합니다.