[백준 , 11053번] 가장 긴 증가하는 부분 수열 (수열, 동적계획법, 다이나믹 프로그래밍 DP, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 가장 긴 증가하는 부분 수열"문제가 처음에는 쉽게 이해가 되지 않았지만 알고보면 크게 어렵지 않은 문제입니다.

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다. 문제에서 나와있듯이 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

 

가장 긴 증가하는 부분 수열이라는 말은 주어진 수열에서 순서대로 (즉, 원래 수열의 순서를 유지하면서) 증가하는 수들 중에서 가장 긴 부분 수열을 찾는 문제입니다.

 

이때 "가장 긴"은 부분 수열의 길이를 의미하며, 반드시 연속된 원소일 필요는 없습니다. 즉, 예제 입력1번대로 A = {10, 20, 10, 30, 20, 50} 라면 수열을 다음과 같이 존재합니다.

• 10
  • {10} ➡️ 길이 : 1
• 20
  • {10, 20} ➡️ 길이 : 2
• 30
  • {10, 20, 30} ➡️ 길이 : 3
• 50
  • {10, 20, 30, 50} ➡️ 길이 : 4

그러면 이제 부분 수열의 길이를 구하기 위해서 다이나믹 프로그래밍 알고리즘을 활용해야합니다. 이 때 점화식을 구해야하는데 점화식은 다음과 같습니다.

 

• A[i]를 마지막 원소로 가지는 가장 긴 부분 수열을 구하려면, A[i] 이전의 원소 중에서 A[i]보다 작은 값들만 사용해야 합니다.
• 예를 들어, A=[10,20,10,30], i=3일 때
  • A[0]=10<A[3], 따라서 A[3]를 [10]뒤에 붙일 수 있습니다.
  • A[1]=20<A[3], 따라서 A[3]를 [10,20] 뒤에 붙일 수 있습니다.
  • A[2]=10<A[3], 따라서 A[3]를 [10] 뒤에 붙일 수 있습니다.

즉, max(dp[1],dp[0]+1)

 

 

여기서 문제의 핵심은 LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)의 특성상 수열은 원래 수열의 원소들을 순서대로 선택하되, 원소들 사이에 반드시 증가 관계가 성립해야 합니다.

 

즉, 선택한 원소들 중에서 각 원소는 그 이전 원소보다 커야 합니다.

 

[Algorithm] LIS : 가장 긴 증가하는 부분 수열 알고리즘 알아보기

---

전체 코드

 

 

문제의 핵심인 수열을 구하는 부분만 설명하자면, 먼저 dp 배열을 fill()메서드로 1로 채워줍니다.

 

이후, 각 원소에 대해 이전 원소들과 비교하여, 이전 값이 더 작다면 그 이전 값을 끝으로 하는 가장 긴 증가하는 부분 수열에 현재 값을 추가할 수 있기 때문에 dp[i] 값을 업데이트해줍니다.

 

이때, 이중 for문을 사용하는 이유는, 각 원소 A[i]에 대해 i보다 작은 인덱스 j를 순차적으로 확인하면서, 이전 원소들이 현재 원소보다 작은 경우에만 부분 수열을 확장할 수 있기 때문입니다.

 

이렇게 비교한 후, dp[i] = Math.max(dp[i], dp[j] + 1)을 통해 dp[i] 값을 업데이트하여 현재 원소를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이를 구합니다.

 

결국, dp 배열에는 각 원소를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이가 저장되며, 그 중 가장 큰 값을 Stream의 max()메서드와 getAsInt()메서드를 사용하여 최댓값을 찾아 LIS의 길이를 구할 수 있습니다.

---

 

이때 이전 값과 비교하지 않으면, 수열은 단순히 {1, 2, 3, 4, 5, 6}처럼 모든 원소가 증가하는 형태로만 이어지게 됩니다. 따라서 이전 값이 더 작을 때만 업데이트하는 조건문이 중요합니다.