2023. 6. 30. 22:11ㆍ알고리즘
LIS(Longest Incresing Subsequence)
개요
최대증가수열 문제는 Dynamic Programming을 공부하기에 좋은 문제 중 하나로 잘 알려져 있다.
백준에서는 가장 긴 증가하는 부분수열 이라는 카테고리로 따로 다루고 있을정도로 문제의 변형도 많은 듯 하다.
가장 긴 증가하는 부분 수열
수열 A=[1, 5, 2, 4, 7]이 있을 때, [1, 2, 4]는 A의 부분 수열이다.
부분 수열에 포함된 수가 순 증가 (strictly increasing)하면 이 부분 수열은 증가 부분 수열 이라고 한다.
LIS는 수열이 주어졌을때 이러한 증가 부분 수열 중 가장 길이가 긴 수열을 찾는 방식이다.
아이디어
완전 탐색
가장 먼저 떠오른 아이디어는 완전탐색이다. 모든 경우의 수를 따라 어딘가에 저장하고, 그 중 가장 길이가 긴 것을 출력한다.
문제와 테스트케이스는 아래 문제를 이용하였다
가장 긴 증가하는 부분 수열 - 3
def lis(i, case=None):
print(case)
if case == None:
case = [lst[i]]
for ii in range(i+1, len(lst)):
if lst[ii] >= lst[i]:
lis(ii, case + [lst[ii]])# 입력
6
10 20 10 30 20 50
# 출력
[10, 20]
[10, 20, 30]
[10, 20, 30, 50]
[10, 20, 20]
[10, 20, 20, 50]
[10, 20, 50]
[10, 10]
[10, 10, 30]
[10, 10, 30, 50]
[10, 10, 20]
[10, 10, 20, 50]
[10, 10, 50]
[10, 30]
[10, 30, 50]
[10, 20]
[10, 20, 50]
[10, 50]이를 조금 수정해서 최대 개수를 출력하도록 만들어보았다.
def lis2(A):
if not len(A):
return 0
ret = 0
for i in range(len(A)):
B = []
for j in range(i+1, len(A)):
if (A[i] <= A[j]):
B.append(A[j])
ret = max(ret, 1 + lis2(B))
return ret# 입력
6
10 20 10 30 20 50
# 출력
4함수 lis의 결과로 보았듯이 입력에 중복이 여러 번 생기는 것을 알 수 있다. 이 중복되는 문제를 다이나믹 프로그래밍 기법을 이용하여 어딘가에 저장해두고 쓴다면 시간복잡도가 줄어들 것이다.
LIS를 구할 때 이전의 선택을 알 필요는 없으니 최적 부분 구조가 성립한다.
메모이제이션 적용하기 $O(N^2)$
함수 lis2는 수열 A의 모든 증가부분수열을 만든 뒤 그 중 가장 긴 것의 길이를 반환한다.
입력받은 수열 A는 항상 아래 2가지 조건을 만족한다
- 원래 주어진 수열 S
- 원래 주어진 수열의 원소 S[i]에 대해 S[i+1 $\cdots$] 부분 수열에서 S[i]보다 큰 수만을 포함하는 부분 수열
def lis_dp(start):
if dp[start] != -1:
return dp[start]
dp[start] = 1
for i in range(start+1, n):
if (lst[start] < lst[i]):
dp[start] = max(dp[start], lis_dp(i)+1)
return dp[start]
max_len = 0
for i in range(n):
max_len = max(max_len, lis_dp(i))
print(max_len)재귀 호출마다 lst[start]보다 뒤에있으면서 큰 수 중 하나를 다음 숫자로 결정한 뒤 여기서 시작하는 부분 증가 수열의 최대치를 구하게 된다.
뒤에 더 이을 숫자가 없는데도 for문을 도는 이유는 어차피 재귀호출을 하지 않아서 결과는 1이기 때문이다.
이 코드는 $O(N)$개의 부분문제를 가지고, $O(N)$시간의 반복문을 순회하므로 $O(N^2)$의 시간복잡도를 갖는다.
lis_dp를 호출할 때에는 항상 LIS의 증가부분수열의 시작위치를 지정해줘야 하므로 반복문을 통해 최댓값을 찾아내야 한다.
메모이제이션 적용하기 $O(N\log N)$
힌트로 이분탐색과 다이나믹프로그래밍을 이용한다라는 정보를 가지고 시작해본다. 텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지 추적한다.
아이디어
수열을 하나씩 나아가면서 c의 마지막 원소와 비교해간다. 만약 lis[i] > c[-1] 이라면 그 뒤에 덧붙이고 반대의 경우라면 이분탐색을 통해 해당 인덱스가 들어가면 좋은 최적의 위치를 찾아 해당 인덱스를 찾아 교체한다 lower_bound를 이용하므로 $O(\log N)$이며, $n$ 크기 반복문을 지나가므로 시간복잡도는 $O(N\log N)$이다.
import bisect
MIN = -9876543210
n = int(input())
lis = list(map(int, input().split()))
c = [MIN]
for i in range(n):
if lis[i] > c[-1]:
c.append(lis[i])
else:
c[bisect.bisect_left(c, lis[i])] = lis[i]
print(len(c) - 1)다만 이 방법의 경우 길이는 구할 수 있지만, 이를 구성하는 수열은 구할 수 없다. 따라서 이 문제를 풀려면 다른 아이디어를 생각해 보아야 한다.
LIS 응용
LIS 역추적하기 ($N \log N$ 응용)
아이디어 1
몇개의 테스트 케이스를 두고 이분탐색 과정을 그대로 따라가면서 최종 LIS 값이 저장되는 규칙을 찾아보았다.
예를 들어 수열 S = [10, 20, 10, 30, 20, 50]의 과정을 따라가보자.
아래는 과정마다 변수 c에 들어있는 값이다. (0번 인덱스 MIN은 생략한다.)
1. [10]
2. 10, 20
3. 10, [20]
4. 10, 20, 30
5. 10, 20, [30]
6. 10, 20, 30, [50]
[10, 20, 30, 50]c의 길이가 같을 때 가장 최신의 리스트 마지막 요소를 또다른 리스트에 넣는다.
대괄호로 마킹 한 것을 보면 된다.
예시를 하나 더 들어보면
S = [2 -8 6 -2 3 -2 7 7 -8 -9]
c는 아래 과정을 따라 업데이트 된다
0. 2
1. [-8]
2. -8, 6
3. -8, [-2]
4. -8, -2, 3
5. -8, -2, [3]
6. -8, -2, 3, 7
7. -8, -2, 3, 7
8. -8, -2, 3, 7
9. -9, -2, 3, [7]
[-8, -2, 3, 7]이를 코드로 구현하면 아래처럼 쓸 수 있다.
from bisect import bisect_left
n = int(input())
s = list(map(int, input().split()))
c = [-float('INF')]
dp = []
for i in range(n):
if c[-1] < s[i]:
c.append(s[i])
dp.append(c[-1])
else:
bs = bisect_left(c, s[i])
if c[bs] == c[-1]:
dp[-1] = s[i]
c[bs] = s[i]
print(c)
print(len(c)-1)
그러나 이 코드는 아래의 경우에서 반례가 발생한다.
7
2 3 4 1 2 3 4
## Answer
1, 2, 3, 4
## Output
2, 3, 3, 4아이디어 2
수열 S와 그에 대응하는 DP 리스트를 하나 만들어준다.
DP[i]는 S[i]가 들어갈 최적의 위치를 저장한다.
위 예시를 그대로 가져다가 따라가본다.
S = [2, 3, 4, 1, 2, 3, 4]
DP = [1, 2, 3, 1, 2, 3, 4]
C 는 아래의 과정을 따른다
[2]
[2, 3]
[2, 3, 4]
[1, 3, 4]
[1, 2, 4]
[1, 2, 3]
[1, 2, 3, 4]
DP를 거꾸로 순회하면서 S[DP[i]]를 출력한다.
아래는 코드이다.
from bisect import bisect_left
n = int(input())
s = list(map(int, input().split()))
c = [-float('INF')]
dp = [0] * (n)
for i in range(n):
if c[-1] < s[i]:
c.append(s[i])
dp[i] = len(c) - 1
else:
c[k:=bisect_left(c, s[i])] = s[i]
dp[i] = k
size, res = len(c) -1, []
for i in range(n-1, -1, -1):
if dp[i] == size:
res.append(s[i])
size -= 1
print(len(c) - 1)
print(*res[::-1])과정
- 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장한다.
- 별도의 재귀함수를 이용해 이 선택을 따라가면서 각 선택지를 저장하거나 출력한다.
JLIS (Jointed Longest Increasing Subsequence)
문제 요약
- 수열 $A$, $B$가 주어졌을 때, 각 수열의 LIS를 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가부분수열이라고 한다. A와 B가 주어졌을 때, 합친 LIS의 길이를 구하는 프로그램을 작성하라.
## INPUT 3 3 3 1 2 4 3 4 7 3 3 1 2 3 4 5 6 5 3 10 20 30 1 2 10 20 30
OUTPUT
5 (1, 2, 3, 4, 7)
6 (1, 2, 3, 4, 5, 6)
5 (1, 2, 10, 20, 30)
#### 아이디어 1
단순히 생각해서 A의 LIS를 구하고 B의 LIS를 구한다 라고 생각했는데 아래 테스트케이스에서 반례가 발생한다.A = [10, 20, 30, 1, 2]
B = [10, 20, 30]
LIS(A) = [10, 20, 30]
LIS(B) = [10, 20, 30]
JLIS(A,B) = [10, 20, 30] != [1, 2, 10, 20, 30]
따라서 다른 방법을 생각해봐야 한다.
#### 아이디어 2
우선 코드를 작성한다.
```python
A = [1, 2]
B = [4, 3]
dp = [[-1]* 10 for _ in range(10)]
def JLIS(indexA, indexB):
if dp[indexA+1][indexB+1] != -1:
print(f"JLIS({indexA}, {indexB})")
print(f"RET{dp[indexA+1][indexB+1]}")
return dp[indexA+1][indexB+1]
dp[indexA+1][indexB+1] = 2
a = -float('INF') if indexA == -1 else A[indexA]
b = -float('INF') if indexB == -1 else B[indexB]
maxElement = max(a, b)
print(f"JLIS({indexA}, {indexB})")
for nextA in range(indexA+1, len(A)):
if maxElement < A[nextA]:
print(f"A : dp[{indexA+1}][{indexB+1}], JLIS({nextA},{indexB})")
print()
dp[indexA+1][indexB+1] = max(dp[indexA+1][indexB+1], JLIS(nextA, indexB) + 1)
for nextB in range(indexB+1, len(B)):
if maxElement < B[nextB]:
print(f"B : dp[{indexA+1}][{indexB+1}], JLIS({indexA},{nextB})")
print()
dp[indexA+1][indexB+1] = max(dp[indexA+1][indexB+1], JLIS(indexA, nextB) + 1)
print(f"RET {dp[indexA+1][indexB+1]}")
return dp[indexA+1][indexB+1]
print(JLIS(-1, -1) - 2)
import pprint
pprint.pprint(dp)이 코드에서 확인을 위해 print 한 부분을 지우고, 입력 형식에 맞게 데이터를 수정하면 아래와 같다.
def JLIS(indexA, indexB):
if dp[indexA+1][indexB+1] != -1:
return dp[indexA+1][indexB+1]
dp[indexA+1][indexB+1] = 2
a = -float('INF') if indexA == -1 else A[indexA]
b = -float('INF') if indexB == -1 else B[indexB]
maxElement = max(a, b)
for nextA in range(indexA+1, len(A)):
if maxElement < A[nextA]:
dp[indexA+1][indexB+1] = max(dp[indexA+1][indexB+1], JLIS(nextA, indexB) + 1)
for nextB in range(indexB+1, len(B)):
if maxElement < B[nextB]:
dp[indexA+1][indexB+1] = max(dp[indexA+1][indexB+1], JLIS(indexA, nextB) + 1)
return dp[indexA+1][indexB+1]
for i in range(int(input())):
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[-1] * 101 for _ in range(101)]
print(JLIS(-1, -1) - 2)(그래도 많이 복잡하네...)
우선 점화식을 보자
$$\text{JLIS(indexA, indexB)}=max\begin{cases}max_{nextA \in\text{NEXT(indexA)}}\text{JLIS(nextA, indexB)+1}\\max_{nextB \in\text{NEXT(indexB)}}\text{JLIS(indexA, nextB)+1}\end{cases}
$$
두 수의 순서는 지정하지 않았으니, A[indexA]와 B[indexB] 중 작은 쪽이 앞에 온다고 하자.
그러면 이 LIS의 다음 숫자는 A[indexA+1] 또는 B[indexB+1] 이후의 수열 중 $max(\text{A[indexA], B[indexB]})$보다 큰 수중 하나가 된다.
예를 들면 테스트 케이스가 아래와 같이 있다고 할때
A = [1, 2]
B = [4, 3]$\text{JLIS(-1, -1)} = max
\begin{cases}
max_{1 \in [1, 2]}\text{JLIS(0, -1)+1}\\
max_{4 \in [4, 3]}\text{JLIS(-1, 0)+1}
\end{cases}$
이러한 과정을 반복한다. 이렇게 되면, 수열 A와 B에서 숫자를 하나씩 선택해 나갈 때 모든 경우의 LIS를 구할 수 있게 된다.
문제가 요구하는 것은 최대 길이니까, 길이를 저장해 DP 테이블에 넣으면 된다.
LIS를 응용했다고 하지만 사실 이해하기 많이 까다로웠다. 직접 과정을 손으로 따라가보면서 변태같이 해결하다보면 길이 나온다.
세그먼트 트리 이용하기 $O(N \log N)$
--------------------< 연구중 >---------------------
Inversion Counting
최적화 문제 동적 계획법 팁
- 모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전탐색 알고리즘을 설계한다.
- 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분문제의 정의를 바꾼다.
- 재귀 호출의 입력에서 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다.
문제에 최적부분구조가 성립할 경우 이전선택에 관한 정보를 모두 없앨 수 있다, - 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션 할 수 있도록 한다.
- 메모이제이션을 적용한다.
용어
- 최적 부분 구조
- DP의 가장 일반적인 사용처는 최적화 문제의 해결이다. 최적화 문제란 여러개의 가능한 답 중 가장 좋은 답을 찾아내는 문제를 의미한다.
- 최적화 문제에 특정 성질이 성립할 경우에는 메모이제이션 적용보다 효율적인 DP를 구현할 수 있다.
- 각 부분문제의 최적해만 있으면 전체 문제의 최적 해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립한다.
- 최적 부분 구조 문제는 대부분 직관적이나 직관적이지 않는 경우 귀류법 또는 대우를 이용하여 증명한다.
풀고싶은 문제
'알고리즘' 카테고리의 다른 글
| 2. 구현 (0) | 2023.05.11 |
|---|---|
| 1. 그리디 (0) | 2023.05.11 |
| 0. 알고리즘의 시작 (0) | 2023.05.11 |