[BOJ/Java] 11053. 가장 긴 증가하는 부분 수열

[BOJ/Java] 11053. 가장 긴 증가하는 부분 수열

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

---

문제 해석

이 문제에서는 수열 A가 주어지고, 그 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 찾는다. 부분 수열은 수열에서 일부 항목을 선택하여 만든 수열이며, 선택된 순서는 원래 수열의 순서를 유지해야 한다.

풀이 과정

• 변수 초기화 및 입력: N은 수열의 길이, arr는 수열을 저장하는 배열, dp는 각 위치에서의 LIS 길이를 저장하는 배열이다.
• 다이나믹 프로그래밍 적용: 각 원소에 대해 이전 원소들을 검토하고, 현재 원소보다 작은 원소들 중 최대의 dp값을 찾아 현재 위치의 dp값을 갱신한다.
• 최대 LIS 길이 계산: 모든 위치의 dp 값을 검토하여 최대 값을 찾는다.

코드

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

import java.io.*;

public class Main {
	private static int N;       // 수열의 길이
	private static int[] arr;   // 주어진 수열을 저장할 배열
	private static int ans;     // 최종 결과를 저장할 변수 (최대 LIS 길이)
	private static int[] dp;    // 각 위치에서의 LIS 길이를 저장할 배열

	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());  // 수열의 길이 입력 받기
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[N];
		dp = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());  // 수열의 각 원소 입력 받기
		}
		
		for (int i = 0; i < N; i++) {
			sol(i);  // 각 위치에서의 LIS 길이 계산
		}
		
		for (int i = 0; i < N; i++) {
			ans = Math.max(ans, dp[i]);  // 최대 LIS 길이 계산
		}
		
		sb.append(ans);
		bw.write(sb.toString());  // 결과 출력
		bw.flush();
		bw.close();
	}

	private static int sol(int i) {
		if (dp[i] == 0) {  // 아직 계산되지 않은 위치라면
			dp[i] = 1;  // 자기 자신만 포함한 경우의 초기값 설정
			
			for (int j = i-1; j >= 0; j--) {  // 이전 위치의 원소들 검토
				if (arr[j] < arr[i]) {  // 증가하는 부분 수열 조건 확인
					dp[i] = Math.max(dp[i], sol(j) + 1);  // 최대 길이로 갱신
				}
			}
		}
		return dp[i];
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 𝑂(𝑁^2)이다. 각 원소에 대해 이전 모든 원소를 검사하기 때문이다.

느낀점

가장 긴 증가하는 부분 수열 문제는 다이나믹 프로그래밍을 활용하여 효율적으로 해결할 수 있는 기본적인 문제 유형 중 하나이다. 이 문제를 통해 다이나믹 프로그래밍의 접근 방식과 구현을 연습하고 이해하는 데 도움이 되었다. 이러한 문제는 알고리즘 경진대회뿐만 아니라 실제 소프트웨어 개발에서도 유용하게 활용될 수 있는 중요한 개념이다.