[BOJ/Java] 11722. 가장 긴 감소하는 부분 수열

[BOJ/Java] 11722. 가장 긴 감소하는 부분 수열

11722번: 가장 긴 감소하는 부분 수열

---

문제 해석

이 문제는 주어진 배열에서 가장 긴 감소하는 부분 수열의 길이를 찾는 문제이다. 감소하는 부분 수열이란, 수열의 원소들이 감소하는 순서로 정렬된 수열을 의미한다.

풀이 과정

제출된 코드는 동적 프로그래밍(DP)을 이용한 방식으로 구현되어 있지만, 로직에 오류가 있어 정확히 문제의 요구사항을 충족하지 못하는 부분이 있다. 주어진 코드는 각 원소를 순회하면서, 해당 원소가 위치할 수 있는 dp 배열의 위치를 찾아 갱신하는 로직을 사용한다. 하지만, 이 로직은 감소하는 수열을 찾기보다는 어떤 형태로든 수열을 구성하려 하므로 문제의 의도와 맞지 않는다.

문제를 풀기 위해 정상적으로 감소하는 부분 수열을 확인하려면, dp 배열을 이용하여 각 위치에서 끝나는 가장 긴 감소하는 부분 수열의 길이를 저장해야 한다. 각 원소에 대해 이전의 원소들과 비교하여, 현재 원소가 더 작을 경우 dp 값을 갱신하는 방식으로 로직을 구성해야 한다.

코드

package edu.ssafy.im.BOJ.Silver.S2.No11722;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, ans = 0; // N: 수열의 크기, ans: 최장 감소 부분 수열의 길이
    private static int[] A, dp; // A: 입력받은 수열, dp: 각 위치에서 끝나는 가장 긴 감소 부분 수열의 길이를 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 수열의 크기 입력

        A = new int[N]; // 수열 저장 배열
        StringTokenizer st = new StringTokenizer(br.readLine()); // 수열 입력 처리
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken()); // 수열의 각 원소 저장
        }

        dp = new int[N]; // DP 배열 초기화
        for (int a : A) { // 각 원소에 대해
            for (int i = 0; i < N; i++) {
                if (dp[i] <= a) { // 현재 원소가 dp 배열 내 저장된 원소보다 크거나 같으면 갱신 (로직 오류 부분)
                    dp[i] = a;
                    break;
                }
            }
        }

        for (int d : dp) { // DP 배열을 순회하며 값이 0이 아닌 원소의 수 계산
            if (d != 0) ans++;
            else break;
        }

        sb.append(ans); // 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 O(N^2)이다. 이는 각 원소에 대해 최악의 경우 모든 dp 배열 원소를 검사할 수 있기 때문이다.

느낀점

코드의 오류를 통해 동적 프로그래밍의 정확한 이해와 적용의 중요성을 다시 한번 깨달았다. 문제의 요구사항을 정확히 이해하고, 알고리즘을 설계할 때 논리적 오류가 없도록 주의해야 함을 느낀다.