문제 설명
가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS)을 찾는 문제는 주어진 수열 내에서 증가하는 순서를 유지하며 가능한 긴 부분 수열을 찾는 것이다. 부분 수열은 연속적이지 않아도 되지만, 선택한 숫자들은 반드시 증가하는 순서를 따라야 한다.
입력 형식
- 첫 번째 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다. 이는 수열의 길이를 나타낸다.
- 두 번째 줄에 N개의 정수 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력 형식
가장 긴 증가하는 부분 수열의 길이를 출력하라.
예제
입력 예시
6
10 20 10 30 20 50출력 예시
4문제 풀이 과정
1단계: 문제 이해하기
문제를 이해하기 위해 수열을 살펴보자. 주어진 수열 [10, 20, 10, 30, 20, 50]의 경우, 가능한 증가하는 부분 수열은 여러 가지가 있다. 이 수열의 증가하는 부분 수열 중 가장 긴 것은 [10, 20, 30, 50]로, 길이는 4이다. 따라서 정답은 4가 된다.
2단계: 알고리즘 선택하기
가장 긴 증가하는 부분 수열을 찾는 알고리즘은 여러 가지가 있지만 가장 효율적인 방법은 동적 프로그래밍을 사용하는 것이다. 이 방법은 O(N^2)의 시간 복잡도를 가진다. 이 방법을 사용하여 문제를 해결해보겠다.
3단계: 동적 프로그래밍 풀이
function LIS(array) {
const N = array.length;
const dp = new Array(N).fill(1); // 부분 수열 길이를 1로 초기화
for (let i = 1; i < N; i++) {
for (let j = 0; j < i; j++) {
if (array[i] > array[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
const sequence = [10, 20, 10, 30, 20, 50];
console.log(LIS(sequence)); // 출력: 4
설명
1. dp 배열을 선언하여 각 인덱스의 가장 긴 증가하는 부분 수열의 길이를 저장한다. 초기값은 1로 설정한다, 각 요소 자신만으로도 부분 수열을 이룰 수 있기 때문이다.
2. 두 개의 반복문을 사용하여 인덱스 i와 j를 비교한다. 만약 array[i]가 array[j]보다 큰 경우, dp[i]의 값은 dp[j] + 1과 현재 dp[i]의 값 중 큰 값으로 업데이트된다. 이는 array[j]를 포함하여 array[i]를 포함한 부분 수열을 고려하는 것이다.
3. 모든 반복이 끝나면 dp 배열에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이가 된다.
결과
위 코드를 실행하면 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 성공적으로 구할 수 있다.
마무리
가장 긴 증가하는 부분 수열(LIS) 문제는 자주 출제되는 알고리즘 문제 중 하나이다. 이 문제를 통해 동적 프로그래밍의 기초를 배우고 실전 코딩 테스트에서의 문제 해결 능력을 키울 수 있다. 다양한 문제를 풀어보며 경험을 쌓는 것이 중요하다.