BAEKJOON #12015 (이진탐색) - python

nathan·2021년 8월 5일
0

알고리즘문제

목록 보기
31/102

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

출처 : 백준 #12015

시간 제한메모리 제한
1초512MB

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.


입출력 예시

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4


풀이

생각

  • 전형적인 LIS(Longest Increasing Sequences) 문제이다.
  • 가장 긴 증가하는 부분 수열과 동일한 문제이나 주어지는 수열 A의 크기의 최댓값이 100만이다.
  • 따라서 DP로는 풀 수 없음이 자명하다. (O(N^2)의 시간 복잡도라서)
  • 이진탐색으로 이 문제는 접근해야 한다.

풀이 설명

가장 긴 증가하는 부분 수열 (DP 풀이) - O(N^2)

  • for 문을 두 개 돌면서 가장 바깥쪽 for 문의 현재 인덱스 i가 있는 위치보다 이전에 있는 인덱스들 (j)을 돈다.
  • 만약 i에 위치한 수가 j에 위치한 수보다 클 경우(오름차순이므로 커야 함)
    • dp[i] = max(dp[i], dp[j] + 1)
    • 위 식의 의미 :
      • dp[i]가 클 경우에는 과거 누적된 수가 많다는 말
      • dp[j]+1이 클 경우에는 새로운 수가 원래 dp에 추가 된다는 의미

가장 긴 증가하는 부분 수열 (이진탐색 풀이) - O(NlogN)

  • 임시로 값을 넣어줄 temp라는 리스트를 하나 만들고 그 안에 수열 첫 번째 값을 넣어준다.
  • for 문을 통해 수열을 탐색한다. (target은 수열 속의 값)
    • 그러는 중에 start = 0, end = len(temp)-1 을 정해놓고 이진탐색을 통해 temp안에서 target 값에 근접한 원소의 인덱스를 찾는다.
    • (start, end 둘 중 어느 것을 써도 상관 없음)
    • 결국엔 while문을 벗어나는 시점에는 start와 end가 겹치기 때문
  • while문을 벗어나면 temp의 마지막 원소가 target보다 작은지 확인한다.
    • 만약 target이 크다면, temp를 그대로 유지하고 끝에 붙임으로써 증가하는 부분수열이 완성될 수 있다.
    • 만약 target이 작거나 같다면, 끝에 붙인다고 해서 증가하는 부분수열이 될 수는 없으므로, 이전에 이진탐색으로 찾았던 인덱스 (start or end)에 target 값을 넣어준다.
    • 이렇게 넣어주더라도 temp의 길이에는 지장이 생기지 않고, 다음에 찾을 수열 값이 지금 넣었던 target과 더욱 가까울 때, 비교를 하더라도 이상이 생기지 않는다. (매우 중요 point!)
      • 예를 들어 target을 넣지 않았을 때, temp = [1, 2, 4, 7]이라고 해보자.
      • temp의 끝 값이 7이고 새로운 수열의 값이 6, target의 값이 5라고 해보자.
      • 그렇게 되면 temp에 target이 대체되지 않았다면, 새로운 수열의 값이 들어갈 자리가 없다.
      • 허나 temp[3] = target으로 대체가 된다면 새로운 수열의 값이 들어가게 되어 temp[1, 2, 4, 5, 6]으로 가장 긴 증가하는 부분수열을 완성할 수 있게 된다.

python code(Bottom UP)

# 백준 12015번 가장 긴 증가하는 부분 수열 2(이진탐색)
from sys import stdin
f = stdin.readline
n = int(f())
numbers = list(map(int, f().split()))

def solution(n, arr):
    temp = [arr[0]]

    for target in arr:  
        start = 0
        end = len(temp)-1    
        while start < end:
            mid = (start+end)//2
            if temp[mid] < target:
                start = mid + 1
            else:
                end = mid
        if temp[-1] < target:
            temp.append(target)
        else:
            temp[end] = target  # idx 값으로 start나 end나 상관 없음
    return len(temp)

print(solution(n, numbers))
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글