알고리즘 문제 - 가장 긴 증가하는 부분 수열
2023. 6. 12.
시리즈 "알고리즘 문제풀기" 개요
- 1~2주 (최소) 1개 문제 풀기를 목표로 한다.
- JavaScript 로 푼다.
문제
Baekjoon Online Judge - 11053. 가장 긴 증가하는 부분 수열
수열 A 가 주어졌을 때, "가장 긴 증가하는 부분 수열"(= Longest Increasing Subsequence, LIS)의 길이를 구하는 문제다.
예를 들어 수열이 [10, 20, 10, 30, 20, 50] 일 경우, LIS 는 ["10", "20", 10, "30", 20, "50"] 이고 길이는 4이다.
접근
DP 카테고리에 있는 문제를 푸는 것이었으므로 DP 로 푸는 것이라는 건 알고 있었다.
DP 는 문제를 간단한 문제로 나눠 푸는 방법을 말한다. 보통 문제를 작은 단위로 나눠서 가장 작은 단위의 답을 알아낸 뒤, 그 답을 이용해서 그보다 큰 단위의 답을 알아내고, 그 답을 또 재활용 해 더 큰 단위의 답을 알아내서 결국 문제의 답을 찾아내는 식이다.
이 문제에서 응용해보자면 짧은 범위 숫자에 대해 LIS 의 길이를 구한 뒤에, 그 답을 사용해 더 큰 단위의 답을 구하면 될 것이다.
수열 10, 20, 10, 30, 20, 50 을 예로 들면
- 수열 [10] 에서 LIS 길이 = 1
- 수열 [10, 20] 에서 LIS 길이 = 수열 [10] 에서 LIS 의 길이 + (20 까지 포함했을 경우 LIS 가 더 길어지면 +1 아니면 +0) = 2
- 수열 [10, 20, 10] 에서 LIS 길이 = 수열 [10, 20] 에서 LIS 의 길이 + (10 까지 포함했을 경우 LIS 가 더 길어지면 +1 아니면 +0) = 2
- 수열 [10, 20, 10, 30] 에서 LIS 길이 = 수열 [10, 20, 10] 에서 LIS 의 길이 + (30 까지 포함했을 경우 LIS 가 더 길어지면 +1 아니면 +0) = 3
- ...
이런 식이다.
풀이
후기
DP 를 사용하는 걸 모르고 풀었으면 풀 수 있었을까? 아니었을 것 같다. 풀었다고 해도 돌고 돌아 어거지로 풀었을 것 같다.
역시 많이 풀어봐야 한다. 그래야 이런 문제가 DP 라는 걸 알 수 있으니까.
목차