[백준] 가장 긴 증가하는 부분 수열 시리즈 - 자바

주재완·2024년 1월 21일
dynamic programming백준이분 탐색
0

백준

목록 보기
4/8
post-thumbnail

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

영어로는 LIS(Longest Increasing Subsequence)라고도 하는 가장 긴 증가하는 부분 수열은 유명한 문제기도 하고 DP(Dynamic Programing)과 이분 탐색 알고리즘을 공부하는데 아주 좋은 문제기에 시리즈로 묶어서 소개하게 되었습니다.

우선 LIS가 무엇인지 아래를 보시면 바로 이해가 되실 것 입니다.

수열 A = {10, 20, 100, 30, 2, 5, 50} 에서 LIS는 {10, 20, 30, 50} 이고 길이는 4 이다.

말 그대로 증가 수열을 찾는 것이고, 동일한 값은 제외합니다.

해결 방법?

크게 두가지 방법으로 해결할 수 있습니다. 바로 DP를 쓰는 법과 이분 탐색입니다. DP를 사용시 시간 복잡도는 O(N^2) 이고, 조금 더 어려운 방법으로 이분 탐색을 사용시 O(NlogN) 으로 해결이 가능합니다. 백준에서 해당되는 시리즈들을 풀이 하겠습니다.

With Dynamic Programming

백준 11053 (Silver 2)

가장 긴 증가하는 부분 수열

해당 문제는 가장 기본적인 LIS 문제입니다. 수열의 길이만 구하는 문제이고, 수열 길이가 1000까지이기에 O(N^2) 정도로 풀어도 시간초과하지는 않습니다.

접근 방법

아래와 같은 배열을 하나 생각합니다. 그리고 dp라는 배열도 만들어서 과정마다 진행상황을 저장할수 있게 합니다.

index0123456
array10  20  10030  2    5    50  
dp0000000

dp[i]는 index i의 원소를 포함하고, 그 단계까지의 LIS의 길이를 말합니다. 이 때 다음과 같은 과정을 반복하면 dp[i]를 구할 수 있습니다.

  1. 우선 자기 자신만 있는게 최소 길이이므로 dp[i]에 1을 넣는다.
  2. 자기 자신보다 앞에 있는 원소들을 살펴본다. 이 때,
    • array[j] < array[i](자기 자신) 일 경우 전까지 수행했던 LIS 길이에 자기자신 하나가 추가된 길이와 현재 가지고 있는 LIS 길이와 비교한다. 즉 max(dp[j] + 1, dp[i])를 수행한다.
    • 나머지의 경우 애초에 증가수열 조건을 만족하지 않으므로 그냥 지나간다.
  3. 이를 계속 반복하고 마지면 dp의 최댓값을 구하면 답이 나온다.

해당 과정을 진행하면 대략 1 x 2 + 2 x 2 + ... + N x 2 번 수행되므로 시간 복잡도는 O(N(N + 1)), 즉 O(N^2) 이 됩니다. 각 과정을 수행하면 아래와 같습니다.

  • 첫 번째
index0123456
array10  20  10030  2    5    50  
dp1000000
  • 두 번째
index0123456
array10  20  10030  2    5    50  
dp1200000

...

  • 마지막
index0123456
array10  20  10030  2    5    50  
dp1233124

Java ☕️

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] dp = new int[n];
		int length = 0;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			// arr 현재 요소 받기
			int ele = Integer.parseInt(st.nextToken());
			arr[i] = ele;
			
			// 현재 요소를 받고 dp 시작
			dp[i] = 1;
			for(int j = 0; j < i; j++) {
				if(arr[j] < ele) {
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
			}
			
			length = Math.max(length, dp[i]);
		}
		
		System.out.println(length);
		br.close();
	}
}

실버2 결과

백준 14002 (Gold 4)

가장 긴 증가하는 부분 수열 4
앞에서 살펴보았던 백준 11053과 동일한데, 다만 실제 LIS까지 출력하는 문제입니다. 아마 실제 출력하는 것을 어떻게 해야되는지 처음에 생각하기는 쉽지 않을 수도 있습니다.

접근 방법

전에 사용한 dp를 살펴봅니다.

index0123456
array10  20  10030  2    5    50  
dp1233124

우선 출력을 위해서 반복문이 필요한데, 시작은 최댓값이 있는 index 부터 뒤에서부터 값을 추가해주면 됩니다. 뒤부터 시작하는 이유는 값의 왜곡이 없기 때문이며(사실 예외는 있는데 다른 부분에 비해 가장 적기도 하고 LIS는 아무것이나 출력하면 되기에 문제되지 않음) 이부분만을 자바 코드로 나타내면 아래와 같습니다.

  • max_idx : 최댓값이 있는 index
  • stack : 자바 스택
  • sb : 자바 StringBuilder
...
		for(int i = max_idx; i >= 0; i--) {
			if(length == dp[i]) {
				stack.add(arr[i]);
				length--;
			}
		}
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
		
		System.out.println(sb);
...

Java ☕️

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] dp = new int[n];
		int length = 0;
		int max_idx = 0;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			// arr 현재 요소 받기
			int ele = Integer.parseInt(st.nextToken());
			arr[i] = ele;
			
			// 현재 요소를 받고 dp 시작
			dp[i] = 1;
			for(int j = 0; j < i; j++) {
				if(arr[j] < ele) {
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
			}
			
			// 최댓값, 최대인덱스를 저장한다.
			if(length < dp[i]) {
				length = dp[i];
				max_idx = i;
			}
		}
		
		System.out.println(length);
		
		for(int i = max_idx; i >= 0; i--) {
			if(length == dp[i]) {
				stack.add(arr[i]);
				length--;
			}
		}
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
		
		System.out.println(sb);
		
		br.close();
	}
}

골드 4 결과

With Binary Search

백준 12015 & 백준 12738 (Gold 2)

가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열 3

두 문제는 동일한 문제여서 한 곳에 묶었습니다. 이 두 문제의 경우에는 범위가 1,000,000 이므로 위에 있는 Dynamic Programing으로 풀면 시간 초과가 납니다. 의외로 이분 탐색으로 풀 수 있는 문제로 이를 통해 접근하면 시간 복잡도가 O(NlogN)이 됩니다.

다만, 생각 해내기가 어렵습니다(본인도 이 시리즈 중 가장 시간이 오래 걸렸던 부분입니다.) 그래서 이 방법을 한번 체화하고 나면 알고리즘 능력 향상에 도움이 되지 않을까 합니다.

접근 방법

간단한 수열 {4, 2, 3, 1}을 보도록 합시다.
여기서 새로운 요소들을 저장할 list를 하나 만들어 줍니다.

index0123
array4231
list----

이제부터 리스트에 요소들을 하나씩 넣어줄 예정인데 몇가지 규칙이 있습니다.

  1. 리스트가 비어있으면 그냥 값을 넣습니다.
  2. 비어있지 않다면 이분 탐색을 통해 그 값의 크기에 따른 인덱스를 찾습니다. 예를 들어 1과 5가 들어가 있는 상황에서, 3을 넣는다고 가정할 때, 3의 경우 1보다 크고 5보다 작으므로 인덱스는 5가 있는 위치인 '1'을 찾습니다.
  3. 인덱스를 찾았으면 두 가지 경우가 발생합니다.
    • 기존에 숫자가 없는 인덱스의 경우 그냥 리스트에 add 해줍니다.
    • 기존에 숫자가 있는 인덱스의 경우, 기존값에서 덮어씁니다. 즉 1과 5가 들어가 있는 상황에서 3을 넣는다면 1과 3이 될 것 입니다.
  4. 이를 반복해서 얻은 list의 길이가 바로 LIS의 길이입니다.

그리고 여기서 사용되는 이분 탐색은 lower bound를 사용합니다. 즉 만약 동일한 값들이 여러가지가 있으면 그 값이 시작되는 인덱스를 반환합니다.

차근차근 보도록 하겠습니다.

  • 첫 번째 : 리스트는 비어있으므로 그냥 add 해줍니다.
index0123
array4231
list4---
  • 두 번째 : 2는 4보다 작으므로 4를 2로 대치합니다.
index0123
array4231
list2---
  • 세 번째 : 3이 가장 큰 숫자이므로 이분 탐색의 결과 인덱스(1)에는 숫자가 없습니다 그냥 add 해줍니다.
index0123
array4231
list23--
  • 네 번째 : 이분 탐색 결과 0으로 나옵니다. 기존 값 2를 대치해줍니다.
index0123
array4231
list13--

최종 결과를 보다시피 애초에 리스트가 정렬이 되어서 나오는 것을 알 수 있고, 이분 탐색을 쓰기에 적합한 구조가 됩니다. 따라서 리스트의 길이 2가 LIS의 길이로 나오게 됩니다... 만 주의할 것이 있습니다.

주의사항

list는 LIS 원소들이 아닙니다. 다만 길이만 같은 뿐입니다.
바로 앞 네번째 단계에서 보았지만 실제 LIS 중 {1, 3}이란 것은 없다는 것을 알 수 있습니다. 이렇게 되는 것은 불필요하게 왜곡되는 상황이 생기기 때문입니다. 하지만 이 문제는 길이만 출력하면 되기에 아직은 신경쓸 필요는 없습니다. 그런데 바로 다음 문제에서는 신경을 써줘야 합니다.

Java ☕️

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] arr;
    static List<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        list = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        list.add(arr[0]);
        br.close();
        for (int i = 1; i < n; i++) {
            int ele = arr[i];
            if (list.get(list.size() - 1) < ele) {
                list.add(ele);
            } else {
                int searchedIdx = lowerBound(ele);
                list.set(searchedIdx, ele);
            }
        }

        System.out.println(list.size());
        br.close();
    }

    public static int lowerBound(int target) {
        int start = 0;
        int end = list.size();
        int answer = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (list.get(mid) < target) {
            	start = mid + 1;
            } else {
            	answer = mid;
            	end = mid - 1;
            }
        }
        return answer;
    }
}

골드2 결과

백준 14003 (Platinum 5)

가장 긴 증가하는 부분 수열 5

대망의 플래티넘 문제입니다. 티어만 보고 겁먹지 않도록 합니다.
문제 자체는 기존 이분 탐색에서 실제 LIS를 어떻게 출력하는가만 고민하면 되는 문제입니다. 물론 생각하기 어려울 수 있습니다.

접근 방법

이 문제를 보자마자 이런 생각이 드실껍니다.

어? 백준 14002번에서 했던 방법처럼 제일 큰 인덱스부터 출발해서 뒤에서 앞으로 하나씩 저장하고 이를 출력하면 되는 것 아닐까?

정답입니다. 근데 이제 어떤 인덱스냐가 문제가 되는데, 이는 이분 탐색 결과를 보면 됩니다. 이분 탐색 결과 인덱스가 반환이 된다고 했는데, 그 인덱스 위치가 사실은 생각해보면 LIS 상의 인덱스가 아닐까요?

어? 근데 LIS와 리스트는 다르다면서요?

네 다릅니다. 그런데 다른 이유는 다름이 아니라 "기존에 있던 값이 대치가 되었기 때문입니다." 즉 인덱스 자체를 저장하는 배열을 따로 만들어서 각 요소 별 이분 탐색 결과를 저장한다면 왜곡이 따로 발생하지는 않을겁니다. 인덱스가 왜곡이 되는게 아닌 리스트의 값만 왜곡이 되니 말입니다.

코드를 살펴보도록 하겠습니다.

Java ☕️

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] arr;
    static int[] idx;
    static List<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        idx = new int[n]; // 인덱스를 저장하는 배열 하나를 만듭니다.
        list = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        list.add(arr[0]);
        br.close();
        for (int i = 1; i < n; i++) {
            int ele = arr[i];
            if (list.get(list.size() - 1) < ele) {
                list.add(ele);
                idx[i] = list.size() - 1;
            } else {
                int searchedIdx = lowerBound(ele);
                list.set(searchedIdx, ele);
                idx[i] = searchedIdx;
            }
        }

        sb.append(list.size() + "\n");
        int lastIdx = list.size() - 1;

        for (int i = n - 1; lastIdx >= 0 && i >= 0; i--) {
            if (idx[i] != lastIdx) continue;
            lastIdx--;
            stack.push(arr[i]);
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }

        System.out.println(sb);
        br.close();
    }

    private static int lowerBound(int target) {
        int start = 0;
        int end = list.size();

        while (start < end) {
            int mid = start + (end - start) / 2;
            if (list.get(mid) >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

플레 5 결과

profile
주재완
언제나 탐구하고 공부하는 개발자, 주재완입니다.
이전 포스트

[백준] #11049 행렬 곱셈 순서 (Java)

다음 포스트

[백준] #13460 구슬 탈출 2 (Java) (feat. 구현 문제 접근법)

0개의 댓글