알고리즘 유형 : DP(Dynamic Programming), 최단경로 역추적
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/14003
소스 코드(파이썬)
import sys
from bisect import bisect_left
input = sys.stdin.readline
# O(NlogN) 풀이
N = int(input())
A = [0] + [*map(int, input().split())] # 수열 입력 받기
LIS_list = [-float("inf")] # 길이만 만족하는 리스트. LIS 아님
# index에 대해, A[index]가 반드시 마지막
# 원소일 때의 LIS 길이 값 리스트
LIS_value = [1]*(N+1)
for idx in range(1, N+1):
if LIS_list[-1] < A[idx]:
LIS_list.append(A[idx])
LIS_value[idx] = len(LIS_list) - 1
else:
move = bisect_left(LIS_list, A[idx])
LIS_list[move] = A[idx]
LIS_value[idx] = move
order_top = len(LIS_list) - 1
print(order_top)
# 최단경로 역추적
# LIS_value 리스트 활용. 이 리스트의 인덱스는 A의 원소 인덱스를,
# 원소는 그 원소의 인덱스까지의 A를 활용하여 만들 수 있는
# LIS 길이 값을 의미
# 만약 A의 최종적인 LIS 길이 값이 K라면, LIS_value에는
# 반드시 1~K의 값이 모두 들어있고, 이를 활용하여
# 그 값의 인덱스를 A와 매칭하여 실제 LIS를 구할 수 있음.
result = []
for idx in range(N, 0, -1):
if LIS_value[idx] == order_top:
result.append(A[idx])
order_top -= 1
print(*result[::-1])풀이 요약
-
앞서 LIS 문제들에서 사용한 로직을 생각해보자.
가장 긴 증가하는 부분 수열 1 에서는 O()의 풀이를 작성하였다. 전체 문제를
현재 원소가 마지막 원소일 때의 LIS 길이 값으로 설정하고, 이 값들을 가지는 리스트의 max 값을 정답으로 취하는 로직이었다.직접적으로 LIS를 구하진 않고, LIS의 길이 값만을 다루는 풀이이다.
가장 긴 증가하는 부분 수열 2 에서는 O(NlogN)의 풀이를 작성하였다. 첫 번째 원소로부터 범위를 한 칸씩 늘려가면서 리스트를 만든다. 단, 이 때 만드는 리스트는 LIS가 아니고 길이만 만족하는 유사 LIS였다.
어떤 원소를 현재 리스트에 바로 추가할 수 없을 때,
이분 탐색으로 자신이 어떠한 위치에서 원래 그 자리에 있던 원소보다 작고, 그 이전의 원소보다는 자신이 클 때, 그 위치에 자신을 대체자로 들어가는 식으로 진행했고 마지막에 만든 리스트의 길이 값을 출력했다.길이만 만족하는 유사 LIS를 만드는 풀이였다.
가장 긴 증가하는 부분 수열 4 에서는 LIS 알고리즘으로 메모이제이션 리스트를 구하고, 그 리스트의 마지막 원소부터 for를 돌면서, LIS 길이 값을 만족하는 인덱스에 대해 해당 인덱스의 A 리스트의 원소 값을 result에 append하고, LIS 길이 값 order를 1 줄여서 또 인덱스를 찾아가는 로직으로 LIS를 구했었다.
-
이제 이 문제의 풀이를 생각해보자. 일단 조건 범위를 봤을 때 O() 풀이로 풀 수는 없다는걸 알 수 있다.
그렇다면 O(NlogN) 풀이를 채택할만한데, 가장 긴 증가하는 부분 수열 4 에서는 O() 풀이에 역추적을 섞은 풀이였다.
그렇다면 이 문제에서는 O(NlogN) 풀이에 역추적을 섞어서 풀어볼 생각을 해볼 수 있겠다.
-
그런데 O() 풀이에서는 메모이제이션 리스트 mem에 대해, 그 원소를
mem의 index에 대해, A[index]가 반드시 마지막 원소로 들어갈 때의 LIS 길이 값로 정했었다.그리고 이 리스트를 활용하여 역추적을 할 수 있었다.
반면 가장 긴 증가하는 부분 수열 4 에서의 O(NlogN) 풀이는 그런 메모이제이션 리스트를 만들지않고, 유사 LIS 리스트를 할당한 뒤에 A를 순회하면서 각 원소를 유사 LIS 리스트에 길이 조건만 만족하도록 적당한 위치에 이분탐색으로 끼워넣는 식으로 진행한 후, 이 리스트의 길이 값을 출력했었다.
따라서 역추적을 위해 O() 풀이에서 구했던 메모이제이션 리스트를 도중에 같이 만들어주면 되겠다.
O(NlogN) 풀이를 살펴보면, A를 순회하면서, 순회 중 원소 e를 유사 LIS 리스트에 이분탐색으로 끼워넣을 때 LIS 조건에 부합하도록 끼워넣기 때문에, 매 단계에서 e가 마지막 원소일 때의 LIS 길이를 구할 수 있게되므로 구현 가능한 부분이다.
-
1부터 N번째 인덱스까지 A를 순회한다. 만약 유사 LIS 리스트인 LIS_list의 마지막 원소보다 크다면, 오른쪽에 바로 붙혀주고, 해당 원소가 마지막 원소일 때의 LIS 길이 값은 그 때의 LIS_list의 길이 값과 같다.
만약 작거나 같다면, 이분 탐색으로 적절한 위치를 찾아서 바꿔 넣어주고 그 위치에 해당하는 인덱스(LIS_list의 유효한 원소는 1부터 시작하므로, 인덱스가 곧 그 자리까지의 원소 개수를 의미)를 LIS_value에 넣어준다.
여기서 적절한 위치란, 어떤 수 e에 대해 e의 왼쪽에 해당하는 LIS_list의 부분 배열에서 자신보다 작은 원소 중 가장 큰 값의 index에 대해, index+1의 위치이다.
- 이 후 order_top을 출력해주고, LIS_value를 역방향으로 순회하면서 order_top, order_top-1, order_top-2에 해당하는 원소의 index를 A와 매칭하여 실제 LIS를 완성해나가면 된다.
배운 점, 어려웠던 점
-
LIS 알고리즘을 전체적으로 정리해볼 수 있는 시간이었다.
O() 풀이와 O(NlogN) 풀이의 차이점, 역추적을 위해 어떤 값이 필요한지를 파악할 수 있었고, 이를 O(NlogN) 풀이에 섞는 방법을 배웠다.
