이번 주에는 이분 탐색에 대한 알고리즘 문제를 풀었습니다.
📌 가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열2는 지난 주에 다이나믹 프로그래밍(DP, Dynamic Programming) 알고리즘 문제를 풀 때, 풀었던 문제의 종류 중 하나입니다.
지난 주에 풀었던 문제와 정말 똑같지만 다른 점은 주어지는 수열의 크기가 1,000,000으로 훨씬 광범위해졌습니다.
이를, DP로 풀게되면 분명히 시간 초과가 날 것입니다.
그래서 이분 탐색을 이용하여 풀어야 합니다.
일단, 먼저 코드를 보겠습니다.
...
// 수열의 크기
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
// 수열 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 부분 수열들을 저장할 배열
int[] seq = new int[n];
seq[0] = arr[0];
// 수열의 길이
int length = 1;
for(int i=1; i<n; i++){
int value = arr[i];
// 부분 수열의 가장 마지막 값보다 크다면
if(seq[length-1] < value){
length++;
seq[length-1] = value;
} else {
// 이분 탐색
int low = 0;
int high = length;
while(low < high){
int mid = (low+high) / 2;
// seq의 중간 값보다 크다면
if(seq[mid] < value){
low = mid + 1;
} else {
high = mid;
}
}
// low 인덱스가 바꿀 원소의 위치가 되어 value 값으로 바꿔준다.
seq[low] = value;
}
}
bw.write(length+"");
...seq 배열에는 부분 수열들을 저장합니다.
그래서, 첫 인덱스에 입력받은 수열의 첫 번째 값을 저장합니다.
이제, for문을 통해 수열의 값들을 하나씩 seq 배열 마지막에 저장된 값과 비교하며, 배열 마지막 값보다 크면 길이를 하나 증가시키고 배열 마지막에 그 값을 추가합니다.
중요한 부분은 else 부분인데, 이 부분에서 이분 탐색이 사용됩니다.
else부분의 코드를 설명하기에 앞서 문제에서 원하는 가장 긴 증가하는 부분 수열의 길이를 구하기 위해 생각해야될 점은 무엇일까요?
값들을 최대한 많이 배치하기 위해 값들 사이의 차이가 적어야 합니다.
그러면 값들 사이의 차이가 적게 최대한 많이 배치하기 위해 어떤 식으로 생각해야 될까요?
그것은 수열의 큰 값을 좀 더 작은 값으로 대체하는 것입니다. arr 배열에 저장된 값을 이분 탐색을 통해 seq 배열에 있는 값보다 큰 값을 찾는데, 가장 근접한 값을 찾습니다. 그냥 자기자신보다 크지만 차이가 적은 값을 탐색하는 것입니다.
그래서 이를 위해 이분 탐색을 이용하는 것이며, 절반씩 좁혀가면서 가장 근접한 큰 값을 찾아 대체합니다.
그렇게 하면서 가장 긴 증가하는 부분 수열의 길이를 나타내는length를 출력합니다.
