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

1. 최장 증가 부분 수열 (LIS) 문제 소개

최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 문제는 컴퓨터 과학 분야에서 널리 알려진 동적 프로그래밍 (Dynamic Programming, DP) 문제입니다. 주어진 수열에서 증가하는 부분 수열 중 가장 긴 수열의 길이를 찾는 것이 목표입니다. 여기서 부분 수열은 원래 수열의 원소들을 순서를 유지하면서 선택하여 만든 수열을 의미합니다.

예를 들어, 수열 [1, 3, 2, 4, 5]가 주어졌을 때, LIS는 [1, 2, 4, 5] 또는 [1, 3, 4, 5]가 될 수 있으며, 길이는 4입니다. LIS는 다양한 알고리즘 문제 해결의 기반이 되며, 최적화, 데이터 분석 등 실용적인 분야에서도 활용됩니다.

2. DP를 활용한 LIS 해결

LIS 문제는 DP를 사용하여 효율적으로 해결할 수 있습니다. DP는 문제를 작은 하위 문제로 나누어 해결하고, 하위 문제의 해결 결과를 저장하여 중복 계산을 피하는 방식으로 작동합니다. LIS 문제에서는 각 원소를 기준으로 LIS 길이를 계산하고, 이 정보를 활용하여 전체 수열의 LIS를 구합니다.

1) DP 테이블 정의

DP 테이블 dp를 정의합니다. dp[i]는 i번째 원소를 마지막 원소로 하는 LIS의 길이를 저장합니다. 즉, dp[i]는 nums[i]를 포함하는 LIS의 길이입니다.

2) 점화식 유도

점화식은 다음과 같이 정의됩니다.

• dp[i] = 1 (초기값: 자기 자신만 포함하는 LIS)
• dp[i] = max(dp[i], dp[j] + 1) for j in range(0, i) if nums[j] < nums[i] (nums[i]보다 작은 값들 중에서 가장 긴 LIS의 길이에 1을 더함)

이 점화식은 nums[i]보다 작은 원소 nums[j]를 찾고, nums[j]를 마지막 원소로 하는 LIS의 길이에 1을 더하여 nums[i]를 마지막 원소로 하는 LIS의 길이를 업데이트합니다.

3) 초기값 설정

모든 dp[i]는 최소 1로 초기화됩니다. 이는 각 원소가 자기 자신만을 포함하는 LIS를 구성할 수 있기 때문입니다.

4) DP 테이블 채우기

DP 테이블을 채우는 과정은 다음과 같습니다.

1. dp 테이블을 1로 초기화합니다.
2. i를 0부터 n-1까지 반복하면서, 각 i에 대해 j를 0부터 i-1까지 반복합니다.
3. 만약 nums[j] < nums[i]라면, dp[i] = max(dp[i], dp[j] + 1)을 수행합니다.
4. DP 테이블을 모두 채운 후, dp 테이블의 최댓값이 LIS의 길이가 됩니다.

3. O(n^2) 풀이: 구현 및 예시

위에서 설명한 DP 알고리즘을 구현하는 가장 직관적인 방법은 O(n²)의 시간 복잡도를 갖는 이중 루프를 사용하는 것입니다.

def longest_increasing_subsequence_n2(nums):
    """
    O(n^2) 시간 복잡도로 LIS를 계산합니다.

    Args:
        nums: 정수 리스트.

    Returns:
        LIS의 길이.
    """
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n  # 각 원소를 마지막으로 하는 LIS의 길이를 저장
    for i in range(1, n):
        for j in range(0, i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

예시: 수열 [1, 3, 2, 4, 5]에 대한 O(n²) 풀이 과정을 살펴보겠습니다.

1. 초기화: dp = [1, 1, 1, 1, 1]
2. i = 1:
   • j = 0: nums[0] (1) < nums[1] (3) 이므로, dp[1] <mark class="highlight"><strong><u> max(1, dp[0] + 1) </u></strong></mark> 2. dp = [1, 2, 1, 1, 1]
3. i = 2:
   • j = 0: nums[0] (1) < nums[2] (2) 이므로, dp[2] <mark class="highlight"><strong><u> max(1, dp[0] + 1) </u></strong></mark> 2. dp = [1, 2, 2, 1, 1]
   • j = 1: nums[1] (3) < nums[2] (2) 는 거짓.
4. i = 3:
   • j = 0: nums[0] (1) < nums[3] (4) 이므로, dp[3] <mark class="highlight"><strong><u> max(1, dp[0] + 1) </u></strong></mark> 2. dp = [1, 2, 2, 2, 1]
   • j = 1: nums[1] (3) < nums[3] (4) 이므로, dp[3] <mark class="highlight"><strong><u> max(2, dp[1] + 1) </u></strong></mark> 3. dp = [1, 2, 2, 3, 1]
   • j = 2: nums[2] (2) < nums[3] (4) 이므로, dp[3] <mark class="highlight"><strong><u> max(3, dp[2] + 1) </u></strong></mark> 3.
5. i = 4:
   • j = 0: nums[0] (1) < nums[4] (5) 이므로, dp[4] <mark class="highlight"><strong><u> max(1, dp[0] + 1) </u></strong></mark> 2. dp = [1, 2, 2, 3, 2]
   • j = 1: nums[1] (3) < nums[4] (5) 이므로, dp[4] <mark class="highlight"><strong><u> max(2, dp[1] + 1) </u></strong></mark> 3. dp = [1, 2, 2, 3, 3]
   • j = 2: nums[2] (2) < nums[4] (5) 이므로, dp[4] <mark class="highlight"><strong><u> max(3, dp[2] + 1) </u></strong></mark> 3.
   • j = 3: nums[3] (4) < nums[4] (5) 이므로, dp[4] <mark class="highlight"><strong><u> max(3, dp[3] + 1) </u></strong></mark> 4. dp = [1, 2, 2, 3, 4]

최종적으로 dp는 [1, 2, 2, 3, 4]가 되고, LIS의 길이는 max(dp) = 4가 됩니다.

4. O(n log n) 풀이: 이진 탐색 활용

O(n²) 풀이는 간단하지만, 입력 크기가 커질수록 성능 저하가 발생합니다. O(n log n) 풀이는 이진 탐색을 활용하여 더 효율적인 해결책을 제공합니다.

1) 핵심 아이디어

O(n log n) 풀이의 핵심 아이디어는 tails라는 배열을 유지하는 것입니다. tails[i]는 길이가 i+1인 LIS의 마지막 원소 중 가장 작은 값을 저장합니다. tails 배열은 항상 정렬된 상태를 유지하며, 이진 탐색을 통해 효율적으로 값을 찾아 업데이트할 수 있습니다.

2) 알고리즘 단계

1. tails 배열을 생성하고, 입력 수열의 각 원소 num에 대해 다음을 수행합니다.
2. tails 배열에서 num보다 크거나 같은 값 중 가장 작은 값을 이진 탐색으로 찾습니다.
   • 만약 num보다 크거나 같은 값이 없다면, num을 tails 배열의 맨 뒤에 추가합니다. 이는 LIS의 길이가 1 증가함을 의미합니다.
   • 만약 num보다 크거나 같은 값이 있다면, 해당 값을 num으로 대체합니다. 이는 현재 길이의 LIS를 유지하면서 마지막 원소를 더 작은 값으로 갱신하여, 추후 더 긴 LIS를 만들 수 있는 가능성을 열어둡니다.
3. 모든 원소를 처리한 후, tails 배열의 길이가 LIS의 길이가 됩니다.

import bisect

def longest_increasing_subsequence_nlogn(nums):
    """
    O(n log n) 시간 복잡도로 LIS를 계산합니다.

    Args:
        nums: 정수 리스트.

    Returns:
        LIS의 길이.
    """
    tails = []
    for num in nums:
        # num보다 크거나 같은 값을 이진 탐색으로 찾음
        i = bisect.bisect_left(tails, num)
        if i == len(tails):
            tails.append(num)  # num이 tails의 모든 값보다 크면 tails에 추가
        else:
            tails[i] = num  # num이 tails의 값보다 작거나 같으면 해당 위치의 값 갱신
    return len(tails)

예시: 수열 [1, 3, 2, 4, 5]에 대한 O(n log n) 풀이 과정을 살펴보겠습니다.

1. nums[0] 1: tails </u></strong></mark> [1]
2. nums[1] 3: tails </u></strong></mark> [1, 3]
3. nums[2] 2: tails </u></strong></mark> [1, 2] (3이 2로 대체됨)
4. nums[3] 4: tails </u></strong></mark> [1, 2, 4]
5. nums[4] 5: tails </u></strong></mark> [1, 2, 4, 5]