tose33

https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 우체국은 양쪽으로 사람수가 가장 일정하게 퍼져있는 곳에 지어야 한다. 그 위치는 이분탐색으로 찾는다. 이분탐색으로 찾은 위치 mid 에서 왼쪽에 있는 사람들의수와 오른쪽에 있는 사람들의 수를 비교해야 하는데, 일일히 더하면 시간복잡도가 O(N^2) 가 된다. 따라서 누적합으로 구해놓으면 된다. 만약 마을 [1,mid..

https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ www.acmicpc.net 이분탐색으로 팀 목표레벨을 탐색하면 된다. 팀 목표레벨이 되기 위해 필요한 레벨수를 카운트해서 K 보다 작거나 같다면 해당 레벨을 달성할수 있다는 뜻이다. K 보다 크다면 달성 불가능하기 때문에 목표레벨을 낮춘다. (right = mid - 1)

https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 처음에 보자마자 이분탐색이 생각나서 이분탐색으로 풀었다. 이분탐색으로 집합 크기를 정하고, 그 크기 내에 1이 K개 이상있는지 슬라이딩 윈도우로 판단한다. 풀고나서 다른 분들 코드를 봤는데 다른 방법으로 많이 풀었다. 먼저 라이언의 인덱스를 저장한다. 예제의 경우 0,4,6,9 가 라이언의 인덱스다. 3개의 라이언이 필요하기 때문에 3개씩 묶어서 끝인덱스-첫인덱스+1을 하면 길이가 된다.

https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 브루트포스로는 안될꺼고, map 에 S의 모든 접두를 저장하는 방법이 될지 안될지 확신이 안섰는데 일단 해봤다. (트라이 인것 같긴한데 트라이 짜기 힘들어서 일단 map으로 해봤다..) 그리고 통과했다. 그리고 나서 찾아 보니까 역시 정식 풀이 방법은 아니었다 (cpp 말고 파이썬 같은 언어로는 tle ) 이분탐..