[파이썬/Python] 백준 12015번: 가장 긴 증가하는 부분 수열 2

📌 문제 : 백준 12015번

---

📌 문제 탐색하기

N : 수열 A의 크기 ($1 ≤ N ≤ 1,000,000$)
A : 입력받은 수열 ($1 ≤ Ai ≤ 1,000,000$)

문제 풀이

입력받은 수열에서 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다.

N과 A의 크기가 매우 크기 때문에 모든 부분 수열을 구하고 찾는 방식으로 푼다면 시간 초과가 발생할 것이다.

→ 최장 증가 부분 수열(LIS) 알고리즘을 활용한다.

⭐️ LIS (Longest Increasing Subsequence)

• 가장 긴 증가하는 부분 수열
• 구현 방법
  • DP 활용 (시간복잡도 : $O(n^2)$)
  • 이분탐색 활용 (시간복잡도 : $O(nlog n)$)

### DP 활용
dp = [1] * n
for i in range(n):
	for j in range(i):	# 첫번째 ~ i번째까지 비교
    	if arr[i] > arr[j]:	$ 뒤에 있는 값보다 크다면
        	dp[i] = max(dp[i], dp[k]+1)           

시간복잡도를 줄이기 위해 이분탐색 활용한 방법으로 문제를 푼다.

LIS 이분탐색 구현

• 수열 A의 값을 순서대로 접근
  • 수열의 값 > 현재 정답 리스트에 저장된 마지막 값
    • 증가하는 수 → 정답 리스트에 추가
  • 수열의 값 <= 현재 정답 리스트에 저장된 마지막 값
    • 들어갈 위치를 이분탐색으로 확인
• 이분 탐색 구현
  • 정답 저장 리스트 내에서 탐색
    • left, right = 0, len(answer)
  • 종료 조건
    • left가 right와 같거나 커지는 경우
  • 간격을 좁혀가며 해당 위치의 정답 리스트 값과 비교
    • 값 < a → left 값 증가 (더 큰 수로 이동)
    • 값 > a → right 값 감소 (더 작은 수로 이동)

가능한 시간복잡도

LIS 이분탐색 → $O(N log N)$

최종 시간복잡도
$O(N log N)$로,최악의 경우 $O(10^6 * log(10^6))$이 되어 제한 시간 1초 내에 연산이 가능하다.

알고리즘 선택

LIS를 이분탐색으로 구현해 탐색

---

📌 코드 설계하기

1. N 입력
2. 수열 A 입력
3. 정답 저장 리스트 정의
4. 이분 탐색 LIS 방법 적용
   4-1. 지금까지 저장된 수열의 마지막 값이 a보다 작다면 증가하는 중 = 추가
   4-2. 아니면 들어갈 위치를 이분탐색으로 확인
   4-3. 이분탐색 정의
5. 결과 출력

---

📌 시도 회차 수정 사항

1회차

• 인덱스 에러가 발생했다.
• 정답 리스트에서 얻은 위치의 값을 갱신하는 코드를 이분탐색 while문 내에 작성해서 발생한 문제이다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# 수열 A 입력
A = list(map(int, input().split()))

# 정답 저장 리스트 정의 (인덱스 계산 편리 위해 초기값 0)
answer = [0]

# 이분 탐색 LIS 방법 적용
for a in A:
    # 지금까지 저장된 수열의 마지막 값이 a보다 작다면 증가하는 중 = 추가
    if answer[-1] < a:
        answer.append(a)
    # 아니면 들어갈 위치를 이분탐색으로 확인
    else:
        left, right = 0, len(answer)    # 정답 리스트 내에서 탐색

        # 이분탐색 정의
        while left < right:
            mid = (left + right) // 2

            if answer[mid] < a:
                left = mid + 1      # a가 크면 왼쪽 이동
            else:
                right = mid      # a가 작으면 오른쪽 이동

        # 찾은 위치에 값 추가
        answer[right] = a

# 결과 출력
print(len(answer) - 1)

• 결과