가장 긴 증가하는 부분 수열
문제
수열 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출처
- 문제를 만든 사람: baekjoon
- 데이터를 추가한 사람: harinboy
비슷한 문제
- 11054번. 가장 긴 바이토닉 부분 수열
- 11055번. 가장 큰 증가 부분 수열
- 11722번. 가장 긴 감소하는 부분 수열
- 12015번. 가장 긴 증가하는 부분 수열 2
- 12738번. 가장 긴 증가하는 부분 수열 3
- 14002번. 가장 긴 증가하는 부분 수열 4
- 14003번. 가장 긴 증가하는 부분 수열 5
알고리즘 분류
- 다이나믹 프로그래밍
해결한 코드
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var n = input[0] / 1
if(n > 1){
var sequence = input[1].split(' ').map((element) => element / 1)
var d = Array(n).fill(1)
var answer = 0
d[0] = 1
for(var i=1; i<n; i++){
var currentElement = sequence[i]
var cnt = 0
for(var j=0; j<i; j++){
if(currentElement>sequence[j]){
cnt = Math.max(cnt, d[j])
}
}
d[i] += cnt
answer = Math.max(answer, d[i])
}
console.log(answer)
} else {
console.log(1)
}알고리즘
1. 점화식을 세운다.
이를 위해 규칙을 살펴본다.
만약 현재 수열이
sequence = [ 10, 20, 10, 30, 20, 50 ]이렇게 길이가 6인 수열로 입력되었다면,
1-1. 길이가 1일 때 가장 긴 부분 수열 구하기
[ 10 ]계산할 것도 없이 가장 긴 부분 수열의 길이는 1이다.
📍 이 값을 따로 메모해두어야 하므로, (길이가 수열의 길이와 같은)d라는 배열을 만들어 1을 저장한다.
(나는 d 배열의 초기값을 모두 1로 지정하였다.)
👉🏻d = [ 1, 1, 1, 1, 1, 1 ]1-2. 길이가 2일 때 가장 긴 부분 수열 구하기
[ 10, 20 ]길이가 2인 수열은 sequence 배열의 인덱스가 0~1까지인 수열이다.
sequence[1]보다 앞에 있는 숫자들과sequence[1]을 비교한다.
sequence[0]vssequence[1]
만약sequence[1]이 더 크면 👉🏻d[0]에 저장한 수열의 길이에sequence[1]을 더 붙일 수 있다는 말이 된다.
하지만sequence[1]이 더 작으면 👉🏻d[0]에 저장한 수열의 길이에sequence[1]을 더 붙일 수 없다.10 < 20 이므로 붙일 수 있음 !!
∴
d[0]에 + 1을 하여d[1]에 저장한다.
👉🏻d = [ 1, 2, 1, 1, 1, 1 ]1-3. 길이가 3일 때 가장 긴 부분 수열 구하기
[ 10, 20, 10 ]
sequence[2]보다 앞에 있는 숫자들과sequence[2]를 비교한다.
sequence[0]vssequence[2]
sequence[2]이 더 크면 👉🏻d[0]에 저장한 수열의 길이에sequence[2]을 더 붙일 수 있다는 말이 된다.10 == 10 이므로 붙일 수 없음 !!
sequence[1]vssequence[2]
sequence[2]이 더 크면 👉🏻d[1]에 저장한 수열의 길이에sequence[2]을 더 붙일 수 있다는 말이 된다.20 > 10 이므로 붙일 수 없음 !!
👉🏻
d = [ 1, 2, 1, 1, 1, 1 ]1-4. 길이가 4일 때 가장 긴 부분 수열 구하기
[ 10, 20, 10, 30 ]
sequence[3]보다 앞에 있는 숫자들과sequence[3]를 비교한다.
sequence[0]vssequence[3]
sequence[3]이 더 크면 👉🏻d[0]에 저장한 수열의 길이에sequence[3]을 더 붙일 수 있다는 말이 된다.10 < 30 이므로 붙일 수 있음 !!
d[0]= 1
sequence[1]vssequence[3]
sequence[3]이 더 크면 👉🏻d[1]에 저장한 수열의 길이에sequence[3]을 더 붙일 수 있다는 말이 된다.20 < 30 이므로 붙일 수 있음 !!
d[1]= 2
sequence[2]vssequence[3]
sequence[3]이 더 크면 👉🏻d[2]에 저장한 수열의 길이에sequence[3]을 더 붙일 수 있다는 말이 된다.10 < 30 이므로 붙일 수 있음 !!
d[2]= 1∴ 1, 2, 1중 최댓값에 +1 하여
d[3]에 저장한다.
👉🏻d = [ 1, 2, 1, 3, 1, 1 ]즉, 수열을 차례로 돌면서, 현재 순서보다 앞선 원소들과 값을 비교하여
👉🏻 현재 원소가 더 크다면
- (비교 하고 있는) 앞선 원소들의
d[앞선 원소]값을 구하고- (
d[앞선 원소]값들 중) 최댓값에 + 1 하여d[현재 원소]의 값으로 지정한다.2. d 배열의 최댓값을 출력한다.
※ 단 수열의 길이가 1이라면 위 점화식 계산이 어려우므로 예외 조건을 달아주어야 한다.
좋은 점화식을 세우지 못해 시간이 많이 걸린 문제.. 다이나믹 프로그래밍 공부를 더 열심히 해야겠다 ㅠㅠ
