알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/12015
SOLVE 1
이분 탐색 직접 구현
import sys
input = sys.stdin.readline
N = int(input())
A = [*map(int, input().split())]
LIS = [A[0]]
def findPlace(e):
start = 0
end = len(LIS) - 1
while start <= end:
mid = (start + end) // 2
if LIS[mid] == e:
return mid
elif LIS[mid] < e:
start = mid + 1
else:
end = mid - 1
return start
for item in A:
if LIS[-1] < item:
LIS.append(item)
else:
idx = findPlace(item)
LIS[idx] = item
print(len(LIS))SOLVE 2
bisect 모듈 활용
import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input())
A = [*map(int, input().split())]
LIS = [A[0]]
for item in A:
if LIS[-1] < item:
LIS.append(item)
else:
idx = bisect_left(LIS, item)
LIS[idx] = item
print(len(LIS))풀이 요약
- 이 문제는 LIS 문제와 상당히 유사해보이지만, DP를 활용한 LIS 알고리즘을 활용할 수는 없는 문제이다. N이 까지인데, LIS 알고리즘은 O()이기 때문이다.
- 핵심은, 수열 A를 처음부터 끝까지 for를 돌면서 원소를 이용하여 배열 LIS를 만드는데, 이 리스트 LIS의 원소들은 A의 "가장 긴 증가하는 부분 수열"을 만족하지는 않지만, 이 리스트 LIS의 길이 값 자체만은 A의 "가장 긴 증가하는 부분 수열" 조건을 만족한다는 것을 이해하는 것이다.
-
대략적인 흐름은 이렇다.
-
LIS 리스트를 새로 만든다. 여기에는 A[0] 하나가 들어가 있다.
-
for로 A의 요소를 돌면서(item으로 두자), item이 LIS의 마지막 원소보다 크면 바로 LIS에 넣어주고, 작거나 같으면 findPlace로 item을 넣을 인덱스를 찾고 거기에 넣어준다. 이걸 끝까지 반복하면, LIS 리스트는 실제 LIS는 아니지만 "길이" 값 만큼은 조건을 만족하기에, len(LIS)를 print해준다.
-
-
그럼 이제 세부적으로 살펴보자.
-
item이 LIS의 마지막 원소보다 작거나 같을 때, findPlace를 호출해서 item을 넣을 LIS의 idx 자리를 구한다. 왜? 그리고 findPlace가 뭐하는 함수인데?
[10, 20, 10, 30, 25, 50]
이 걸 예로 살펴보자.
처음에 LIS = [10]이다.
이제 for 돌면서 LIS를 채우자. A의 다음 원소 20은 LIS의 마지막 원소 10보다 크므로, 그냥 넣어준다.
이렇게 LIS의 길이는 2가 되었다.그 다음 A의 원소는 10이다. LIS의 마지막 원소 20보다 작거나 같으므로, findPlace로 넣을 인덱스를 찾는다. 이 때,
findPlace는 LIS의 왼쪽부터 탐색을 시작해서, item보다 크거나 같은 원소를 처음으로 만났을 때의 인덱스를 반환한다.그래서 findPlace(10)은, LIS에서 10 이상의 수는 LIS[0]인 10이므로, 0을 반환해서 idx = 0 이고, LIS[idx] = item 이렇게 찾은 인덱스 자리에 item을 넣어준다.
계속 진행해보자. 다음 A의 원소는 30이다. LIS의 마지막 원소 20보다 크므로 그냥 넣어준다. 현재 LIS = [10, 20, 30]이고 길이 3이다.
다음 A의 원소는 25이다. LIS의 마지막 원소 30보다 작거나 같으므로 findPlace로 item(25)를 LIS에 넣을 자리 idx를 찾는다.
findPlace 내부에서 수행하는 것을 따라가보자. LIS의 왼쪽에서부터 시작해서, item보다 크거나 같은 수가 나올 때까지 탐색하자. 그 수는 바로 30이다. 따라서 인덱스 2를 반환하고, LIS[2] = item으로 바꿔준다.
왜 이렇게 바꿔줄까?
만약 [10, 20, 60, 30, 40]의 경우에, 처음부터 마지막까지 순차 탐색하면서 단순 크기 비교만 하면서 LIS를 만든다면, [10, 20, 60]이 나올텐데, 사실 LIS 길이는 4이고, [10, 20, 30, 40]이 구하는 답이다. 여기서, 60 다음 30을 탐색할 때, 60보다 작다고 버리지말고, 이전의 만들어놓은 LIS에서 30 이상의 수를 30으로 대체해주면, 그 다음 탐색부터 60이었을 때보다 더 많은 수를 받아들일 수 있게 된다. 예를 들어 40 같은 경우말이다. 한편 주의할 것이 있다.
A = [10, 20, 30, 15, 50]
이 리스트에 대해 LIS를 위에서 설명한 로직으로 구해보면, [10, 15, 30, 50]이 나온다. 근데 이건 A에서 나올 수 없는 부분 수열이다. 15가 30 앞에 있는걸 봐보면 안다.
하지만 findPlace를 통해 item을
LIS의 처음으로 등장하는 item보다 크거나 같은 수와 교체해줬을 때, 길이 자체는 변하게 하지 않으면서, 20을 15로 바꿔주기만 하면서 뒤에 남은 탐색할 수들을 최대한 많이 담을 수 있도록 함이 목적이고, 이 때 15는 그냥 20이 담겨있는 것으로 취급해도 된다.이해가 안될 것 같아 한번 더 설명해본다. 다시 [10, 20, 60, 30, 40]를 살펴보면, LIS = [10, 20, 60]이고 현재 item = 30인 단계일 때, 위에서 설명한 로직대로 60을 30으로 바꿔주게 된다. 이 때, 30을 60 자리에 바꿔넣었다고 해서, 구하는 정답인 길이 값 규칙에 위배되지 않는다. 그 뒤에 만약 60보다 큰 수들이 들어오면, 60 자리에는 30이 있으나 60이 있으나 상관없다. 만약 30보다는 크고 60보다 작은 수가 들어오면, 저 자리에 60이었을 때는 그 수를 안넣었을텐데 그 자리에 30이 있으니, 그 수를 LIS에 넣게 된다. 이런 경우에는 60 자리에 30이 있는게 더 이득인 셈이 된다. 이러나 저러나, 60 자리에 30을 넣는게, 구하고자 하는 길이 값을 찾는데 무조건 이득이다. 사실 내가 쓰면서도 뭔 말을 하고 있는건지 모르겠다... 말로 설명하려니 너무 어렵다..
-
- findPlace 함수를 구현하지 않고 bisect 모듈을 활용할 수도 있다. bisect 모듈 활용에 대해서는 이 곳에 잘 정리돼있으니 참고하자. 다른 블로그 글이다.
배운 점, 어려웠던 점
- 이 문제도 말로 설명하려니 너무 어렵다.. 풀 때도 어려웠는데, 애초에 LIS 알고리즘은 쓰지도 못하는 문제였고, 완전히 다른 알고리즘을 구상하고 풀어야되는 문젠데,
그 원소가 LIS 조건을 만족하지는 않을 수도 있지만, 그 길이 값 자체는 LIS 조건을 만족하는 리스트를 구해서 푼다라는 개념을 이해 및 떠올리기가 상당히 어려웠다.
