선호:하다

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 import sys from bisect import bisect_left n = int(sys.stdin.readline()) data = list(map(int, sys.stdin.readline().rstrip().split())) dp = [data[0]] for i in range(1, n): if data[i] > dp[-1]: dp.append(data[i]) else: idx = b..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net import sys n, c = map(int, sys.stdin.readline().rstrip().split()) data = [] for i in range(n): data.append(int(sys.stdin.readline())) data.sort() start = 1 end = data[-1] - data[0] while start =..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net import sys k, n = map(int, sys.stdin.readline().rstrip().split()) data = [] for i in range(k): data.append(int(sys.stdin.readline().rstrip())) start = 1 end = max(data) while start = n: start = mid + 1 else:..

파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공한다. bisect 라이브러리는 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. bisect 라이브러리에서는 bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 모두 시간 복잡도 O(logN)에 동작한다. bisect_left(array, x): 정렬된 순서를 유지하면서 리스트 array에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는다. bisect_right(array, x): 정렬된 순서를 유지하면서 리스트 array에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는다. 예를 들어 정렬된 리스트 [1, 2, 5, 5, 7]이 있고 새롭게 5를 삽입하려..

순차 탐색(Sequential Search) 이진 탐색을 알아보기 전에, 가장 기본적인 탐색 방법으로 데이터를 차례대로 하나씩 확인하며 탐색하는 순차 탐색이 있다. 순차 탐색은 구현이 매우 쉽고 리스트에서 특정한 값의 원소의 개수를 세는 count() 메서드도 내부적으로 순차 탐색을 이용한다. 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 것이 특징이다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간 복잡도는 O(N)이다. 이진 탐색(Binary Search) 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위 일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 ..