[백준] 12015 가장 긴 증가하는 부분 수열 2 (파이썬 python)

2024. 4. 17. 19:02· Algorithm/BOJ
목차
  1. 문제 링크
  2. 문제 풀이

 

 

문제 링크

 

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

 

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

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

 

 

 

문제 풀이

 

LIS 알고리즘은 보통 dp를 사용해서 수열의 길이를 갱신하는 방식으로 구현하며,

시간복잡도는 O(n^2)가 됩니다.

이 문제에서는 수열의 길이가 100만까지로 크기 때문에 기존 방식을 활용하면 시간 초과가 나게 됩니다.

시간을 단축하기 위해 이분 탐색을 활용하여 알고리즘을 구현할 수 있습니다.

이 경우에는 O(nlogn)의 시간복잡도를 띄게 됩니다.

 

알고리즘 방식은 다음과 같습니다.

일단, 기본값으로 0이 포함된 arr 배열을 만들어줍니다.

dp 방식과 같이 입력받은 배열을 앞에서부터 하나씩 확인합니다.

확인한 숫자가 arr 배열의 마지막 값보다 클 경우 바로 배열에 추가해줍니다.

작을 경우, 이분탐색을 통해 arr 배열에서 현재 숫자가 위치할 index를 찾아준 후

해당 인덱스에 해당하는 값과 대치시켜줍니다.

이 과정을 배열을 모두 확인할 때까지 반복해주면, arr 배열에는 가장 긴 증가하는 부분수열이 보여집니다.

 

처음에는 숫자가 작을 경우 이분 탐색으로 index를 찾아 그 위치에 대치시키는 과정이 이해되지 않았으나,

예시를 통해 이해했습니다.

만약 입력받은 배열이 [1, 2, 5, 6, 3, 4]라고 합시다.

6까지는 무난하게 arr 배열에 순서대로 추가될 것입니다.

3을 확인하면 arr 배열의 마지막 숫자인 6보다 작으므로

이분탐색을 통해 위치할 인덱스를 찾고 대치시켜줘야 합니다.

이때 3이 위치할 인덱스는 2입니다.

그러면 arr 배열은 [1, 2, 3, 6]이 됩니다.

입력받은 배열의 마지막 값인 4를 확인할 때도

마찬가지로 위치할 인덱스인 3에 해당하는 6과 대치되어 결론적으로 arr 배열은 [1, 2, 3, 4]가 됩니다.

이렇게 작은 숫자를 기존 숫자와 대치시키는 이유는

숫자가 작을 수록 다음에 추가될 수 있는 숫자의 범위가 커지기 때문입니다.

마지막 숫자가 6이라면 이후에 추가될 숫자의 범위는 7 이상이 됩니다.

마지막 숫자가 4라면 그 범위는 5 이상이 됩니다.

따라서, 배열의 값이 작을 수록 더 많은 숫자값을 수열에 추가할 수 있게 되는 것입니다.

 

def binary_search(num):
    start, end = 0, len(arr)
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] < num:
            start = mid + 1
        else:
            end = mid - 1
    return start


n = int(input())
a = list(map(int, input().split()))
arr = [0]
for i in range(n):
    if arr[-1] < a[i]:
        arr.append(a[i])
    elif arr[-1] > a[i]:
        idx = binary_search(a[i])
        arr[idx] = a[i]

print(len(arr) - 1)
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[백준] 4803 트리 (파이썬 python)  (0) 2024.04.18
[백준] 1253 좋다 (파이썬 python)  (1) 2024.04.18
[백준] 7682 틱택토 (파이썬 python)  (0) 2024.04.17
[백준] 1261 알고스팟 (파이썬 python)  (0) 2024.04.15
[백준] 11808 스티커 붙이기 (파이썬 python)  (0) 2024.03.28
  1. 문제 링크
  2. 문제 풀이
'Algorithm/BOJ' 카테고리의 다른 글
  • [백준] 4803 트리 (파이썬 python)
  • [백준] 1253 좋다 (파이썬 python)
  • [백준] 7682 틱택토 (파이썬 python)
  • [백준] 1261 알고스팟 (파이썬 python)
YOONJELLY
YOONJELLY
YOONJELLY
JELLYJELLY
YOONJELLY
전체
오늘
어제
  • 분류 전체보기 (153)
    • Springboot (2)
    • Android (15)
    • Algorithm (126)
      • 개념 (8)
      • BOJ (91)
      • Programmers (15)
      • SWEA (4)
    • 경험_기록 (1)
    • RIM_TIP (4)
    • Github (2)
    • CS (1)
      • 운영체제 (1)
      • 컴퓨터네트워크 (0)
      • 정보처리기사 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Android
  • 완전탐색
  • kotlin
  • 정렬
  • 코딩테스트
  • 이진탐색
  • BFS
  • 문자열
  • DP
  • softeer
  • 그리디
  • Python
  • 안드로이드
  • 이것이코딩테스트다
  • 백준
  • 다이나믹프로그래밍
  • 알고리즘
  • BOJ
  • 딕셔너리
  • SWEA
  • 자료구조
  • 파이썬
  • 소프티어
  • 큐
  • programmers
  • 프로그래머스
  • DFS
  • 코틀린
  • 스택
  • 액티비티컴포넌트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
YOONJELLY
[백준] 12015 가장 긴 증가하는 부분 수열 2 (파이썬 python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.