가장 긴 증가하는 부분 수열 2 [백준 12015] - python

 

결국 풀지 못했다. 

다음번에 틀리지 않기 위해 기록해두자!

설명이 정말 잘되어 있는 블로그를 찾았다. 해당 블로그를 보고 이해한 내용을 정리해두자!

 

정답코드 먼저 살펴봅시다

import sys
from bisect import bisect_left

def find(target):
  start, end = 1, len(dist) - 1
  while start < end :
    mid = (start + end) // 2
    if dist[mid] < target :
      start = mid + 1
    elif dist[mid] > target :
      end = mid
    else :
      start = end = mid
  return end


n = int(input())
array = list(map(int, sys.stdin.readline().split()))
dist = [0]

for i in array :
  if dist[-1] < i :
    dist.append(i)
  else :
    dist[find(i)] = i
    # dist[bisect_left(dist, i)] = i

print(len(dist) - 1)

 

가장 긴 증가하는 부분 수열 1 문제는 dp로 간단하게 풀수 있다. 

이 문제는 범위가 훨씬 넓다. 1번에서 풀었던 방식으로 시도했더니 시간 초과로 풀지 못해버렸다.

 

이분 탐색을 곁들인 위의 코드를 단계별로 살펴봅시다

우리는 O(nlogn)에 끝내버릴 것입니다

 

입력 예시 하나를 살펴보자

8
10 20 30 5 10 20 30 40

우선 거리 배열을 하나 둡니다

이 거리 배열을 업데이트 하면서 정답에 접근해보겠습니다.

 

0

10

20

30

10, 20, 30 까지는 증가하는 수열이다. 위의 예시는 쉽게 이해가 될거에요

5를 비교해야 할때 이슈가 발생합니다.

 

0과 10사이에 값을 넣어주어야 하나?? 어떻게 해야할까 혼란스러울 겁니다.

이전까지 구한 최장 길이는 건드리지 않으면서 값만 바꿔주어야 해요.

 

비교하는 값이 거리배열에서 들어갈 수 있는 인덱스를 구해서 그 값과 바꿔주면 됩니다.

 

* 5를 비교할 차례

0

5

20

30

5를 10과 바꾸어주면 현재까지 구한 최장길이는 바뀌지 않으면서 비교하는 값만 적절한 위치에 넣어주었습니다.

이 적절한 위치를 찾을때에 이분탐색을 사용합니다. (직접 코드로 구현하거나 bisect_left 이용)
코드를 살펴보면 두개의 방법 전부 추가해 두었습니다

* 이진탐색을 살펴보는 경우는 따로 포스팅 하겠습니다

 

5의 경우와 같이 하나씩 갱신해 줍시다.

* 10을 비교할 차례

0

5

10

30

* 20을 비교할 차례

0

5

10

20

* 30을 비교할 차례

30을 비교할 차례인데 30은 기존의 거리배열중 최댓값보다 큽니다. 끝에 붙여주면 됩니다

0

5

10

20

30

* 40을 비교할 차례

0

5

10

20

30

40

 

 

출처: https://suri78.tistory.com/199

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