[python] 이분 탐색 / Binary Search / LIS / 가장 긴 증가하는 부분 수열 / 직접 구현 / bisect
[유형]
효율성을 체크하는 문제 / DP로 풀었을 때 시간 초과가 나는 문제 / (정렬된) 배열 안에서 특정 값을 찾는 문제
[대표 문제]
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
https://programmers.co.kr/learn/courses/30/lessons/64062
코딩테스트 연습 - 징검다리 건너기
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3
programmers.co.kr
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
1. bisect 사용
파이썬 표준 라이브러리인 bisect를 이용한다.
from bisect import bisect, bisect_left, bisect_right 를 통해 불러올 수 있다.
- bisect.bisect(a, x) : 오름차순으로 정렬된 리스트 'a'에 value 'x'가 삽입 될 가장 오른쪽 index를 리턴한다.
- bisect.bisect_left(
a, x
) : 오름차순으로 정렬된 리스트 'a'에 value 'x'가 삽입 될 가장 왼쪽 index를 리턴한다.
- bisect.bisect_right(a, x) : 오름차순으로 정렬된 리스트 'a'에 value 'x'가 삽입 될 가장 오른쪽 index를 리턴한다.
* 가장 오른쪽, 가장 왼쪽을 나누는 이유 : 삽입할 값인 x와 동일한 값이 리스트 a에 이미 존재하는 경우가 있기 때문
https://www.acmicpc.net/problem/14003
14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
대표적인 문제인 가장 긴 증가하는 부분 수열을 구하는 문제를 풀어보았다.
DP 배열이 어떻게 채워지는지, idx가 bisect_left를 이용하여 어떻게 계산이 되는지, answer에 어떻게 추가가 되는지 등을 따라가 보면 잘 이해할 수 있다.
2. 직접 구현
오름차순으로 정렬된 배열 안에서 data의 left idx, right idx, middle idx을 이용해 찾고자 하는 값인 target 값을 찾는 알고리즘이다.
[구현 방법]
세 가지 케이스로 나누어 target값을 찾는다.
1. data[middle] == target // mid값을 return한다. ( data의 mid값이 target값)
2. data[middle] < target // middle 값이 target값보다 작으므로, left = mid+1로 범위를 좁혀준다.
3. data[middle] > target // middle 값이 target값보다 크므로, right = mid-1로 범위를 좁혀준다.
세가지 케이스에는 조건이 존재하는데, 점점 오른쪽으로 옮겨가는 left와 점점 왼쪽으로 옮겨지는 right의 위치가 뒤집어 지면 안되기 때문에, left <= right 라는 조건 안에서만 케이스가 나뉜다.
<script src="https://gist.github.com/KimGaYeong/d0dc88b5d355ce62a5e90326418ee494.js"></script>
어렵지 않게 이해할 수 있지만 응용을 하기가 까다로울 수 있기 때문에, 미리 연습을 많이 해놔야 겠다. 파이팅파이팅!!
