가장 긴 증가하는 부분 수열
1 초 | 256 MB | 169140 | 67958 | 45098 | 38.082% |
---|
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1 복사
6
10 20 10 30 20 50
예제 출력 1 복사
4
가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 동적 프로그래밍(DP)을 이용하여 해결하는 Java 코드를 작성해드리겠습니다. 이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제입니다. DP를 사용하면 효율적으로 해결할 수 있습니다.
Java 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 수열 A의 크기 N 입력
int N = scanner.nextInt();
int[] A = new int[N];
// 수열 A의 요소들 입력
for (int i = 0; i < N; i++) {
A[i] = scanner.nextInt();
}
// DP 배열 초기화
int[] dp = new int[N];
int maxLength = 1; // LIS의 최소 길이는 1
// DP 초기값 설정
for (int i = 0; i < N; i++) {
dp[i] = 1;
}
// DP를 이용하여 LIS 계산
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (A[i] > A[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
// 현재까지의 최대 LIS 길이 업데이트
if (maxLength < dp[i]) {
maxLength = dp[i];
}
}
// 결과 출력
System.out.println(maxLength);
scanner.close();
}
}
코드 설명
1.입력 처리:
- 첫째 줄에서 수열의 크기 ( N )을 입력받고, 두 번째 줄에서 수열 ( A )의 요소들을 입력받습니다.
2.DP 배열 초기화:
dp
배열은 각 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 초기값으로 모든dp
값을 1로 설정합니다. 이는 각 요소 자체만으로도 길이 1의 증가하는 부분 수열이 되기 때문입니다.
3.DP 계산:
- 이중 루프를 사용하여
dp
배열을 업데이트합니다. A[i]
가A[j]
보다 크고(A[i] > A[j]
),dp[i]
가dp[j] + 1
보다 작다면dp[i]
를dp[j] + 1
로 업데이트합니다.- 이는
A[j]
까지의 부분 수열에A[i]
를 추가하여 새로운 증가하는 부분 수열을 만들 수 있기 때문입니다.
4.최대 길이 계산:
- 각
dp[i]
값을 비교하여 현재까지의 가장 긴 증가하는 부분 수열의 길이를maxLength
로 업데이트합니다.
5.결과 출력:
maxLength
를 출력하여 가장 긴 증가하는 부분 수열의 길이를 결과로 나타냅니다.
이 코드는 시간 복잡도 ( O(N^2) )로, 입력 크기 ( N )이 1,000 이하일 때 효율적으로 동작합니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 부녀회장이될테야 - 2775번 (1) | 2024.06.15 |
---|---|
[백준] 핸드폰 번호 궁합 - 17202번호 (1) | 2024.06.15 |
DP(Dynamic Programming) 핥아보기 (0) | 2024.06.15 |
[백준] 우유축제 - 14720번 (0) | 2024.06.14 |
[백준] 한조서열정리하고옴ㅋㅋ - 14659번 (1) | 2024.06.14 |