🔥 이진 탐색으로 빠르게 푸는 최장 증가 부분 수열 (LIS) 알고리즘 대공개! 🚀

안녕하세요, 여러분! 오늘은 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 알고리즘을 이진 탐색을 이용해 효율적으로 푸는 방법에 대해 알아보겠습니다. 🧠✨ 초보자도 쉽게 따라올 수 있도록 하나하나 단계별로 설명드릴 테니 끝까지 함께 해주세요!

---

📚 LIS 알고리즘이란?

최장 증가 부분 수열(LIS)은 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것을 찾는 문제입니다. 예를 들어, 수열 [10, 20, 10, 30, 20, 50]의 LIS는 [10, 20, 30, 50]으로 길이는 4입니다.

---

🛠 이진 탐색을 이용한 LIS 알고리즘

이진 탐색을 활용하면 LIS 알고리즘의 시간 복잡도를 O(n log n)으로 줄일 수 있습니다. 어떻게 가능한지 함께 알아볼까요?

1️⃣ 초기화

• 빈 tails 배열 생성: 현재까지 가능한 LIS의 마지막 원소들을 관리합니다.
• tails_idx 배열 생성: tails에 저장된 원소들이 원래 수열에서 어디에 위치하는지 기록합니다.
• prev_idx 배열 생성: 각 원소의 이전 원소의 인덱스를 저장하여, 최종적으로 수열을 역추적할 수 있게 합니다.

import bisect

def lis(sequence):
    n = len(sequence)
    tails = []
    tails_idx = []
    prev_idx = [-1] * n

2️⃣ 수열 순회 및 업데이트

수열의 각 원소 num과 그 인덱스 i에 대해 다음을 수행합니다:

1. 이진 탐색으로 위치 찾기: pos = bisect.bisect_left(tails, num)
2. tails 업데이트:
   • pos가 tails의 길이와 같으면 num을 tails에 추가
   • 그렇지 않으면 tails[pos]를 num으로 대체
3. 인덱스 기록:
   • tails_idx[pos]를 현재 인덱스 i로 업데이트
   • prev_idx[i]는 pos > 0일 때 tails_idx[pos - 1]로 설정

    for i in range(n):
        num = sequence[i]
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            tails.append(num)
            tails_idx.append(i)
        else:
            tails[pos] = num
            tails_idx[pos] = i

        if pos > 0:
            prev_idx[i] = tails_idx[pos - 1]

3️⃣ LIS 수열 복원

tails_idx의 마지막 인덱스부터 시작하여 prev_idx를 따라가며 LIS 수열을 복원합니다.

    lis_length = len(tails)

    lis_sequence = []
    k = tails_idx[-1] if tails_idx else -1
    while k != -1:
        lis_sequence.append(sequence[k])
        k = prev_idx[k]
    lis_sequence.reverse()

    return lis_length, lis_sequence

💡 전체 알고리즘 코드

import bisect

def lis(sequence):
    n = len(sequence)
    tails = []
    tails_idx = []
    prev_idx = [-1] * n

    for i in range(n):
        num = sequence[i]
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            tails.append(num)
            tails_idx.append(i)
        else:
            tails[pos] = num
            tails_idx[pos] = i

        if pos > 0:
            prev_idx[i] = tails_idx[pos - 1]

    lis_length = len(tails)

    lis_sequence = []
    k = tails_idx[-1] if tails_idx else -1
    while k != -1:
        lis_sequence.append(sequence[k])
        k = prev_idx[k]
    lis_sequence.reverse()

    return lis_length, lis_sequence

# 🔍 예제 사용
sequence = [10, 20, 10, 30, 20, 50]
length, subsequence = lis(sequence)
print("LIS의 길이:", length)          # 출력: 4
print("LIS 수열:", subsequence)      # 출력: [10, 20, 30, 50]

# 📈 추가 예제
sequence2 = [3, 10, 2, 1, 20]
length2, subsequence2 = lis(sequence2)
print("LIS의 길이:", length2)         # 출력: 3
print("LIS 수열:", subsequence2)     # 출력: [3, 10, 20]

---

🧮 예제 분석: [10, 20, 10, 30, 20, 50]

초기 상태

tails: []
tails_idx: []
prev_idx: [-1, -1, -1, -1, -1, -1]

업데이트 과정

1. 10 (i = 0):

   • tails: [10]
   • tails_idx: [0]
   • prev_idx: [-1, -1, -1, -1, -1, -1]

2. 20 (i = 1):

   • tails: [10, 20]
   • tails_idx: [0, 1]
   • prev_idx: [-1, 0, -1, -1, -1, -1]

3. 10 (i = 2):

   • tails: [10, 20]
   • tails_idx: [2, 1]
   • prev_idx: [-1, 0, -1, -1, -1, -1]

4. 30 (i = 3):

   • tails: [10, 20, 30]
   • tails_idx: [2, 1, 3]
   • prev_idx: [-1, 0, -1, 1, -1, -1]

5. 20 (i = 4):

   • tails: [10, 20, 30]
   • tails_idx: [2, 4, 3]
   • prev_idx: [-1, 0, -1, 1, 2, -1]

6. 50 (i = 5):

   • tails: [10, 20, 30, 50]
   • tails_idx: [2, 4, 3, 5]
   • prev_idx: [-1, 0, -1, 1, 2, 3]

최종 상태

tails: [10, 20, 30, 50]
tails_idx: [2, 4, 3, 5]
prev_idx: [-1, 0, -1, 1, 2, 3]

• LIS의 길이: 4
• 복원된 LIS 수열: [10, 20, 30, 50]

---

🎯 결론

이진 탐색을 활용한 LIS 알고리즘은 효율적이고 직관적입니다. tails 배열을 유지하며 가능한 작은 값으로 LIS를 확장함으로써 더 긴 LIS를 구성할 수 있는 기회를 극대화합니다. 또한, tails_idx와 prev_idx를 활용해 실제 LIS 수열을 복원할 수 있습니다.

이번 포스팅을 통해 O(n log n) 시간 복잡도로 LIS를 구하는 방법을 이해하셨길 바랍니다. 💪 다음에도 유용한 알고리즘으로 다시 찾아뵙겠습니다. 감사합니다! 😊