이진 탐색 알고리즘 Q www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net A 이진 탐색 알고리즘을 쓰는데, bisect 라이브러리를 활용하면 더 쉽게 풀 수 있다. bisect 사용 코드 from bisect import bisect_left, bisect_right import sys testcase = int(sys.stdin.readline().rstrip().split()) for _ in range(..
이진 탐색 알고리즘 파라메트릭 서치 Q 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 A 이진 탐색 문제이다. 다만, 문제를 그냥 풀기보다는 파라메트릭 서치를 적용하여 결정 문제로 바꾼 뒤에 푸는 것이 훨씬 간단해진다. 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이므로, 최대 거리를 범위로 잡고, 공유기를 다 설치할 수 있는지 결정하는 문제로 바꿔서 풀었다. 코드 import sys n, c =..
이진 탐색 알고리즘 Q www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net A 이진 탐색 알고리즘을 사용하였다. 코드 import sys from math import floor x, y = map(int, sys.stdin.readline().rstrip().split()) z = floor((y*100)/x) #내림 start = 0 end = 1000000000 if x == y or z == 99: #승률 100프로와 99프로는 변하지 않으므로 -..
