본문 바로가기

Algorithm/Binary Search

 (47)
(C++) - 백준(BOJ) 2343번 : 기타 레슨 답 www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색 문제였습니다. 이분탐색시 pivot역할을 하는 left, right의 초기값과 max값을 잘 생각해 작성해야합니다. 풀이방법 1. 이분탐색시 비교할 초기값 생각하기 : 가장 긴 레슨이 곧 해당 블루레이 길이의 최소가 되므로 이를 left로 두고 right는 블루 레이의 개수가 1개, 10만개의 레슨 개수, 모든 레슨의 길이가 1만일경우 한 블루레이의 길이는 1만 * 10만 = 10000 * 100000 = 1..
(C++) - 백준(BOJ) 2141번 : 우체국 답 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, 0≤A[i]≤1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 이분탐색 문제였습니다. 지문이 헷갈렸는데 먼저 우체국은 무조건 마을이 있는 위치에 세워야 합니다. 1.5 위치같은 소수점 위치에 세우거나 마을이 존재하지 않는 위치에 우체국을 만드는 경우는 없습니다. 또한 우체국을 세운 위치로부터 왼쪽 끝 마을에 위치한 사람들까지의 합, 우체국을 세운 위치 바로 다음 마을부터 오른쪽 끝 마을에 위치한 사람들까지의 합이 ..
(C++) - 백준(BOJ) 2022번 : 사다리 답 www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다. www.acmicpc.net 피타고라스 정리, 그래프 식세우기를 이용해 이분탐색을 하는 문제였습니다. 풀이방법 입력받는 x,y를 각각 a,b라고 가정한 뒤 구하려는 값을 k, 두 빌딩의 높이를 각각 A,B라고 가정했습니다. 이 때 가장 왼쪽 하단 꼭지점을 0,0으로 하여 직선 a,b에 대한 방정식을 구했습니다. 이 정보들을 공식으로 표현하면 다음과 같습니다. $A = \sqrt{a^2 - k^2}$ $B = \sqrt{b^2 - k^2}$ 직선 a에 대한 방정식 f(x) $f(x) = -\frac{A}{k}x + ..
(C++) - 백준(BOJ) 1072번 : 게임 답 www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 최대 값 설정, 승률 계산 방식을 신경써 푼 기본 이분탐색 문제였습니다. 풀이방법 앞으로 할게임 수를 mid로 두어 z값이 바뀌는 최소값을 이분 탐색을 통해 찾습니다. 1. 승률이 99%라면 게임을 아무리 많이해도 100%가 될 수 없으므로 -1을 반환합니다. 2. 승률이 달라질 경우(기존 승률보다 ) r = mid - 1, 아닐경우 l = mid+1로 l= 99) return -1; while(l> game >> win; cout
(C++) - 백준(BOJ) 2110번 : 공유기 설치 답 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 해석이 좀 난해한 이분탐색 문제였습니다. 풀이방법 * 최대한 공유기를 넓게 c만큼 설치했을 때는 집이 각 공유기가 설치된 위치에 위치하고 있습니다. * 최대한으로 설치하기 위해서는 첫번째 집에 공유기를 설치하면서 시작하는 것이 좋습니다. 1. 집의 좌표를 오름차순으로 정렬 2. 첫째 집을 제외한 모든 집의 좌표에 대해 공유기 두 개 사이의 거리가 x이..
(C++) - 백준(BOJ) 11561번 : 징검다리 답 www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이분탐색문제였습니다. 풀이방법 1. 최대의 징검다리를 밟을 경우는 무조건 이전거리보다 1만큼만 더 뛰는 것입니다. 따라서 매번 뛰는 횟수들을 계산했을 때 1의 등차를 가진 수열의 형태로 뛸 거리가 정해집니다. 징검다리 개수를 m개라고 했을 때 m(m+1)/2 > n; cout
(C++) - 백준(BOJ) 2473번 : 세 용액 답 www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net two pointer문제였습니다. 풀이방법 1. 첫 번째 용액 특성값을 first로 두고 n-2까지 loop를 돕니다. 2. 나머지 first+1 ~ n - 1까지 two pointer로 정답을 찾습니다. 3. 오름차순으로 정렬한 세 특성값을 출력합니다. Code #include #include #include #define ll long long using namespace std; ll..
(C++, Python3) - 백준(BOJ) 2470번 : 두 용액 답 www.acmicpc.net/problem/2470 2470번: 두 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00www.acmicpc.netBinary Search 혹은 Two Pointer로 풀 수 있던 문제였습니다.📕 풀이방법📔 입력 및 초기화배열길이와 배열을 입력받고 오름차순으로 원소들을 저장합니다.📔 풀이과정📑 Two Pointer 1. 두 용액의 특성값을 더했을때 기존에 있던 결과값보다 작다면 갱신 2. 두 용액의 특성값 합이 0이하면 left pivot을 ++ 3. 두 용액의 특성값 합이 0초과면 ..

티스토리툴바