알고리즘 문제를 풀기 위해서는 문제의 본질을 이해하고, 적절한 자료구조와 알고리즘을 선택하는 것이 매우 중요합니다. 이번 강좌에서는 ‘가장 길게 증가하는 부분 수열(Longest Increasing Subsequence, LIS)’ 문제를 다룰 것입니다. 이 문제는 특정 데이터를 처리할 때, 증가하는 순서를 유지한 채로 가능한 가장 긴 부분 수열을 찾아내는 문제입니다.
1. 문제 정의
주어진 정수 배열에서 가장 길게 증가하는 부분 수열을 찾는 문제입니다. 부분 수열은 배열에서 몇 개의 수를 선택하여 순서를 유지한 채로 만든 수열을 의미합니다. 여기서 중요한 것은 선택한 수가 반드시 연속해서 있어야 할 필요는 없다는 점입니다. 즉, [10, 20, 10, 30, 20, 50]라는 배열이 주어졌을 때, 가장 길게 증가하는 부분 수열은 [10, 20, 30, 50]입니다.
1.1 문제 예시
입력: [10, 20, 10, 30, 20, 50]
출력: 4 (부분 수열: [10, 20, 30, 50])
입력: [5, 6, 3, 7, 8, 4, 1]
출력: 5 (부분 수열: [5, 6, 7, 8])
2. 문제 접근 방법
가장 길게 증가하는 부분 수열 문제는 다음 두 가지 기본 접근 방법을 사용할 수 있습니다:
- 동적 계획법(Dynamic Programming)
- 이분 탐색(Binary Search)
2.1 동적 계획법
동적 계획법은 주어진 문제를 작은 부분 문제로 나누어 해결하는 방식입니다. LIS 문제를 동적 계획법으로 해결하기 위해서는 두 개의 배열을 사용할 수 있습니다. 하나는 원본 배열의 각 원소에 대해 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열, 다른 하나는 그 수열을 구성하는 원소들을 저장하는 배열입니다.
2.2 이분 탐색
이 방법은 LIS 문제를 보다 효율적으로 해결할 수 있게 해줍니다. 이분 탐색을 이용한 방법은 O(n log n) 시간 복잡도를 가지며, 배열을 탐색하는 과정에서 이미 발견된 증가하는 부분 수열의 길이를 이용하여 각 원소의 위치를 결정합니다.
3. 알고리즘 구현
아래는 스위프트로 구현한 동적 계획법과 이분 탐색을 이용한 LIS 문제의 해결 과정입니다.
3.1 동적 계획법 구현
func lengthOfLIS(_ nums: [Int]) -> Int {
guard !nums.isEmpty else { return 0 }
var dp = Array(repeating: 1, count: nums.count)
var maxLength = 1
for i in 1.. nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
maxLength = max(maxLength, dp[i])
}
return maxLength
}
// 사용 예시
let nums = [10, 20, 10, 30, 20, 50]
print(lengthOfLIS(nums)) // 출력: 4
3.2 이분 탐색 구현
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int]()
for num in nums {
if let idx = dp.firstIndex(where: { $0 >= num }) {
dp[idx] = num
} else {
dp.append(num)
}
}
return dp.count
}
// 사용 예시
let nums = [10, 20, 10, 30, 20, 50]
print(lengthOfLIS(nums)) // 출력: 4
4. 시간 복잡도 분석
동적 계획법의 경우, 이중 루프를 사용하여 모든 쌍의 배열 원소를 비교하므로 O(n^2) 시간 복잡도를 가집니다. 반면, 이분 탐색을 통해 구현한 방법은 O(n log n)의 시간 복잡도를 가집니다. 이는 큰 입력을 처리할 때 보다 효율적입니다.
5. 결론
오늘은 가장 길게 증가하는 부분 수열을 찾는 문제를 다루어 보았습니다. 동적 계획법과 이분 탐색 방식의 두 가지 접근 방법을 살펴보았으며, 각각의 구현과 시간 복잡도를 분석하였습니다. 이러한 문제를 해결하는 과정은 알고리즘 인터뷰의 좋은 연습이 될 수 있습니다. 코딩테스트 준비를 위해 다양한 문제를 풀어보는 것을 권장합니다.
다음 강좌에서는 다른 알고리즘 문제를 다루어 보겠습니다. 많은 관심 부탁드립니다!