[백준] 12015번 가장 긴 증가하는 부분 수열 2 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

https://www.acmicpc.net/problem/12015

• 도저히 구상할 수가 없어서 다른 코드를 참고하였다. 다른 코드를 보아도 왜 그런지 원리를 정확히 이해하는 것은 너무 어려웠다. 알고리즘을 적용시키는 스킬을 늘려주는 문제이다.

---

< 가장 긴 증가하는 부분 수열 2 > 

[문제]

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

[출력]

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력	예제 출력
6 10 20 10 30 20 50	4

---

아이디어

아무리 봐도 간단한 알고리즘조차 떠오르지 않았다. 진짜 '의외로 이분 탐색으로 풀 수 있는 놀라운 문제 2'라는 설명이 적절하다고 생각되었다. 다른 코드를 참고하여서 풀었다. 내가 설명하는 것보다 다른 사람이 친절히 설명한 글을 참고하면 더 좋을 것 같아서 내가 참고한 글의 링크를 남긴다.

https://rebro.kr/33

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열

실제의 가장 긴 증가하는 수열과는 다른 배열이 저장되지만, 그 길이는 같다는 것을 이용하여 풀었다.

풀이 및 코드

def bsIdx(lis, target):
    start = 0
    end = len(lis) - 1
    # 반환할 인덱스
    idx = -1
    while (start <= end):
        mid = (start + end) // 2
        # lis 배열의 값이 타겟보다 크거나 같으면 그 인덱스 저장 후 뒤의 배열 탐색
        if (lis[mid] >= target):
            idx = mid
            end = mid - 1
        # 작으면 앞의 배열 탐색
        else :
            start = mid + 1
    return idx

n = int(input())
array = list(map(int, input().split()))
# 첫 번째 수는 lis에 넣음.
lis = [array[0]]
# array의 모든 원소에 접근
for i in range(1, n):
    # 마지막 원소보다 크다면 lis에 추가
    if (lis[-1] < array[i]):
        lis.append(array[i])
    # 크지 않다면 lis의 알맞은 위치의 수와 바꿈.
    else :
        lis[bsIdx(lis, array[i])] = array[i]
# lis의 길이가 우리가 원하는 답
print(len(lis))

후기

가장 긴 증가하는 부분수열을 정확히 구하지 않아도 그 길이를 구할 수 있다는 것이 너무 신기했다. 여러번 곱씹으며 생각했는데 아직도 정확히 실제 lis와 우리가 저장한 lis의 길이가 같다는 것은 아직도 이해가 가지 않는다. 이걸 이렇게 적용할 수 있다는 것을 배웠다는 것에 의의를 두고 이분 탐색 알고리즘은 여기서 마무리하겠다.