[BOJ/백준] 가장 긴 증가하는 부분 수열(LIS) 시리즈 (Java)
문제 정리
| 문제 링크 | 티어 | 시간복잡도 | 알고리즘 |
| 가장 긴 증가하는 부분 수열 | 실버 2 | O(n^2) | DP |
| 가장 긴 증가하는 부분 수열 2 | 골드 2 | O(nlogn) | 이분탐색 |
| 가장 긴 증가하는 부분 수열 3 | 골드 2 | O(nlogn) | 이분탐색 |
| 가장 긴 증가하는 부분 수열 4 | 골드 4 | O(n^2) | DP + 부분 수열 구하기 |
| 가장 긴 증가하는 부분 수열 5 | 플래 5 | O(nlogn) | 이분탐 + 부분 수열 구하기 |
가장 긴 증가하는 부분 수열 : DP / O(n^2)
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
n이 1000까지 이기 때문에 O(n2) 의 시간복잡도로 풀어도 괜찮은 문제이다.
- dp 배열의 모든 값을 1로 초기화
- 현재 위치 i 보다 이전에 있는 원소 j가 작은지 확인 ( j < i )
- 원소 j 가 원소 i 보다 작다면, dp[i] 값과 dp[j]에서 1 더한값을 비교해 더 큰값으로 변경
- dp 배열의 최댓값 출력
수열 A가 주어졌을 때,
| 10 | 20 | 10 | 30 | 20 | 50 |
i = 2 까지의 dp 배열은 다음과 같다.
| 1 | 2 | 1 (여기까지 구함) | 1 | 1 | 1 |
이제 30 (i = 3)과 그 전 원소들을 비교할것이다.
j = 0, 10 < 30 이고, 1 < 1 + 1 이므로 dp[3]은 2가 된다.
j = 1, 20 < 30 이고, 2 < 2 + 1 이므로 dp[3]은 3이 된다.
j = 2, 10 < 30 이고, 3 > 1 + 1 이므로 dp[3]은 바뀌지 않는다.
이 과정을 반복하면 주어진 예제에서 완성된 dp 배열은 다음과 같다.
| 1 | 2 | 1 | 3 | 2 | 4 |
따라서 답은 4이다.
소스코드
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[] nums = new int[n];
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
System.out.println(res);
}
}
가장 긴 증가하는 부분 수열 2, 3 : 이분탐색 / O(nlogn)
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
12738번: 가장 긴 증가하는 부분 수열 3
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
n이 1 ≤ N ≤ 1,000,000 / 1 ≤ N ≤ 1,000,000 으로, 두 문제 다 DP로 O(n2) 풀이로 푼다면 시간초과가 날 것이다.
DP 풀이에선 i보다 앞에있는 모든 j에 대해 검토했었다. 하지만 굳이 모든 수를 볼 필요가 있을까?
가장 긴 LIS를 구하기 위해선, 원소들 간의 차이가 작을수록 긴 LIS를 구할수 있다.
다음과 같이 배열 A가 주어진다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A[i] | 10 | 20 | 40 | 25 | 20 | 50 | 30 | 70 | 85 |
LIS는 10, 20, 40, 50, 70, 85로 길이 6인 배열이 될 것이다.
Binarysearch를 이용해 O(nlogn)의 시간복잡도로 LIS의 길이를 구하는 방법은 다음과 같다:
- 임의의 배열 L을 생성한다. size는 0이다.
- i=0 부터 순회하며 L의 가장 마지막 원소보다 A[i]가 더 클 경우 L의 맨 뒤에 A[i]를 추가하고 size를 1 증가시킨다.
- L의 가장 마지막 원소보다 A[i]가 더 작을 경우 Binarysearch로 A[i]가 오름차순을 유지하면서, 들어갈 자리를 찾고 그 자리의 값을 A[i]의 값으로 대체한다. size는 그대로 유지한다.
- L 배열의 길이이자 size의 값이 답이 된다.
LIS를 구하기 위해, 임의의 배열 L을 만든다. 초기 L은 비어있으므로, 10을 넣어준다. (size = 1)
i = 1일때, 20은 10보다 크므로 20을 끝에 추가한다. (size = 2)
i = 2일때, 40은 20보다 크므로 끝에 40을 추가한다. (size = 3)
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| L[i] | 10 | 20 | 40 |
i = 3일때, 25는 20보단 크고 40보다는 작다. 40을 25로 대체한다.
만약 바로 뒤에 30이 오고, 40을 25로 대체하지 않았다면 LIS배열에 30을 추가하지 못해 LIS를 구하지 못했을 것이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| L[i] | 10 | 20 | 25 |
이 과정을 반복해 나가면 결과는 이렇게 된다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| L[i] | 10 | 20 | 25 | 30 | 70 | 85 |
LIS의 길이는 6으로, 답은 6이다.
하지만 여기서 주목해야 할 것이, L배열이 실제 LIS와 다를 수 있다는 것이다.
수열상에 뒤에 있던 원소가 먼저 들어온 원소보다 이분 탐색으로 된 최적의 위치가 앞에 있을 수 있기 때문이다.
실제 LIS배열을 구하는 것은 뒤의 다른 문제에서 한다.
Binarysearch 알고리즘을 직접 구할 순 있지만 자바에서는 Arrays.binarySearch() 로 구할 수 있다.
찾고자 하는 원소가 배열에 있을 경우엔 해당 원소의 위치 인덱스를 반환하고,
찾고자 하는 원소가 배열에 없을 경우엔 key보다 greater한 최초의 위치 * (-1) -1 값을 리턴한다.
우리가 찾고자 하는것은 key보다 greater한 최초의 위치이기 때문에
Arrays.binarySearch로 찾은 인덱스가 0보다 작을 경우 -1을 곱하고, -1을 빼주어 인덱스를 구한다.
만약 그게 가장 끝 위치일 경우 size를 늘려준다.
소스코드
public class Main {
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int[] list = new int[n];
int size = 0;
for (int i = 0; i < n; i++) {
int idx = Arrays.binarySearch(list, 0, size, nums[i]);
if (idx < 0) idx = idx * (-1) - 1;
list[idx] = nums[i];
if (idx == size) size++; // 끝에 들어갔을 경우
}
System.out.println(size);
}
}
가장 긴 증가하는 부분 수열 4 : DP + 추적 / O(n^2)
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
11053 문제에서 실제 부분 수열까지 출력하는 문제이다.
dp 배열 말고도, memo라는 배열을 하나 더 만든다.
dp[i]가 초기화 될 때, dp[i]가 어디로부터 온 원소인지 메모를 한다.
그렇게 하면 이런 결과가 나온다.
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| A[i] | 10 | 20 | 10 | 30 | 20 | 50 |
| dp[i] | 1 | 2 | 1 | 3 | 2 | 4 |
| memo[i] | 0 | 0 | 0 | 1 | 0 | 3 |
LIS는 4이고, dp[i]가 4일때 인덱스는 5이다. max_idx = 5, max_int는 4이다.
i = 3일때, 결과 배열에 A[max_idx] = A[5]인 50을 추가한다. memo[5]가 3이므로, max_idx가 3이 된다.
i = 2일때, 결과 배열에 A[max_idx] = A[3]인 30을 추가한다. memo[3]이 1이므로, max_idx가 1이 된다.
i = 1일때, 결과 배열에 A[max_idx] = A[1]인 20을 추가한다. memo[1]이 0이므로, max_idx가 0이 된다.
i = 0일때, 결과 배열에 A[max_idx] = A[0]인 10을 추가한다.
그럼 결과 배열이 50, 30, 20, 10이 되고 이를 거꾸로 출력하면 그게 답이다.
소스코드
public class Main {
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] nums = new int[n];
int[] dp = new int[n];
int[] memo = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
dp[i] = 1;
}
int max_idx = 0;
int max_val = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
memo[i] = j; // i는 j로부터 옴
}
}
if (dp[i] > max_val) {
max_val = dp[i];
max_idx = i;
}
}
int[] res = new int[max_val];
for (int i = max_val - 1; i >= 0; i--) {
res[i] = nums[max_idx];
max_idx = memo[max_idx];
}
System.out.println(max_val);
for (int i = 0; i < max_val; i++) {
System.out.print(res[i] + " ");
}
}
}
가장 긴 증가하는 부분 수열 5 : 이분탐색 + 추적 / O(nlogn)
14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
무려 플레문제다. 2,3번에 실제 LIS를 구하는 로직을 추가하면 된다.
4번 문제와 똑같이 memo라는 배열을 추가하고, 어디로부터 온 원소인지 메모를 한다. 그럼 결과가 이렇게 된다.
아래 표에서 L이 이분탐색으로 구한 임시 lis 배열이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| A[i] | 10 | 20 | 10 | 30 | 20 | 50 |
| L[i] | 10 | 20 | 30 | 50 | 0 | 0 |
| memo[i] | 0 | 1 | 0 | 2 | 1 | 3 |
idx = 3으로 출발해, 하나씩 줄여가면서 어느 원소로부터 L[i]가 만들어졌는지 구하면 된다.
소스코드
public class Main {
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] nums = new int[n];
int[] lis = new int[n];
int[] memo = new int[n];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int size = 0;
for (int i = 0; i < n; i++) {
int idx = Arrays.binarySearch(lis, 0, size, nums[i]);
if (idx < 0) idx = idx * (-1) - 1;
memo[i] = idx;
lis[idx] = nums[i];
if (idx == size) size++;
}
int idx = size - 1;
int[] answer = new int[size];
for (int i = n - 1; i >= 0; i--) {
if (memo[i] == idx) {
answer[idx--] = nums[i];
}
}
sb.append(size).append("\n");
for (int i = 0; i < size; i++) {
sb.append(answer[i]).append(" ");
}
System.out.println(sb);
}
}