[Baekjoon] 백준 11053 가장 긴 증가하는 부분 수열(실버 2) - Python

문제설명

어떠한 수열을 입력받아 그 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제이다

예제를 통해 문제를 이해해보자면, 10 20 10 30 20 50 이 주어져있다

이 수열에서 증가하는 수열을 만들어본다고 생각해보자

제일 첫번째 10을 기준으로 삼으면 10 20 30 50이 나오고, 두번째 20을 기준으로 삼으면 20 30 50이 나온다

이러한 방식으로 증가하는 부분 수열을 만들었을때 가장 긴 부분 수열의 길이를 구하면 된다

 

이 문제를 풀기에 앞서 나무위키에서 부분 수열에 대해 찾아보았는데, 알고리즘 구현 방법까지 상세하게 나와있었다

그래서 이를 참고하여 그대로 코드를 작성하였다

간단하게 설명하자면 두 개의 리스트를 따로 만든후에, 입력받은 리스트의 index를 이동하면서 

더 작은 값을 저장하는 배열의 값보다 크다면 그 값을 추가적으로 저장하고, 배열의 값보다 작다면

배열을 이진탐색하여 해당 값을 넣어준다

 

말로만 하면 이해가 힘들기 때문에 예시를 통해 다시 설명하자면 10 20 15 30 25 50 이라는 배열이 주어져있다고 가정하자

따로 만들어야하는 두 개의 리스트의 이름을 편의를 위해 D와 min이라고 할 때, D와 min에는 0이 저장되어있다

이제 연산을 시작하면 index를 돌게되는데 index가 1일때의 값은 10이다

min의 제일 마지막 index의 값이 0과 비교하였을때 10이 더 크기 때문에 10을 추가적으로 저장하고,

D에는 이전 index의 값 + 1한 값을 추가적으로 저장한다(result[-1] + 1)

index가 2인 경우의 값은 20인데, min의 마지막 값과 비교하였을때 20이 더 크기 때문에 min에 20을 추가적으로 저장하고

D에도 +1한 값을 추가적으로 저장해준다

이후 index의 값이 5인데, 이 값은 min의 마지막 배열값보다 작다

그렇다면 이진탐색을 통해 min의 배열을 확인하여 더 작은 값을 저장해준다

이 상황에서는 min이 10 20에서 5 20으로 바뀌게 될 것이다

왜 바꾸냐면 현재 증가부분수열의 길이가 1인 수열중 끝이 10으로 끝나는 증가부분수열과 끝이 5로 끝나는

부분수열이 있기때문에 이 중에서 끝값이 더 작은 값을 저장하는 것이다

 

혹여나 말로만 설명하여 이해가 되지 않는 부분이 존재한다면 나무위키가 큰 도움이 될 것이다

이러한 방식으로 해당 문제의 코드를 작성하면

from bisect import bisect_left

length = int(input())
seq = (list(map(int, input().split())))

result = [0] # 최대 길이
min_seq = [0] # 작은 값 저장

for i in range(length):
    if seq[i] > min_seq[-1]:
        min_seq.append(seq[i])
        result.append(result[-1] + 1)
    else:
        pos = bisect_left(min_seq, seq[i])
        min_seq[pos] = seq[i]
        
print(len(min_seq) - 1)

이와 같은 형식이 되고 이를 제출하면 정답임을 확인할 수 있다