💡문제
💡풀이
접근법 : 방법을 생각해내면 쉬운 LIS 문제이다.
아이들을 최소로 옮기기 위해서는 가장 많은 아이들을 고정시켜두면 된다.
즉, 3 7 5 2 6 1 4 에서 LIS인 3 5 6 인 아이들은 그대로 두고 나머지 아이만 옮기면 최소로 옮길 수 있다.
LIS를 푸는 방법은 두 가지가 있다. DP로 풀거나, 이분탐색으로 풀거나.
간단한 LIS 문제를 만난김에 두 가지 방법으로 풀어보았다.
DP로 풀기
DP로 LIS 문제를 풀 때에는 보통 이중 for문을 돌린다. 나보다 이전 수들이 증가되고 있는지 모두 확인해야하기 때문이다.
int max = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1; // 다시 구하기 위해 초기화 해준다.
for (int j = 0; j < i; j++) { // 자기 앞까지의 숫자들을 모두 비교해서 자신을 구한다.
if(child[i] > child[j]){ // 앞 수가 나보다 작으면
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}이분탐색으로 풀기
이분탐색으로 풀기 위해서는 접근 방식의 이해가 조금 필요하다.
방금 전 dp로 풀기 위해서는 나보다 작은 값들과 내 값을 모두 비교해야만 했다.
이분탐색으로 풀 때에는 lis 배열을 하나 생성한 뒤에
-
배열의 마지막 값보다 큰 값이 들어오면 배열에 추가하고
-
작은 값이 들어오면 이분탐색을 통해 배열의 적절한 위치에 넣고 기존 값을 대체한다.
<예시>
1 6 2 5 7 3 5 6 의 수열이 들어온다고 생각해보자
lis배열은 처음엔 1을 그대로 가진다.
LIS 배열: [1]
다음으로 6이 들어오면 1보다 크므로 뒤에 추가한다.
LIS 배열: [1, 6]
2가 들어오면 6보다 작으므로 이분탐색을 통해서 들어가야할 인덱스를 찾아서 대체한다.
LIS 배열: [1, 2]
5가 들어오면
LIS 배열: [1, 2, 5]
7이 들어오면
LIS 배열: [1, 2, 5, 7]
3이 들어오면 7보다 작으므로 인덱스를 찾아 대체한다.
LIS 배열: [1, 2, 3, 7]
5가 들어오면 7보다 작으므로 인덱스를 찾아 대체한다.
LIS 배열: [1, 2, 3, 5]
6이 들어오면
LIS 배열: [1, 2, 3, 5, 6]
따라서 최종적으로 LIS의 길이는 5이다!
주의할 점
예시에서는 1,2,3,5,6 이 나왔지만 실제로는 이 방식으로 계산한 LIS 배열이 항상 실제 LIS와 일치하지는 않는다.
이 방식은 길이는 정확하게 구하지만, 최적의 LIS를 구하지는 못한다.
int lis = 0;
for (int i = 0; i < n; i++) {
if(lis == 0 || child[i] > lisArr[lis-1]){ // 큰 값이 들어올 경우
lisArr[lis] = child[i]; // 배열에 넣기
lis++; // LIS 길이 증가
} else{
int idx = binarySearch(0, lis, child[i]);
lisArr[idx] = child[i]; // 값 대체
}
}
- int lis는 LIS의 길이를 나타내는 값이다.
- lis배열의 마지막값보다 큰 값이 들어오면 배열에 그대로 넣고, lis++
- 작은 값이 들어오면 이분탐색을 통해 인덱스를 구하고 값을 대체한다.
💡내 코드
1. DP로 풀기 O(n^2)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] child = new int[n];
int [] dp = new int[n+1];
for (int i = 0; i < n; i++) {
child[i] = Integer.parseInt(br.readLine());
}
dp[0] = 1;
int max = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1; // 다시 구하기 위해 초기화 해준다.
for (int j = 0; j < i; j++) { // 자기 앞까지의 숫자들을 모두 비교해서 자신을 구한다.
if(child[i] > child[j]){ // 앞 수가 나보다 작으면 +1
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(n-max);
}
}
2. 이분탐색으로 풀기 O(nlogn)
import java.io.*;
public class Main {
static int [] lisArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] child = new int[n];
lisArr = new int[n];
for (int i = 0; i < n; i++) {
child[i] = Integer.parseInt(br.readLine());
}
int lis = 0;
for (int i = 0; i < n; i++) {
if(lis == 0 || child[i] > lisArr[lis-1]){
lisArr[lis] = child[i];
lis++;
} else{
int idx = binarySearch(0, lis, child[i]);
lisArr[idx] = child[i];
}
}
System.out.println(n-lis);
}
static int binarySearch(int left, int right, int target){
while(left < right){
int mid = (left+right)/2;
if(lisArr[mid] <target){
left = mid + 1 ;
} else{
right = mid;
}
}
return right;
}
}