백준 11053 & 11722 "가장 긴 증가/감소 부분 수열" (JAVA)

🔍 문제링크

https://www.acmicpc.net/problem/11053

https://www.acmicpc.net/problem/11722

---

📌 문제 요약

1️⃣ 백준 11053 - 가장 긴 증가하는 부분 수열 (LIS)

• 수열에서 "증가하는 부분 수열" 중에서 가장 긴 길이를 찾는 문제.

2️⃣ 백준 11722 - 가장 긴 감소하는 부분 수열 (LDS)

• 수열에서 "감소하는 부분 수열" 중에서 가장 긴 길이를 찾는 문제.

---

🛠 풀이 및 알고리즘

1. dp[i] 정의
   • dp[i]는 nums[i]를 마지막 원소로 하는 증가/감소 수열의 최장 길이.
2. 점화식 (DP)
   • LIS (Longest Increasing Subsequence)
     • dp[i] = max(dp[i], dp[j] + 1) (단, nums[i] > nums[j])
   • LDS (Longest Decreasing Subsequence)
     • dp[i] = max(dp[i], dp[j] + 1) (단, nums[i] < nums[j])
3. 최종 결과
   • dp 배열에서 최댓값 출력 (Arrays.stream(dp).max().getAsInt())

---

💡 코드

1.  백준 11053 - 가장 긴 증가하는 부분 수열 (LIS)

public class Baekjoon_11053 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int[] dp = new int[n]; // dp[i]는 num[i]가 마지막 숫자인 증가 수열의 최대 갯수
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        System.out.println(Arrays.stream(dp).max().getAsInt());
    }
}

2. 백준 11722 - 가장 긴 감소하는 부분 수열 (LDS)

public class Baekjoon_11722 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int[] dp = new int[n]; // dp[i]는 nums[i]를 마지막 숫자인 감소 수열의 최대 길이
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] < nums[j]) {
                    dp[i]  = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        System.out.println(Arrays.stream(dp).max().getAsInt());
    }
}

---

🏆 시간 복잡도 분석

• O(N^2):
• N ≤ 1000이므로 최악의 경우 O(1,000,000)