안녕하세요! 이번 포스트에서는 코딩 테스트에서 자주 출제되는 “가장 길게 증가하는 부분 수열” 문제를 다뤄보겠습니다. 이 문제는 알고리즘의 기초를 이해하고, 실력을 쌓는 데 큰 도움이 됩니다. 문제를 효과적으로 풀기 위한 이론과 코틀린을 활용한 구체적인 구현 과정을 설명하겠습니다.
문제 설명
주어진 배열에서 가장 길게 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 찾는 문제입니다. 부분 수열이란, 원래 배열의 원소를 순서대로 선택해서 만든 배열이며, 원래 배열의 순서를 유지해야 합니다. 증가 수열이란 원소들이 모두 오름차순으로 정렬되어 있는 수열을 의미합니다.
예제
입력: [10, 22, 9, 33, 21, 50, 41, 60, 80]
출력: 6
설명: 가장 길게 증가하는 부분 수열의 예는 [10, 22, 33, 50, 60, 80]입니다.
문제 풀이 접근법
이 문제를 해결하기 위한 기본적인 접근법은 동적 프로그래밍(DP)을 사용하는 것입니다. DP는 문제를 작은 부분 문제로 나누어 푸는 방법이며, 이전의 계산 결과를 저장하여 같은 계산을 반복하지 않도록 합니다.
1단계: DP 테이블 초기화
먼저 DP 테이블을 초기화합니다. 입력 배열의 각 인덱스에서 시작할 때의 LIS 길이를 저장할 배열을 생성합니다. 초기에는 각 원소가 자기 자신으로 이루어진 부분 수열이 최대이므로 모든 값은 1로 설정합니다.
2단계: DP 테이블 업데이트
이제 입력 배열의 모든 원소에 대해 서로 비교합니다. 각 원소 arr[i]에 대해, 그보다 앞에 있는 모든 원소 arr[j] (j < i)를 확인하여 다음 조건을 평가합니다:
if arr[i] > arr[j] then
dp[i] = max(dp[i], dp[j] + 1)
여기서 dp[i]는 arr[i]를 포함하는 LIS의 길이이며, dp[j] + 1은 arr[j] 다음에 arr[i]를 추가한 경우의 길이를 나타냅니다.
3단계: 결과 도출
모든 원소에 대한 처리가 끝난 후, dp 배열에서 가장 큰 값을 찾아 LIS의 길이를 결과로 반환합니다.
코틀린 구현
이제 직접 코틀린으로 구현해보겠습니다. 아래는 앞서 설명한 알고리즘을 따르는 코드입니다.
fun longestIncreasingSubsequence(arr: IntArray): Int {
val n = arr.size
val dp = IntArray(n) { 1 } // initialize dp array
for (i in 1 until n) {
for (j in 0 until i) {
if (arr[i] > arr[j]) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
}
return dp.maxOrNull() ?: 1 // return the maximum value in dp array
}
fun main() {
val arr = intArrayOf(10, 22, 9, 33, 21, 50, 41, 60, 80)
val length = longestIncreasingSubsequence(arr)
println("가장 길게 증가하는 부분 수열의 길이: $length")
}
복잡도 분석
결과적으로, 이 알고리즘의 시간 복잡도는 O(n²)입니다. 이는 중첩된 반복문이 n에 대해 실행되기 때문입니다. 공간 복잡도는 O(n)으로 DP 배열을 저장하기 위한 공간이 필요합니다.
최적화 방법
만약 더 높은 성능이 요구된다면, 이진 탐색(binary search)을 활용하여 LIS 문제를 O(n log n)으로 해결할 수 있습니다. 이 방법은 다음과 같은 방식으로 구현됩니다:
import java.util.*
fun longestIncreasingSubsequenceOptimized(arr: IntArray): Int {
if (arr.isEmpty()) return 0
val tails = mutableListOf()
for (num in arr) {
val index = tails.binarySearch(num)
if (index < 0) {
val pos = -(index + 1)
if (pos == tails.size) {
tails.add(num)
} else {
tails[pos] = num
}
}
}
return tails.size
}
여기서는 tails 배열이 LIS의 가능한 마지막 요소들을 저장합니다. 이진 탐색을 통해 적절한 위치를 찾아 삽입하거나 교체합니다.
마무리
이번 글에서는 코틀린을 이용한 가장 길게 증가하는 부분 수열 문제에 대해 알아보았습니다. 문제의 접근 방식과 구현 방법을 자세히 설명드렸고, 추가적으로 최적화 방법도 다뤘습니다. 이러한 문제들은 코딩 테스트에서 자주 출제되므로, 반복적인 연습이 중요합니다. 앞으로도 다양한 알고리즘 문제를 함께 나누도록 하겠습니다. 궁금한 점이 있다면 댓글로 질문해 주세요!