파이썬 코딩테스트 강좌, 가장 길게 증가하는 부분 수열 찾기

이 강좌에서는 파이썬 코딩테스트의 중요한 개념 중 하나인 “가장 길게 증가하는 부분 수열” (Longest Increasing Subsequence, LIS)을 찾는 문제를 다룰 것입니다. 이 문제는 여러 IT 기업의 코딩 알고리즘 시험에 자주 등장하며, 효율적인 알고리즘 설계와 구현 능력을 요구합니다. 따라서 제대로 이해하고 연습하는 것이 중요합니다.

1. 문제 설명

주어진 수열에서 증가하는 부분 수열의 길이 중 가장 긴 것을 찾는 문제입니다. 부분 수열은 원래 수열에서 일부 원소들을 선택하여 순서를 유지하면서 만드는 수열입니다. 예를 들어, 수열 [10, 20, 10, 30, 20, 50]이 주어질 때, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4입니다.

2. 문제 접근 및 이해

가장 긴 증가하는 부분 수열 문제는 다음과 같은 특징을 가지고 있습니다.

  • 부분 수열의 원소는 반드시 원래 수열에서 순서를 유지해야 합니다.
  • 부분 수열의 길이를 찾아야 하며, 부분 수열 자체를 찾아야 하는 것은 아닙니다.

이 문제를 해결하기 위해서는 두 가지 접근 방법을 사용할 수 있습니다.

  1. 동적 프로그래밍(Dynamic Programming) 접근법
  2. 이진 탐색(Binary Search) 접근법

2.1 동적 프로그래밍 접근법

동적 프로그래밍을 이용하면 수열의 각 원소를 기준으로 가장 긴 증가하는 부분 수열의 길이를 유지할 수 있습니다. 이 접근법의 시간 복잡도는 O(n^2)입니다.

동적 프로그래밍을 이용한 알고리즘을 다음과 같이 설명할 수 있습니다:

  1. dp[i]를 증가하는 부분 수열의 길이로 초기화하여 모든 값을 1로 설정합니다.
  2. 각 원소 i에 대해 이전 원소 j (j < i)를 순회하면서, arr[j] < arr[i]인 경우 dp[i]를 dp[j] + 1로 업데이트합니다.
  3. 최종 결과는 dp 배열의 최대값입니다.

2.2 이진 탐색 접근법

이진 탐색을 이용한 방법은 좀 더 효율적이며, 시간 복잡도는 O(n log n)입니다. 이 방법은 ‘tails’라는 배열을 이용하여 현재까지의 가장 긴 증가하는 부분 수열의 끝 원소를 저장합니다.

이진 탐색 접근법의 알고리즘을 다음과 같이 설명할 수 있습니다:

  1. 빈 배열을 초기화합니다.
  2. 수열을 순회하면서 현재 원소에 대해 이진 탐색을 수행하여 tails 배열에서 현재 원소를 삽입할 위치를 찾습니다.
  3. 찾은 위치가 tails 배열의 길이와 같다면, 현재 원소를 추가하고 그렇지 않다면 해당 위치를 현재 원소로 업데이트합니다.
  4. 최종 결과는 tails의 길이입니다.

3. 알고리즘 구현

3.1 동적 프로그래밍 구현

def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n  # 초기화
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

3.2 이진 탐색 구현

from bisect import bisect_left

def longest_increasing_subsequence(arr):
    tails = []
    for x in arr:
        i = bisect_left(tails, x)  # x보다 큰 원소의 인덱스 찾기
        if i == len(tails):
            tails.append(x)  # 새로운 원소 추가
        else:
            tails[i] = x  # 원소 업데이트
    return len(tails)

4. 예제와 결과

이제 위에서 구현한 알고리즘을 통해 몇 가지 예제를 돌려보겠습니다.

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

arr = [3, 2, 5, 6, 3, 7, 1]
print(longest_increasing_subsequence(arr))  # 출력: 5

arr = [1, 2, 3, 4, 5]
print(longest_increasing_subsequence(arr))  # 출력: 5

5. 결론

가장 길게 증가하는 부분 수열 찾기 문제는 코딩 인터뷰에서 자주 등장하는 문제로, 동적 프로그래밍과 이진 탐색 두 가지의 접근법을 통해 해결할 수 있습니다. 이 문제를 통해 동적 프로그래밍의 개념과 이진 탐색의 활용을 모두 익힐 수 있으며, 복잡한 알고리즘 문제를 풀기 위한 기초를 다질 수 있습니다.

여기까지 가장 길게 증가하는 부분 수열을 찾는 파이썬 코딩테스트 강좌를 마치겠습니다. 알고리즘 문제를 해결하는 데 도움이 되었길 바랍니다. 지속적인 연습을 통해 알고리즘 실력을 향상시키고, 다음 코딩 테스트에 대비하세요!