[백준 알고리즘] - 가장 긴 증가하는 부분 수열 2 (12015번) with Python

📎 간략한 문제 정리

• 주어진 수열에서 요소가 오름차순이 되는 부분 수열 중 가장 길이가 긴 부분 수열의 길이를 구합니다.

📈 문제 분석

• DP에서 가장 유명한 문제 중 하나로 일반적으로 DP로 해결합니다. 하지만 이 문제는 DP로 풀 경우 속도 이슈가 발생합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [1 for _ in range(N)]
for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[j]+1, dp[i])
print(max(dp))

💻 풀이한 코드

from sys import stdin
from bisect import bisect_left
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
ascending_partial_sequence = [A[0]] # 1< N 이므로 오류 발생 안함
for element in A:
    if ascending_partial_sequence[-1] < element:
        ascending_partial_sequence.append(element)
        continue
    index = bisect_left(ascending_partial_sequence, element)
    ascending_partial_sequence[index] = element
print(len(ascending_partial_sequence))

📝 해결 과정에서 만난 문제, 고민들

• 주어진 조건은 1,000,000 이하로 O(NlogN) 이내의 속도로 풀어야합니다. 하지만 전형적인 DP 방식은 O(N^2)로 당연히 오류가 발생합니다.

• 이 문제 풀이의 포인트는 2가지 입니다.

  1. bisect_left의 의미
  2. 부분 수열의 요소들을 정확히 알 필요가 없다.

  우선 1번을 설명하기 위해 필요한 것은 bisect가 무엇인지입니다. bisect는 파이썬의 라이브러리로 이분 탐색 기능입니다. 이분 탐색에 대한 자세한 설명은 문제 해설의 범위를 넘어서기 때문에 생략하겠습니다. 중요한 것은 O(logN)의 속도로 특정 위치를 찾는데 그 위치는 어떤 값이 배열의 오름차순을 깨지 않는 상태를 유지하는 위치를 의미합니다.

  예를 들어 설명해보겠습니다.

  [10, 20, 40, 70]

  의 배열이 존재합니다. 여기에 50이라는 숫자를 넣고 싶은데 오름차순을 유지하려면 어디에 들어가야할까요? 당연히 40과 70 사이입니다. 이것을 첫 요소부터 순회하며 50과 비교할 수 있지만 이렇게 되면 O(N)의 속도가 나옵니다. 비효율적인 속도입니다. 이것을 binary search를 통해 탐색하면 O(logN)의 속도로 적합한 위치를 반환해줍니다.

  여기서 bisect는 bisect_left, bisect_right이 있습니다. 이름에서 유추 가능하지만 left는 오름차순이 유지 될 수 있는 위치 중 가장 왼쪽, right은 오른쪽입니다. 모든 요소에 중복이 존재하지 않는다면 당연히 두 메소드의 결과는 같습니다. 위의 예시에서는 어떤 메소드를 써도 40과 70사이의 값이 나옵니다.

  하지만 아래 예시를 보겠습니다.

  [10, 20, 20, 40, 70]

  이런 수열이 존재할 때 20을 넣는다면 20은 사실 인덱스 1, 2, 3 어디에 들어가도 상관이 없습니다. 이 때 bisect_left는 1을, bisect_right은 3을 반환합니다. 그러면 이 문제에서 bisect_left가 갖는 의미는 무엇일까요?

  다시 한번 예시를 들어보겠습니다.

  [10, 20, 10, 30, 50, 40]

  이런 배열이 존재할 때

  index = bisect_left(ascending_partial_sequence, element)
  ascending_partial_sequence[index] = element

  로직이 의미하는 바를 살펴보겠습니다.

  우선 정답 로직을 따라가보면 ascending_partial_sequence(이하 aps)는 다음과 같이 진행됩니다.

  [10]

  [10, 20]

  이 다음 element는 10이 됩니다. 이 때 만약 bisect_right을 사용하면 어떤 일이 발생할까요? 당연히 결과는 1이 나오고 바로 위의 로직 부분에 의해 aps는 [10, 10]이 됩니다. 하지만 조건에 의해 이 수열은 증가하는 수열이 아닙니다. 당연히 원하는 값은 [10, 20]이 유지되어야겠죠. 하지만 이 부분을 유지한다의 개념이 아니라 bisect_left를 사용하므로써 기존 10이 새로운 element 10으로 대체되게 만듭니다. 같은 10이지만 사실상 새로운 할당이 되는 것이죠. 중요한 것은 오름차순이 유지되는 것이니까요!

  2번째인 요소가 중요하지 않다는 의미는 무엇일까요?

  위의 예시를 이어서 살펴보겠습니다.

  aps를 추적해서 element가 50까지 왔다면

  [10, 20, 30, 50]

  상태가 됩니다.

  여기서 사실 40은 50보다 작기 때문에 이 상태로 완결되어도 상관이없는데 로직에 따라

  [10, 20, 30, 40]

  으로 교체됩니다. 즉, 요소의 값 자체가 중요하지 않다는 점과 중복은 같은 값으로 대체된다는 특성을 이용해서 간단하게 로직을 조건없이 구현할 수 있었습니다.

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