백준/이분 탐색

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 풀이 기존의 dp로만 풀어주면 시간초과가 일어난다. dp풀이는 N^2의 시간 복잡도를 가지기 때문에 N의 크기가 최대 10^6이기에 1초를 넘어서는 시간초과가 일어난다. 그래서 이분탐색을 이용해서 풀어줘야하는 문제이다. DP 코드(시간초과) n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분탐색 문제 # 백준 1654 # K개의 다른길이를 가진 전선들을 N개의 일정한 길이의 전선들로 만들어야한다. # 이분탐색을 위한 target, start, mid를 잡아준다. 이분탐색을 최댓값을 찾을때까지 진행된다. import sys input = sys.stdin.readline K, N = map(int, input().split()) # K개와 N개를 ..