안녕하세요! 오늘은 자바 코딩 테스트에서 자주 출제되는 문제 중 하나인 ‘가장 길게 증가하는 부분 수열(LIS: Longest Increasing Subsequence)’ 찾기 문제를 다루어보려 합니다. 이 문제는 주어진 수열에서 선택된 원소들의 값이 증가하는 가장 긴 부분 수열의 길이를 찾는 것입니다. 복잡한 알고리즘 문제처럼 보일 수 있지만, 효율적인 접근 방법을 통해 해결할 수 있으며, 이를 통해 코딩 테스트에서 점수를 향상시킬 수 있습니다.
문제 설명
주어진 정수 배열이 있습니다. 이 배열에서 가장 길게 증가하는 부분 수열을 찾아 그 길이를 반환하는 프로그램을 작성하세요. 예를 들어:
입력: [10, 9, 2, 5, 3, 7, 101, 18]
출력: 4
설명: 증가하는 부분 수열은 [2, 3, 7, 101]로 길이가 4입니다.문제 해결 방법
이 문제를 해결하기 위해 여러 가지 접근 방식을 사용할 수 있습니다. 가장 직관적인 방법 중 하나는 동적 프로그래밍(Dynamic Programming) 기법을 사용하는 것입니다. 이 방법을 사용하면 O(n^2)의 시간복잡도로 문제를 해결할 수 있습니다. 또한, 이 문제를 더욱 최적화하면 O(n log n) 시간복잡도로도 해결할 수 있습니다. 이번 글에서는 두 가지 방법을 모두 다루어보겠습니다.
1. 동적 프로그래밍을 사용한 방법
먼저, 동적 프로그래밍을 사용하여 이 문제를 해결하는 방법을 살펴보겠습니다. 이 방법은 다음과 같은 절차로 진행됩니다:
- 길이를 n인 배열이 주어질 때, n 크기의 DP 배열을 생성합니다. DP 배열의 각 원소는 해당 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장합니다.
- DP 배열의 초기값으로 모두 1을 설정합니다. (각 원소는 최소한 자기 자신으로만 구성된 부분 수열을 가질 수 있기 때문입니다.)
- 이중 루프를 이용하여 각 원소를 확인하고, 이전 원소들과 비교하여 증가하는 부분 수열의 길이를 업데이트합니다.
- 최종적으로 DP 배열에서 가장 큰 값을 반환합니다.
이제 이를 자바로 구현해 봅시다.
public class LongestIncreasingSubsequence {
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
// 모든 수열의 길이를 1로 초기화
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// DP 배열에서 최대값 찾기
int maxLength = 0;
for (int length : dp) {
maxLength = Math.max(maxLength, length);
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("가장 길게 증가하는 부분 수열의 길이: " + lengthOfLIS(nums));
}
}코드 분석
위의 코드는 다음과 같은 단계로 진행됩니다:
- 주어진 배열이 null이거나 길이가 0이면 0을 반환합니다.
- DP 배열을 초기화하여 모든 값이 1이 되도록 설정합니다.
- 이중 루프를 통해 각 원소를 비교하여 증가하는 부분 수열의 길이를 업데이트합니다.
- 최종적으로 DP 배열에서 가장 긴 수열의 길이를 찾아 반환합니다.
2. O(n log n) 방법
다음으로, O(n log n) 방법을 살펴보겠습니다. 이 방법은 이진 탐색(Binary Search)을 통해 보다 효율적으로 문제를 해결할 수 있습니다. 이 알고리즘은 다음과 같은 절차를 따릅니다:
- 비어있는 리스트를 생성합니다.
- 입력 배열의 각 요소를 순회합니다. 리스트의 마지막 원소보다 큰 경우, 해당 원소를 리스트에 추가합니다.
- 리스트의 마지막 원소보다 작거나 같은 경우, 이진 탐색을 통해 리스트에서 해당 원소가 들어갈 위치를 찾은 후 그 위치의 원소를 대체합니다.
- 리스트의 길이가 결국 가장 길게 증가하는 부분 수열의 길이가 됩니다.
이제 이를 자바로 구현해 보겠습니다.
import java.util.ArrayList;
import java.util.List;
public class LongestIncreasingSubsequenceBinarySearch {
public static int lengthOfLIS(int[] nums) {
List lis = new ArrayList<>();
for (int num : nums) {
int index = binarySearch(lis, num);
if (index == lis.size()) {
lis.add(num);
} else {
lis.set(index, num);
}
}
return lis.size();
}
private static int binarySearch(List lis, int num) {
int left = 0, right = lis.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (lis.get(mid) < num) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("가장 길게 증가하는 부분 수열의 길이: " + lengthOfLIS(nums));
}
} 코드 분석
위의 코드 분석은 다음과 같습니다:
- 빈 리스트를 생성하여 가장 길게 증가하는 부분 수열을 저장합니다.
- 각 원소를 순회하며 이진 탐색을 통해 들어갈 위치를 찾습니다.
- 리스트의 마지막 원소보다 작은 경우 해당 위치의 원소를 대체합니다.
- 최종적으로 리스트의 길이를 반환하여 가장 길게 증가하는 부분 수열의 길이를 제공합니다.
결론
오늘은 자바를 사용하여 ‘가장 길게 증가하는 부분 수열’ 문제를 해결하는 두 가지 방법을 알아보았습니다. 동적 프로그래밍을 사용한 O(n^2) 방법과 이진 탐색을 활용한 O(n log n) 방법을 통해 문제를 해결할 수 있었습니다. 이 두 가지 접근법을 통해 코딩 테스트에서 유용하게 활용할 수 있을 것입니다.
여러분이 취업 준비와 코딩 테스트 준비에 도움이 되길 바랍니다. 감사합니다!