HS_development_log

가장 큰 증가하는 부분 수열(LIS) 본문

Algorithm-이론

가장 큰 증가하는 부분 수열(LIS)

DevHyeonseong 2020. 1. 17. 17:46
반응형

가장 큰 증가하는 부분 수열을 구하는 알고리즘이다.

 

예를들어

 

10 30 50 40 20 이라는 배열이있을때 

 

10 30 50 이 가장큰 증가하는 부분수열이며 길이는 3이다

 

길이를 구하는 알고리즘과 요소까지 다구하는 알고리즘은 차이가 좀 있는데 2개다 밑에 설명할 것이다.

 

 

 

1. LIS의 길이

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
import java.util.*;
public class LIS_length
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++)
        {
            array[i] = scan.nextInt();
        }
        
        int[] ans = new int[n];
        int idx = 0;
        ans[0] = array[0];
        
        for(int i=1;i<n;i++)
        {
            if(ans[idx]<array[i])
            {
                idx++;
                ans[idx] = array[i];
            }
            else
            {
                int start = 0;
                int end = idx;
                int mid;
                while(end>start)
                {
                    mid = (start+end) /2;
                    if(ans[mid] < array[i])
                    {
                        start = mid+1;
                    }
                    else
                    {
                        end = mid;
                    }
                }
                ans[end] = array[i];
            }
        }
        System.out.println(idx+1);
    }
}
 
 cs

Lower bound라는 방식으로 길이를 구하는 알고리즘이다. 시간복잡도는 O(NlogN).

배열을 구성하는 요소는 LIS의 구성요소가 아니다 길이만 같을뿐.

 

2. LIS 요소

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
import java.util.*;
public class LIS_element_reversetrace 
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++)
        {
            array[i] = scan.nextInt();
        }
        
        int[] lisLen = new int[n]; // 최장증가수열의 길이를 담는배열
        int idx = 0;
        lisLen[0] = array[0]; 
        
        int[][] lis = new int[n][2]; // 요소 역추적 배열
        lis[0][0] = 0;
        lis[0][1] = array[0];
        // 길이구하기
        for(int i=1;i<n;i++)
        {
            if(lisLen[idx]<array[i])
            {
                idx++;
                lisLen[idx] = array[i];
                lis[i][0] = idx;
                lis[i][1] = array[i];
            }
            else
            {
                int start = 0;
                int end = idx;
                int mid;
                while(end>start)
                {
                    mid = (start+end) /2;
                    if(lisLen[mid] < array[i])
                    {
                        start = mid+1;
                    }
                    else
                    {
                        end = mid;
                    }
                }
                lisLen[end] = array[i];
                lis[i][0] = end;
                lis[i][1] = array[i];
            }
        }
        // 역추적 시작
        int max = Integer.MIN_VALUE;
        int maxidx = 0;
        for(int i=0;i<lis.length;i++) // 길이가 가장길때의 요소 구하기
        {
            if(max<lis[i][0])
            {
                max = lis[i][0];
                maxidx = i;
            }
        }
        //역추적
        Stack<Integer> ans = new Stack<Integer>();
        ans.push(lis[maxidx][1]);
        for(int i=maxidx;i>=0;i--)
        {
            if(lis[i][0]==max-1)
            {
                max = lis[i][0];
                ans.push(lis[i][1]);
            }
        }
        while(!ans.isEmpty())
        {
            System.out.print(ans.pop()+" ");
        }
 
    }
}
 
 
 cs

길이를 먼저구하고, 길이를 구하면서 요소들을 저장한것으로 역추적을 하는 알고리즘이다.

 

반응형

'Algorithm-이론' 카테고리의 다른 글

알고리즘 실용 - Wrapper 클래스 메서드 활용  (0) 2020.08.12
자바 Collections 라이브러리의 시간 복잡도  (0) 2020.02.01
알고리즘 - 수학  (0) 2020.01.15
세그먼트 트리(Segment Tree) / Java  (0) 2020.01.13
트리(Tree) / Java  (0) 2020.01.13
'Algorithm-이론' Related Articles more