최장 증가 부분 수열(LIS) 구하기: 다이나믹 프로그래밍 활용법

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 부분 수열 중 증가하는 원소들로 이루어진 가장 긴 수열을 찾는 문제입니다. 이 문제는 컴퓨터 과학과 알고리즘 분야에서 중요한 문제 중 하나로, 다양한 응용 분야에서 사용됩니다. 이번 글에서는 다이나믹 프로그래밍(dynamic programming) 접근법을 사용해 LIS를 효율적으로 구하는 방법을 자세히 설명하겠습니다.

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 작은 하위 문제로 나누어 그 결과를 저장하고, 이를 사용해 전체 문제를 해결하는 알고리즘 기법입니다. 이는 메모이제이션(memoization)이나 타뷸레이션(tabulation)을 사용해 중복 계산을 피함으로써 효율성을 극대화합니다. 주로 최적화 문제에서 사용되며, 매우 큰 입력에서도 실용적인 실행 시간을 보장합니다.

LIS 문제 정의

LIS 문제는 다음과 같이 정의할 수 있습니다:

• 주어진 수열이 [a_1, a_2, ..., a_n]이라 할 때, 가장 긴 길이의 증가하는 부분 수열을 찾습니다.

예를 들어, 수열 [10, 22, 9, 33, 21, 50, 41, 60, 80]가 주어졌을 때, LIS는 [10, 22, 33, 50, 60, 80]이며 그 길이는 6입니다.

LIS를 구하는 다이나믹 프로그래밍 접근법

다이나믹 프로그래밍을 사용해 LIS를 구하는 방법은 다음과 같습니다:

1. dp[i]를 수열의 i번째 원소를 마지막으로 하는 LIS의 길이라고 정의합니다.
2. 초기화: 모든 dp 배열의 값을 1로 초기화합니다. 즉, dp[i] = 1(모든 원소가 자기 자신만으로 LIS를 형성할 수 있으므로).
3. 상태 전이: 각 i와 j에 대해(단, 0 ≤ j < i), a[j] < a[i]이고, dp[i] < dp[j] + 1이면 dp[i] = dp[j] + 1로 업데이트합니다.
4. 결과: 전체 dp 배열을 순회하며 최대값을 찾습니다. 이것이 LIS의 길이입니다.

단계별 예제

다음 예제 수열을 사용해 단계별로 살펴보겠습니다: [10, 22, 9, 33, 21, 50, 41, 60, 80].

1. 초기화:

plaintext
10 22  9 33 21 50 41 60 80
 1  1  1  1  1  1  1  1  1

2. 상태 전이:

• i = 1, j = 0: a[0] < a[1] (10 < 22), dp[1] = max(dp[1], dp[0] + 1) = 2

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  1  1  1  1  1  1

• i = 2, 상태 전이 없음 (9가 이전의 어떤 값보다 크지 않으므로)

• i = 3, j = 0: a[0] < a[3] (10 < 33), dp[3] = max(dp[3], dp[0] + 1) = 2

• i = 3, j = 1: a[1] < a[3] (22 < 33), dp[3] = max(dp[3], dp[1] + 1) = 3

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  1  1  1  1  1

• i = 4, j = 0: a[0] < a[4] (10 < 21), dp[4] = max(dp[4], dp[0] + 1) = 2
• i = 4, j = 2: a[2] < a[4] (9 < 21), 상태 전이 없음
• i = 4, j = 3: a[3] < a[4] (33 >= 21), 상태 전이 없음

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  2  1  1  1  1

• i = 5, j = 0: a[0] < a[5] (10 < 50), dp[5] = max(dp[5], dp[0] + 1) = 2
• i = 5, j = 1: a[1] < a[5] (22 < 50), dp[5] = max(dp[5], dp[1] + 1) = 3
• i = 5, j = 3: a[3] < a[5] (33 < 50), dp[5] = max(dp[5], dp[3] + 1) = 4
• i = 5, j = 4: a[4] < a[5] (21 < 50), 상태 전이 없음

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  2  4  1  1  1

• i = 6, j = 0: a[0] < a[6] (10 < 41), dp[6] = max(dp[6], dp[0] + 1) = 2
• i = 6, j = 1: a[1] < a[6] (22 < 41), dp[6] = max(dp[6], dp[1] + 1) = 3
• i = 6, j = 3: a[3] < a[6] (33 < 41), dp[6] = max(dp[6], dp[3] + 1) = 4
• i = 6, j = 4: a[4] < a[6] (21 < 41), 상태 전이 없음
• i = 6, j = 5: a[5] < a[6] (50 >= 41), 상태 전이 없음

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  2  4  4  1  1

• i = 7, j = 0: a[0] < a[7] (10 < 60), dp[7] = max(dp[7], dp[0] + 1) = 2
• i = 7, j = 1: a[1] < a[7] (22 < 60), dp[7] = max(dp[7], dp[1] + 1) = 3
• i = 7, j = 3: a[3] < a[7] (33 < 60), dp[7] = max(dp[7], dp[3] + 1) = 4
• i = 7, j = 4: a[4] < a[7] (21 < 60), 상태 전이 없음
• i = 7, j = 5: a[5] < a[7] (50 < 60), dp[7] = max(dp[7], dp[5] + 1) = 5
• i = 7, j = 6: a[6] < a[7] (41 < 60), 상태 전이 없음

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  2  4  4  5  1

• i = 8, j = 0: a[0] < a[8] (10 < 80), dp[8] = max(dp[8], dp[0] + 1) = 2
• i = 8, j = 1: a[1] < a[8] (22 < 80), dp[8] = max(dp[8], dp[1] + 1) = 3
• i = 8, j = 3: a[3] < a[8] (33 < 80), dp[8] = max(dp[8], dp[3] + 1) = 4
• i = 8, j = 4: a[4] < a[8] (21 < 80), 상태 전이 없음
• i = 8, j = 5: a[5] < a[8] (50 < 80), dp[8] = max(dp[8], dp[5] + 1) = 5
• i = 8, j = 6: a[6] < a[8] (41 < 80), 상태 전이 없음
• i = 8, j = 7: a[7] < a[8] (60 < 80), dp[8] = max(dp[8], dp[7] + 1) = 6

plaintext
10 22  9 33 21 50 41 60 80
 1  2  1  3  2  4  4  5  6

3. 결과: dp 배열의 최대값은 6이며, 이는 최장 증가 부분 수열의 길이입니다.

plaintext
최종 dp 배열: [1, 2, 1, 3, 2, 4, 4, 5, 6]
최대 LIS 길이: 6

시간 복잡도

이 다이나믹 프로그래밍 알고리즘의 시간 복잡도는 O(n^2)입니다. 이는 이중 루프를 사용해 각 원소에 대해 이전 모든 원소와 비교하기 때문입니다. 이는 작은 수열에서 충분한 성능을 보이지만, 큰 수열에서는 더 나은 접근법이 필요할 수 있습니다.

결론

이 글에서는 다이나믹 프로그래밍을 사용해 최장 증가 부분 수열(LIS)을 구하는 방법을 자세히 설명했습니다. 다이나믹 프로그래밍이란 무엇인지, 이를 사용해 LIS 문제를 해결하는 방법, 그리고 예제를 통해 단계별로 문제를 푸는 과정을 다뤘습니다. 다이나믹 프로그래밍 접근법은 시간 복잡도가 O(n^2)으로 작은 입력에서는 효율적이지만, 큰 입력에서는 다른 최적화 기법을 고려해 볼 필요가 있습니다. 이를 통해 여러분이 다이나믹 프로그래밍 기법을 이해하고, LIS 문제에 적용하는 데 도움이 되었으면 합니다.