[백준/JAVA] 11053번: 가장 긴 증가하는 부분 수열

🔺 문제

11053번: 가장 긴 증가하는 부분 수열

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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[] seq = new int[N + 1];
        int[] dp  = new int[N + 1];  // LIS 저장 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1; // dp 값 1로 초기화
        }
        
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= i ; j++) { // 1 ~ i 이전 원소들 탐색
                if(seq[j] < seq[i] && dp[i] < dp[j] + 1) { // i가 j의 값보다 크고, 이전 dp 크기보다 작으면
                    dp[i] = dp[j] + 1;
                }
            }
        }
        
        int max = -1;
        for(int i = 1 ; i <= N ; i++) {
            max = Math.max(dp[i], max);
        }
        System.out.println(max);
    }
}

✅ 해결 아이디어
✔ DP (Botom-Up)

 

 

디버깅해보면 대충 이렇게

 

---

🔺 다른 풀이들

- 과정 설명 굿..

[백준] 11053번 :가장 긴 증가하는 부분 수열 - JAVA [자바]

 

 

- 왜 dp[i] <= dp[j] 비교를 해야하나 싶었는데, 중복 방지를 위해서라는 걸 이 분 글 보고 깨달았당

[BOJ] 백준 11053번 : 가장 긴 증가하는 부분 수열 (JAVA)

---

💬 느낀 점

후앙 어렵다,,,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V	7.19	8.2	24.1.18

 

 

(+7/19 2회독 :  binary Search를 활용한 LIS 계산 풀이)

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A, dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        dp = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int LIS = 0;    // 처음 저장된 원소는 없으므로 값은 0
        
        for(int i = 0 ; i < N ; i++) {
            int idx = binarySearch(A[i], 0, LIS, LIS + 1);
            
            // 찾지 못한 경우, 가장 마지막 위치에 원소 삽입하고 LIS 길이 늘림
            if(idx == -1) {
                dp[LIS++] = A[i];
            }
            // 찾은 경우, 해당 위치에 현재 값 삽입해 갱신
            else {
                dp[idx] = A[i];
            }
        }
 
        int ans = 0;
        for(int i : dp) {
            if(i != 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }
    
    // 🔔 binary Search 활용한 LIS 🔔
    private static int binarySearch(int num, int s, int e, int size) {
        int pos = 0;    // 원소 위치 기억용 변수
        
        while(s <= e) {
            int mid = (s + e) / 2;
            
            if(num <= dp[mid]) {
                pos = mid;  
                e = mid - 1;
            }
            else {
                s = mid + 1;
            }
        }
        
        // dp 테이블에 삽입될 위치를 못 찾은 경우
        if(s == size)  {
            return -1;
        }
        // dp 테이블에 삽입될 위치를 찾은 경우
        else {
            return pos;
        }
    }
}
 

 

 

( + 8.2 3회독)

더 이해하기 좋은 풀이 발견!

알고리즘 풀이 - 백준 11053(가장 긴 증가하는 부분 수열, DP)

[DP] 백준 11053 가장 긴 증가하는 부분 수열 자바

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] A, LIS;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        LIS = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        LIS[0] = A[0];
        int end = 0;
        
        for(int i = 1 ; i < N ; i++) {
            if(LIS[end] < A[i]) {
                LIS[++end] = A[i];
                continue;
            }
            
            // LIS에 A[i]가 위치할 인덱스 찾아 해당 인덱스 값과 현재값 swap
            int targetIdx = findIdx(end, i);
            LIS[targetIdx] = A[i];
        }
        
        System.out.println(end + 1);
    }
    
    private static int findIdx(int end, int idx) {
        int start = 0;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(LIS[mid] == A[idx])      return mid;
            else if(LIS[mid] < A[idx])  start = mid + 1;
            else if(LIS[mid] > A[idx])  end = mid - 1;
        }
        
        return start;
    }
}

 

 

(+24.1.18 4회독)

단순한 방법을 찾았는데 왜 여지껏 어렵게 풀었는지,,,

이게 가장 간단한 풀이 방법 같다

 

코드 확인하기

import java.util.*;
import java.io.*;
 
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[] A = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        
        int max = 1;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < i ; j++) {
                if(A[i] > A[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        
        System.out.println(max);
    }
}
 

---

(참고)

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]