-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathLIS_DP.java
More file actions
99 lines (80 loc) · 4.52 KB
/
Copy pathLIS_DP.java
File metadata and controls
99 lines (80 loc) · 4.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//############################################################
// | cafe | http://cafe.naver.com/dremdelover |
// | Q&A | https://open.kakao.com/o/gX0WnTCf |
// | business | ultrasuperrok@gmail.com |
//############################################################
// 1. 개념:
// Longest Increasing Subsequence (LIS)는 주어진 숫자 배열에서 증가하는 부분 수열 중 가장 긴 것을 찾는 문제입니다.
// 예를 들어, [10, 22, 9, 33, 21, 50, 41, 60, 80]의 LIS는 [10, 22, 33, 50, 60, 80]입니다.
// 2. 입력과 출력:
// 입력: 숫자 배열 arr[]
// 출력: LIS의 길이
// 3. 시간 복잡도:
// 이 알고리즘의 시간 복잡도는 O(n^2)입니다.
// 이는 각 원소에 대해 이전의 모든 원소를 확인하여 LIS를 계산하기 때문입니다.
// 4. 문제 예시:
// - 수열 정렬: 주어진 수열을 가장 적은 수의 원소를 제거하여 오름차순으로 만드는 문제입니다.
// - 최장 경로 찾기: 그래프에서 가장 긴 경로를 찾는 문제에서도 LIS를 응용할 수 있습니다.
/*
1. 초기화:
- `lis[]` 배열을 생성하고, 모든 원소를 1로 초기화합니다. 이 배열은 `lis[i]`가 `arr[i]`를 마지막 원소로 가지는 LIS의 길이를 저장합니다.
- `arr[] = [10, 22, 9, 33, 21]`
- `lis[] = [1, 1, 1, 1, 1]`
2. LIS 길이 계산:
- arr[1] (22)을 처리하는 과정:
- 현재 원소는 22입니다. 이전 원소와 비교하여 현재 원소보다 작은 원소가 있는지 확인합니다. 이전 원소는 10입니다.
- 현재 원소(22)보다 이전 원소(10)가 작기 때문에, 이전 원소(10)의 LIS 길이에 1을 더한 값(1+1=2)을 현재 원소의 LIS 길이 후보로 고려합니다.
- `lis[1]`을 2로 업데이트합니다.
- `lis[] = [1, 2, 1, 1, 1]`
- arr[2] (9)을 처리하는 과정:
- 현재 원소는 9입니다. 이전 원소와 비교하여 현재 원소보다 작은 원소가 있는지 확인합니다. 이전 원소는 22입니다.
- 현재 원소(9)보다 이전 원소(22)가 크기 때문에, 현재 원소(9)는 자체적으로 길이 1짜리 LIS가 됩니다.
- `lis[2]`는 1로 유지됩니다.
- `lis[] = [1, 2, 1, 1, 1]`
- arr[3] (33)을 처리하는 과정:
- 현재 원소는 33입니다. 이전 원소와 비교하여 현재 원소보다 작은 원소가 있는지 확인합니다. 이전 원소는 9, 22, 10입니다.
- 현재 원소(33)보다 작은 원소가 있는 경우, 그 중 가장 큰 LIS 길이를 찾아서 현재 원소의 LIS 길이 후보로 고려합니다.
- 이전 원소(22)의 LIS 길이는 2이고, 이것이 현재 원소(33)의 LIS 길이 후보가 됩니다.
- `lis[3]`을 2로 업데이트합니다.
- `lis[] = [1, 2, 1, 2, 1]`
- arr[4] (21)을 처리하는 과정:
- 현재 원소는 21입니다. 이전 원소와 비교하여 현재 원소보다 작은 원소가 있는지 확인합니다. 이전 원소는 9, 22, 10, 33입니다.
- 현재 원소(21)보다 작은 원소가 있는 경우, 그 중 가장 큰 LIS 길이를 찾아서 현재 원소의 LIS 길이 후보로 고려합니다.
- 이전 원소(22)의 LIS 길이는 2이고, 이것이 현재 원소(21)의 LIS 길이 후보가 됩니다.
- `lis[4]`을 2로 업데이트합니다.
- `lis[] = [1, 2, 1, 2, 2]`
3. 최종 결과:
- 이 과정을 모든 원소에 대해 반복하면, `lis[]` 배열에는 각 원소를 마지막으로 하는 LIS의 길이가 저장됩니다.
- `arr[] = [10, 22, 9, 33, 21]`
- 최종 `lis[] = [1, 2, 1, 2, 2]` (각 원소를 마지막으로 하는 LIS의 길이가 계산됨)
*/
public class LIS {
public static void main(String[] args) {
int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
System.out.println("Length of LIS: " + lis(arr));
}
static int lis(int[] arr) {
int n = arr.length;
int[] lis = new int[n];
int i, j, max = 0;
// lis[i]는 arr[i]를 마지막으로 하는 LIS의 길이를 저장합니다.
for (i = 0; i < n; i++) {
lis[i] = 1;
}
// 동적 프로그래밍을 사용하여 LIS를 계산합니다.
for (i = 1; i < n; i++) {
for (j = 0; j < i; j++) {
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}
// lis[] 배열에서 가장 큰 값을 찾아 LIS의 길이를 결정합니다.
for (i = 0; i < n; i++) {
if (max < lis[i]) {
max = lis[i];
}
}
return max;
}
}