12015_가장 긴 증가하는 부분수열 이해가 안된다면?

문제는 더보기!

 

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

23852

9777

6794

42.735%

문제

수열 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

 

 

예전에 가장긴 증가하는부분수열을 푼 적이 있다. 해당 문제의 dp를 사용한 해법을 한번 봐야 풀 수 있는 문제이다.

 

푸는 방법은 똑같으나 케이스가 많아 이분탐색을 이용해 시간을 많이 줄이는게 핵심이다.

 

자, 10 20 10 30 20 50 이 순서대로 케이스에 들어온다고 생각해보자.

 

우선 dp는 [0]으로 시작한다고 생각하자.

 

여기서 dp는 일종의 부분수열을 만들었다고 보면된다. 자 우리는 첫번째 숫자로 10을 받았다. 10은 0보다 크기에 index 첫번째에 들어와야할 것이다. 그렇기에 해당 10을 append해주면 된다.

 

그러면 우리 dp는 [ 0 , 10 ] 이 되어있을 것이다.

 

20이 들어왔을때도 똑같다. 20이 dp에 들어온다면 index두번째에 들어와야하기에 [ 0 , 10 , 20 ] 이 되어있을 것이다.

 

이다음케이스에서 10이 들어왔다. 10은 dp에 들어온다면 index 첫번째자리에 들어와야한다. 그렇기에 이 첫번째 자리를 대체하는것이다. 

 

 

만약 5가 들어온다면 어떻게 될까?

 

5가 만약 들어온다면 0과 10사이에 들어와야한다고 생각할 수 있는데, 그러면 배열크기가 증가하게 되므로 안된다. 즉, 0보다 큰 10을 대체하여 5가 들어가게된다.

 

만약 5가 이타이밍에 들어온다면 배열은 [ 0 , 5, 20 ] 이 될 것이다.

 

그렇다. 이는 정답인 부분수열과는 다를 수 있다. 그래서 부분수열의 개수는 구할수 있지만 부분수열 자체는 구할 수 없는 알고리즘이다.

 

잘이해가 되지않는다면 아래 코드의 print주석을 빼보고 

 

6
10 20 10 30 20 50

 

6

10 20 6 7 8 9

 

위와같은 케이스들을 보면서 이해하면 잘 될것이다.

 

n = int(input())
lst = list(map(int,input().split()))

start,end = 1,n
dp = [0]

for i in range(n):
    start,end = 0,len(dp)-1

    while start<=end:
        mid = (start + end) //2
        # print('start',start,'end',end,'mid : ',mid)
        if dp[mid] <lst[i]:
            start = mid + 1
        else:
            end = mid -1
    if start >= len(dp):
        dp.append(lst[i])
    else:
        dp[start] = lst[i]
    # print(dp)

print(len(dp)-1)

 

 

인터넷 검색을 해보다 보니 bisect라는 이분탐색 모듈이 있다고 한다. 이를 활용하면 좀더 깨끗하게 만들 수 있다

 

from bisect import bisect_left

n = input()
lst = list(map(int,input().split()))
dp = []

for i in lst:
    k = bisect_left(dp,i)
    if k > len(dp):
        dp.append(i)
    else:
        dp[k] = i

print(len(dp))