[python]백준 11053번: 가장 긴 증가하는 부분 수열(LIS)

 

잘못된 풀이

처음에 이 문제를 봤을 때 부분 수열에만 집중하고 가장 긴 증가하는 부분 수열을 보지 못했다. 문제만 봤을 때는 순서 상관없이 증가하기만 하면 카운트해주면 되는구나 생각하고 코드를 작성했었다.

N = int(input())
list_ = list(map(int, input().split()))
result = []
for i in range(len(list_)):
  if i == 0:
    result.append(list_[i])
  elif list_[i] > list_[i-1]:
    result.append(list_[i])
print(len(result))

실제로 위와 같이 코드를 작성하게 되면 의도한대로 예제 출력과 같은 값이 나오고, result라는 리스트에는 순차적으로 증가하는 [10, 20, 30, 50]이 나오게 된다. 이렇게 제출해보니 실패가 나왔고, 부분 수열에 개념에 대해 부족한 나는 왜 틀렸는지 이해할 수 없었다.

가장 긴 부분 수열

여기서 핵심이 가장 긴 부분 수열이었다. 위와 같이 코드를 작성했을 때에 부분 수열이 되는 것은 맞지만, 그게 항상 가장 긴 부분 수열이라고 할 수는 없으며 증가하는 값을 모두 result에 넣게 되어 값이 엉뚱하게 나와버린다.

 

예를 들어 [10, 20, 50, 10, 20, 30, 40]이라고 할 때 내가 작성한 코드에 따르면 [10, 20, 50, 20, 30, 40]이 될 것이고 값은 6이 나올 것이다. 

 

때문에 가장 긴 부분 수열을 정확하게 구하기 위해 다음과 같이 2가지 방법을 사용할 수 있다.

1. Dynamic Programming (동적 계획법)

2. Binary Search (이분 탐색)

 

풀이

1. Dynamic Programming (동적 계획법)

N = int(input())

list_ = list(map(int, input().split())) # [10, 20, 50, 10, 20, 30, 40]

dp = [1 for i in range(N)] # [1, 1, 1, 1, 1, 1]

for i in range(N):
    for j in range(i):
        if list_[i] > list_[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

해설

list_[i] > list_[j]의 의미는 현재 위치 list_[i]보다 이전에 있는 값이 작은지 확인하는 로직이다. 수열이 되기 위해선 20이 10보다 작거나 같으면 안된다. if문이 충족된다면 아래 로직이 실행되고 dp값이 저장되게 되는데 예제에서 처럼 i가 0~5인 경우를 모두 정리해보았다.

i = 0이면 j값이 없으므로 기존의 1이 dp에 저장된다.

i = 1이면 j = 0이고 dp[1] = max(dp[1], dp[0]+1) 이므로 2가 된다.

i = 2이면 j = 0,1이지만 if문을 충족시키지 못하기 때문에 기존의 값인 1이 기록된다. 

i = 3이면 j = 0,1,2이고 dp[3] = max(dp[3], dp[0]+1) or max(dp[3], dp[1]+1) or max(dp[3], dp[2]+1) 가 반복되면서 max값을 dp에 저장하게 된다.

i = 4이면 j = 0,1,2,3이고 j = 1, 3은 if문을 충족하지 못하고 0, 2는 if문을 충족한다.
따라서 dp[4] =  max(dp[4], dp[0]+1) or max(dp[4], dp[2]+1)값을 저장하게 되고 dp[0]과 dp[1]은 1이므로 2값이 저장되게 된다.

i = 5이면 j = 0,1,2,3,4이고 모두 if문을 충족한다.
따라서 dp[5] = max(dp[5], dp[0]+1) or max(dp[5], dp[1]+1) or max(dp[5], dp[2]+1) or max(dp[5], dp[3]+1) or max(dp[5], dp[4]+1)값을 저장하게 되고 dp[3] +1인 4의 값이 dp[5]에 저장되며 가장 긴 부분 수열의 값이 나오게 된다.

list_	10	20	10	30	20	50
dp	1	2	1	3	2	4

하지만 위와 같이 풀게 되면 이중for문으로 모든 수를 다 살펴보기 때문에 O(N^2)의 시간복잡도를 가지게 된다.

 

풀이

2. Binary Search (이진탐색)

import bisect
N = int(input())
list_ = list(map(int, input().split()))

dp = [list_[0]]

for i in range(N):
    if list_[i] > dp[-1]:
        dp.append(list_[i])
    else:
        idx = bisect.bisect_left(dp, list_[i])
        dp[idx] = list_[i]

print(len(dp))

해설

알고리즘 문제의 최적화(?)된 python에는 bisect라는 내장모듈이 들어있다. bisect는 이진 탐색을 쉽게 구현하게끔 해주는 모듈이다. 참고로 bisect를 쓰기 위해서는 리스트가 오름차순으로 정렬되어 있어야 한다.

 

bisect_left(literable, value) -> value값을 삽입할 인덱스 반환(최소)

bisect_right(literable, value) -> value값을 삽입할 인덱스 반환(최대)

 

예제

from bisect import bisect_left, bisect_right

list_ = [4, 5, 5, 5, 5, 5, 5, 5, 5, 6]
target = 5

print(bisect_left(list_, target))
print(bisect_right(list_, target))

'''
결과값
1
9
'''

target 5를 bisect_left를 사용하면 4, 5사이인 인덱스 1의 값이 나오고

target 5를 bisect_right을 사용하면 5, 6사이인 인덱스 9의 값이 나오게 된다.

 

처음 내가 잘못 접근했던 방식을 bisect을 사용하면  예외없이 구현할 수 있다.

import bisect
N = int(input())
list_ = list(map(int, input().split()))

dp = [list_[0]] # [10]

for i in range(N):
    if list_[i] > dp[-1]:
        dp.append(list_[i])
    else:
        idx = bisect.bisect_left(dp, list_[i]) # list_[i]값을 dp리스트 안에 삽입한 인덱스 값이 idx
        dp[idx] = list_[i] # list_[i]값을 dp[idx]에 저장

print(len(dp)) # dp = [10, 20, 30, 50]

1. dp를 list_[0]으로 초기화한다.

2. 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가한다.

3. 현재 위치(i)가 이전 위치의 원소보다 작거나 같으면, bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index값을 구한다. 그리고 dp의 index 원소를 list_[i]로 바꿔준다.

4. dp의 길이를 출력한다.

 

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

11053번: 가장 긴 증가하는 부분 수열