정신차려 하프물범 정신차려 하프물범

문제 링크 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 풀이 처음엔 단순히 N(상자 개수)개의 누적합 테이블(dp)을 만들어, start, end, mid를 통해서 dp[mid]의 도토리 개수에 따라 mid를 파악하려 했다. [시간 초과 난 코드] import sys input = sys.stdin.readline N, K, D = map(int, inpu..

이진 탐색탐색의 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 기법.특징이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만-1000억 이면 이진 탐색으로 접근하길 권한다.3가지 변수(시작점, 끝점, 중간점)가 사용된다.시작점, 끝점 : 탐색하고자 하는 범위를 나타내기 위해 사용중간점 : 중간점에 있는 데이터와 찾고자 하는 데이터가 일치하는지 비교기위해 사용.시간 복잡도: O(logN) -> 한 번 비교때마다 반 씩 줄어드니까!소스코드 (재귀, 반복문)1. 재귀# 이진 탐색 소스코드 구현 (재귀 함수)def binary_search(array, target, start, end): if start > end: ..