LeetCode의 300번째 문제인 Longest Increasing Subsequence를 함께 풀어보도록 하겠습니다.
문제
정수 배열 nums가 주어졌을 때, 가장 길고 엄격하게 증가하는 부분 수열의 길이를 반환하시오.
예제
입력: nums = [10,9,2,5,3,7,101,18]
결과: 4입력: nums = [0,1,0,3,2,3]
결과: 4입력: nums = [7,7,7,7,7,7,7]
결과: 1풀이 1
이 문제를 가장 단순 무식하기 푸는 방법은 주어진 배열에서 나올 수 있는 모든 경우의 수의 부분 수열을 구하는 건데요. 엄격하게 증가하는 부분 수열들만 길이를 구해서 그 중에서 가장 큰 값이 우리가 찾고자 하는 값일 것입니다.
예를 들어, 입력 배열로 [1, 2, 1, 3]이 주어지면, 16개의 부분 수열을 구할 수 있는데요.
그 중 10개의 수열이 엄격하게 증가하고, 기장 긴 수열은 [1, 2, 3]으로 길이가 3입니다.
| 부분 수열 | 증가? | 길이 |
|---|---|---|
| [] | ✅ | 0 |
| [3] | ✅ | 1 |
| [1] | ✅ | 1 |
| [1, 3] | ✅ | 2 |
| [2] | ✅ | 1 |
| [2, 3] | ✅ | 2 |
| [2, 1] | ❌ | - |
| [2, 1, 3] | ❌ | - |
| [1] | ✅ | 1 |
| [1, 3] | ✅ | 2 |
| [1, 1] | ❌ | - |
| [1, 1, 3] | ❌ | - |
| [1, 2] | ✅ | 2 |
| [1, 2, 3] | ✅ | 3 (최대) |
| [1, 2, 1] | ❌ | - |
| [1, 2, 1, 3] | ❌ | - |
이 알고리즘을 코드로 한 번 구현해보겠습니다. 선택된 숫자의 배열과 선택되지 않은 숫자의 배열을 인자로 받는 재귀 함수를 작성하고, 부분 수열이 엄격하기 증가하는 여부를 구하기 위한 별도의 함수를 작성하였습니다.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def is_increasing(nums):
for i in range(1, len(nums)):
if nums[i - 1] >= nums[i]:
return False
return True
def dfs(picked, unpicked):
if not unpicked:
return len(picked) if is_increasing(picked) else 0
return max(
dfs(picked, unpicked[1:]), # not taken
dfs(picked + [unpicked[0]], unpicked[1:]), # taken
)
return dfs([], nums)입력 배열의 길이를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(2^n * n)이 되는데요.
재귀 함수 내에서 재귀 호출이 2번씩 일어나는데, 호출 스택의 깊이가 n이고, 수열이 증가하는지 구하는데 또 O(n)의 시간이 걸리기 때문입니다.
공간 복잡도는 호출 스택이 n과 비례하여 깊어지고, 각 재귀 함수 내에서 배열을 복제하므로 O(n^2)이 되겠습니다.
이 알고리즘은 너부 비효율적이라서 LeetCode에 제출하면 Time Limit Exceeded 오류가 발생할 것입니다.
풀이 2
위 풀이에서 각 부분 수열이 엄격하게 증가하는지 구하는데 O(n)의 시간이 걸렸느데요.
반드시 이렇게 수열 내의 모든 숫자를 차례대로 대소 비교를 해야만 할까요?
조금만 더 생각해보면 수열에 새로운 숫자를 추가하기 전에 여태까지 만든 수열의 마지막 숫자와만 비교를 해도 됩니다. 마지막 숫자보다 크다면 그 숫자를 수열에 추가하고, 작다면 그 숫자를 수열에 추가하지 않는다면, 애초에 모든 부분 수열을 만들어내지 않고, 증가하는 부분 수열만 만들어 낼 수 있을 것입니다.
[]
[]
[]
[] => 길이 0
[3] => 길이 1
[1]
[1] => 길이 1
[1, 3] => 길이 2 (1 < 3)
[2]
[2]
[2] => 길이 1
[2, 3] => 길이 2 (2 < 3)
[2, 1] => ❌ (2 > 1)
[1]
[1]
[1]
[1] => 길이 1
[1, 3] => 길이 2 (1 < 3)
[1, 1] => ❌ (1 == 1)
[1, 2]
[1, 2]
[1, 2] => 길이 2
[1, 2, 3] => 길이 3 (2 < 3) ✅ 최대여태까지 만든 수열의 마지막 숫자와만 대소 비교를 하도록 코드를 수정해보겠습니다.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def dfs(picked, unpicked):
if not unpicked:
return len(picked)
return max(
dfs(picked, unpicked[1:]), # not taken
(
dfs(picked + [unpicked[0]], unpicked[1:])
if not picked or picked[-1] < unpicked[0]
else 0
), # taken
)
return dfs([], nums)이 풀이는 더 이상 각 부분 수열이 엄격하게 증가하는지 구하기 위해서 O(n)의 시간을 쓰지 않지만 여전히 모든 경우의 수의 부분 수열을 구하고 있기 때문에 O(2^n)으로 소폭 향상됩니다.
그러므로 LeetCode에 제출하면 마찬가지로 Time Limit Exceeded 오류가 발생할 것입니다.
풀이 3
지금까지 풀이에서는 엄격하게 증가하는 수열을 만든 후에 그 길이를 구했는데요. 하지만 문제에서는 길이만 요구하고 있으니 수열을 만들지 않고 바로 길이를 구해보면 어떨까요?
여태까지 만든 수열의 마지막 숫자보다 새로운 숫자가 더 크다면 해당 숫자를 수열에 추가할 수 있으므로 우리는 단순히 길이를 1 증가시킬 수 있을 것입니다.
그러므로 재귀 함수가 수열의 마지막 숫자와 다음으로 고려할 숫자의 인덱스만 받도록 재설계할 수 있습니다.
이렇게 코드를 수정하면 중복되는 입력으로 재귀 호출이 일어나서 메모이제이션(memoization)을 활용할 수 있게 됩니다.
from functools import cache
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
@cache
def dfs(start, prev):
if start == len(nums):
return 0
return max(
dfs(start + 1, prev), # not taken
(
1 + dfs(start + 1, start)
if prev < 0 or nums[prev] < nums[start]
else 0
), # taken
)
return dfs(0, -1)이 풀이는 시간 복잡도는 메모이제이션 효과로 중복 연산이 제거되어 O(n^2)으로 대폭 향싱이 됩니다.
더 이상 재귀 함수에 배열을 복제하지 않으므로 공간 복잡도도 O(n)으로 개선될 것이빈다.
재귀 함수가 어떻게 호출되고 언제 캐시에 저장된 값이 사용되는지 파악하기 쉽도록 전체 호출 트리를 시각화해보았습니다.
F(-1, 0) = max(2, 2 + 1) = 3
F(-1, 1) => max(2, 1 + 1) = 2
F(-1, 2) => max(1, 1 + 1) = 2
F(-1, 3) => max(0, 1 + 0) = 1
F(-1, 4) => 0
F(3, 4) => 0
F(2, 3) => max(0, 1 + 0) = 1
F(2, 4) => 0
F(3, 4) => ✅ cache hit => 0
F(1, 2) => max(1, 0) = 1
F(1, 3) => max(0, 1 + 0) = 1
F(1, 4) => 0
F(3, 4) => ✅ cache hit => 0
F(0, 1) => max(2, 1 + 1) = 2
F(0, 2) => max(1, 1 + 1) = 2
F(0, 3) => max(0, 1 + 0) = 1
F(0, 4) => 0
F(3, 4) => ✅ cache hit => 0
F(1, 2) => ✅ cache hit => 1
F(1, 3) => ✅ cache hit => 1
F(1, 4) => ✅ cache hit => 0
F(3, 4) => ✅ cache hit => 0풀이 4
이 문제는 동적 계획법(Dynamic Programming)이라는 테크닉을 사용하면 반복 알고리즘으로도 해결할 수 있는데요.
기본 아이디어는 인덱스 0부터 인텍스 n - 1에 있는 숫자에서 끝나는 배열에서 가장 긴 증가하는 수열의 길이를 알고 있으면,
인덱스 n에 있는 숫자와 대소 비교를 통해서 인덱스 n에서 끝나는 배열에서 가장 긴 증가하는 수열의 길이를 구할 수 있다는 것입니다.
따라서 n을 하나씩 늘려가면서 가장 긴 증가하는 수열의 길이를 차곡 차곡 배열에 쌓아나가면,
더 작은 인덱스에서 구한 결과 값을 더 큰 인덱스에서 결과를 구할 때 활용할 수 있을 것입니다.
인덱스가 0일 때는 숫자가 하나 밖에 없기 때문에 수열의 길이가 1이 되기 때문에, 배열의 초기값으로 모두 1을 저장해놓고 반복을 시작할 수 있습니다.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
for cur in range(1, len(nums)):
for pre in range(cur):
if nums[pre] < nums[cur]:
dp[cur] = max(1 + dp[pre], dp[cur])
return max(dp)이해를 돕기 위해서 위 반복 알고리즘이 수행되는 과정을 시각화해보았습니다.
dp[0] = 1
cur = 1
pre = 0
nums[0] = 1 < nums[1] = 2 ✅
dp[1] = max(dp[0] + 1, dp[1]) = max(1 + 1, 1) = 2
cur = 2
pre = 0
nums[0] = 1 == nums[2] = 1 ❌
pre = 1
nums[1] = 2 > nums[2] = 1 ❌
cur = 3
pre = 0
nums[0] = 1 < nums[3] = 3 ✅
dp[3] = max(dp[0] + 1, dp[3]) = max(1 + 1, 1) = 2
pre = 1
nums[1] = 2 < nums[3] = 3 ✅
dp[3] = max(dp[1] + 1, dp[3]) = max(2 + 1, 2) = 3
pre = 2
nums[2] = 1 < nums[3] = 3 ✅
dp[3] = max(dp[2] + 1, dp[3]) = max(1 + 1, 3) = 3풀이 5
이 문제는 직관을 동원하여 완전히 새로운 방법으로 접근해볼 수도 있습니다.
우리가 언제 부분 수열에 새로운 숫자를 넣는지를 관찰해보면 어떨까요?
어떤 숫자가 여태까지 구한 부분 수열의 최대 값보다 크다면 간단합니다. 무조건 부분 수열에 넣어야 합니다.
그렇지 않다면 우리에게는 여러 가지 경우의 수가 생기는데요. 하지만 한 가지 확실한 것은 부분 수열의 길이는 지금보다 늘어날 수 없다는 것입니다.
자, 그러면 새로운 숫자가 여태까지 구한 부분 수열의 최대 값보다 작을 때는 이 숫자로 기존 수열에 있는 값을 바꾸면 어떨까요?
이게 말로만은 설명이 좀 어려워서 제가 예제를 통해서 추가로 설명을 드릴께요. 😅
입력 배열로 [5, 1, 4, 2, 3]가 주어졌다고 상상을 해보겠습니다.
첫 번째 숫자는 무조건 부분 수열에 넣습니다. 숫자가 하나도 없는 것 보다는 하나라도 있는 게 무조건 유리할테니까요.
nums = [5, 1, 4, 2, 3]
^
부분 수열 = [] + [5]두 번째 숫자는 1은 부분 수열의 최대값 5보다 작습니다.
여기서 우리는 고민에 빠지는데요… 🤔
5을 그대로 두면 앞으로 나오는 숫자가 적어도 5보다는 커야지 부분 수열에 넣을 수 있을 것입니다.
하지만 1로 바꾸면 앞으로 나오는 숫자가 1보다만 크면 부분 수열에 넣을 수 있을 것입니다.
그러므로 5을 1로 대체해놓는 것이 훨씬 유리하다는 것을 알 수 있습니다. 💡
nums = [5, 1, 4, 2, 3]
^
부분 수열 = [5 👉 1]다음 숫자 4은 부분 수열의 최대값 1보다 큽니다.
증가하는 부분 수열의 길이를 늘리기 위해서 이 숫자를 추가해야 합니다.
nums = [5, 1, 4, 2, 3]
^
부분 수열 = [1] + [4]다음 숫자 2는 부분 수열의 최대값 4보다 작습니다.
우리는 두 번째 숫자에서와 동일한 이유로 4을 2로 바꿉니다.
nums = [5, 1, 4, 2, 3]
^
부분 수열 = [1, 4 👉 2]다음 숫자 3은 부분 수열의 최대값 2보다 큽니다.
증가하는 부분 수열의 길이를 늘리기 위해서 이 숫자를 추가해야 합니다.
nums = [5, 1, 4, 2, 3]
^
부분 수열 = [1, 2] + [3]이를 통해 최종적으로 길이가 3인 부분 수열 [1, 2, 3]을 구하게 되었습니다. 🎉
이 접근 방식의 한 가지 맹점은 부분 수열 안에 들어있는 숫자가 틀릴 수도 있다는 것입니다.
예를 들어, 입력 배열로 [2, 3, 4, 1]이 주어지면, 증가하는 가장 긴 부분 수열은 [2, 3, 4]이지만 이 알고리즘을 통해서 구하면 [1, 3, 4]가 됩니다.
하지만 부분 수열의 길이만 정확하다면 큰 문제가 되지 않을 것입니다.
이 알고리즘을 코드로 구현해보겠습니다.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
sub = [nums[0]]
for num in nums[1:]:
# 이 숫자와 부분 수열의 최대값보다 크면 부분 수열에 무조건 추가
if num > sub[-1]:
sub.append(num)
else:
# 부분 수열에서 이 숫자보다 가장 가깝게 큰 숫자를 찾아서 대체
i = 0
while sub[i] < num:
i += 1
sub[i] = num
return len(sub)이 풀이는 최악의 경우 for 반복문 안에서 while 반목문이 실행되기 때문에 O(n^2)의 시간 복잡도를 갖습니다.
공간 복잡도는 부분 수열을 저장하는 배열 안에 입력 배열의 모든 숫자가 저장될 수 있으므로 O(n)이 됩니다.
풀이 6
위 풀이는 선형 탐색을 대신에 이분 탐색(binary search)을 하도록 개선할 수 있습니다.
파이썬의 bisect 모듈의 bisect_left() 함수는 첫 번째 인자로 넘어온 리스트 안에 두 번째 인자로 넘어온 숫자를 정렬을 유지하려면 어느 위치에 추가해야 하는지 알려줍니다.
bisect_left() 함수가 부분 수열의 길이를 반환하다면 현재 부분 수열에는 인자로 넘긴 숫자보다 큰 숫자는 없다는 뜻입니다.
이 경우, 증가하는 부분 수열의 길이를 늘리기 위해서 이 숫자를 부분 수열의 맨 뒤에 추가해야합니다.
bisect_left() 함수가 부분 수열의 길이보다 작은 값을 반환한다면, 그 위치에 있는 숫자를 새로운 숫자로 바꿔주면 되겠습니다.
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
sub = []
for num in nums:
index = bisect_left(sub, num)
if index == len(sub):
sub.append(num)
else:
sub[index] = num
return len(sub)이분 탐색이 덕분에 인해서 이 풀이의 시간 복잡도는 O(n * log n)으로 향상됩니다.