코드

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

# 처음에 0을 미리 넣어둠
d = [0]

for n in arr:
    
    # n이 DP 테이블의 맨 마지막 요소보다 크다면 DP에 추가
    # 증가하는 부분 수열을 구하므로 n은 오름차순으로 DP 테이블에 들어감
    if d[-1] < n:
        d.append(n)
        
    # n이 작거나 같다 => 증가하지 않는 것
    # 이진 탐색을 수행
    else:
        idx = binary_search(n)
        print(idx)
        d[idx] = n # 덮어씌여짐
        
# target이 DP 테이블의 마지막 요소보다 작거나 같은 경우에 동작
# DP 테이블 내에서 target의 인덱스를 반환해줌
# 만약 target이 DP 테이블에 존재하지 않으면 start를 반환해줌
def binary_search(target):
    start = 0
    end = len(d)
    
    while start <= end:
        mid = (start + end) // 2
        
        if d[mid] == target:
            return mid
        elif d[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start
        
# 처음 넣은 0이 있으므로 -1
print(len(d)-1)

문제 해설

LIS를 이분 탐색을 이용하여 푸는 문제.

DP를 이용한 LIS는 많이 접하여 이제 자신있게 풀 수 있었지만, 이 문제의 경우 기존의 DP 방식을 이용하면 시간 초과가 발생한다. 따라서 이 문제는 DP에 이분 탐색을 이용하여 해결해야 한다.

핵심 메커니즘은 아래와 같다.

  1. DP 테이블을 [0]으로 초기화 시킨다.
  2. 각각의 배열 요소를 DP 테이블의 맨 마지막 요소와 비교한다 (처음은 0)
    • 마지막 요소보다 값이 큰 경우, 해당 값을 DP 테이블에 추가한다.
    • 마지막 요소보다 값이 작은 경우, DP 테이블에서 주어진 값의 위치를 이분 탐색으로 파악하고, 그 값을 리턴한다. 이때, 값이 없다면 start의 값을 리턴한다.
      • 리턴 받은 위치에 해당하는 DP 테이블의 인덱스 요소(리턴한 값)에 배열의 요소를 넣어준다.

위의 과정을 거쳐서 최종적으로 0을 제외한 나머지 모든 숫자들이 LIS로 DP 테이블에 들어가는 것을 확인할 수 있다. 다양한 방법으로 같은 문제를 풀 수 있는 경우가 대단히 많은 것 같다. 많은 문제를 접하여 코딩 테스트에서 조금 더 수월한 해결 방안을 탐색할 수 있도록 열심히 훈련해야 겠다.

댓글남기기

참고