LIS 알고리즘 - O(N^2)
i 를 인덱스 1부터 시작하고,
그 때 j를 0부터 i-1 까지 보면서 최장증가수열을 구하는 알고리즘이다.
dp[i] 값을 구하기 위해 이전(0...i-1) 배열값을 모두 다 보아야만 하기 때문에 N^2 의 시간이 걸린다.
# 초기값
dp 배열은 1로 초기화
i는 index 1부터 시작해서 N-1까지 진행하고, 그 때마다 j 는 0…i-1 만큼 반복한다.
| |
j |
i |
|
|
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
1 |
1 |
1 |
1 |
1 |
# i = 1
1. j = 0
arr 값을 체크해서 arr[j] < arr[i] 이면, 증가 추세이므로 dp[i] = dp[j] + 1 해준다.
| |
j |
i |
|
|
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
1 |
1 |
1 |
# i = 2
1. j = 0
arr[j] < arr[i] 을 만족하지 않으므로, PASS (아무 작업도 하지 않는다)
| |
j |
|
i |
|
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
1 |
1 |
1 |
2. j = 1
arr[j] < arr[i] 을 만족하지 않으므로, PASS
| |
|
j |
i |
|
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
1 |
1 |
1 |
# i = 3
1. j = 0
arr[j] < arr[i] 이므로, dp[i] = dp[j] + 1 해준다.
| |
j |
|
|
i |
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
2 |
1 |
1 |
2. j = 1
arr[j] < arr[i] 이므로, dp[i] = dp[j] + 1 해준다.
| |
|
j |
|
i |
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
1 |
1 |
3. j = 2
arr[j] < arr[i] 을 만족하긴 하지만 현재 dp[i]값(= 3)이 dp[j]+1 값(=2)보다 더 크므로 PASS
| |
|
|
j |
i |
|
|
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
1 |
1 |
… 생략 ….
# i = 5
1. j = 0
arr[j] < arr[i] 이므로, dp[i] = dp[j] + 1 해준다.
| |
j |
|
|
|
|
i |
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
2 |
2 |
2. j = 1
arr[j] < arr[i] 이므로, dp[i] = dp[j] + 1 해준다.
| |
|
j |
|
|
|
i |
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
2 |
3 |
3. j = 2
arr[j] < arr[i] 을 만족하긴 하지만 현재 dp[i]값이 dp[j]+1보다 더 크므로 PASS
| |
|
|
j |
|
|
i |
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
2 |
3 |
4. j = 3
arr[j] < arr[i] 이므로, dp[i] = dp[j] + 1 해준다.
| |
|
|
|
j |
|
i |
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
2 |
4 |
5. j = 4
arr[j] < arr[i] 을 만족하긴 하지만 현재 dp[i]값이 dp[j]+1보다 더 크므로 PASS
| |
|
|
|
|
j |
i |
| arr[] |
10 |
20 |
10 |
30 |
20 |
50 |
| dp[] |
1 |
2 |
1 |
3 |
2 |
4 |
마무리
알고리즘이 다 끝났고, 현재 dp 배열에 제일 큰 값( 마지막 값이 아닌, 제일 큰 값!!)을 출력하면 최장 증가 수열의 길이가 구해진다.
소스 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ11053 {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
/* INPUT */
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());
}
/* LIS */
int dp[] = new int[N];
Arrays.fill(dp, 1);
int maxLength = 1;
for(int i=1; i<N; i++) {
for(int j=0; j<i; j++) {
if( arr[j] < arr[i] ) {
dp[i] = Math.max(dp[i], dp[j] + 1);
maxLength = Math.max(maxLength, dp[i]);
}
}
}
System.out.println(maxLength);
}
}
댓글