binarysearch 검색 결과
3 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 1789번 수들의 합(이분 탐색)[Kotlin - 코틀린]

백준 1789번 문제입니다. (solved.ac) 기준 실버 5 문제입니다. https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 문제 자연수 s를 입력받고, 1부터 n까지의 합이 s가 되는 최대 n값을 구하면 되는 문제입니다. 1 ~ n까지의 합을 구하기 위하여 반복문을 사용해도 되지만(O(n)) n이 커질수록 연산의 시간이 오래걸릴 것이라고 생각해서 수식을 이용한 함수를 만들었습니다. ( 1 ~ n 까지의 합 = n * (n+1) / 2) s의 범위가 굉장히 크기 때문에 n값을 찾기위하여 이분탐색을 진행하였습니다. 탐색의 시작점(start)은 1, 끝점(end)은..

2022. 6. 21. 15:38
알고리즘 문제풀이[Algorithm]

[백준] 2110번 공유기(파라메트릭 서치)(Python - 파이썬)

백준 2110번 문제입니다. (solved.ac)기준 골드 5 문제입니다. 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 힌트 : 공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다. n개의 집에 c개의 공유기를 설치해야하는데 설치된 공유기들 중 가장 인접한 두 공유기 사이의 거리가 최댓값일 때를..

2022. 1. 31. 14:40
알고리즘 문제풀이[Algorithm]

[백준] 2512번 예산(파라메트릭 서치)(Python - 파이썬)

백준 2512번 문제입니다. (solved.ac)기준 실버 3 문제입니다. https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net n개 지방에서 각각 요청 예산을 입력 받고 예산의 총액(M)에서 2가지의 조건을 만족시키도록 예산 배정을 하면 되는 문제입니다. 1번 조건 : 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 2번 조건 : 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 ..

2022. 1. 27. 00:44