본문 바로가기

Algorithm/Binary Search

 (43)
(C++) - 백준(BOJ) 7795번 : 먹을 것인가 먹힐 것인가 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 lower_bound를 구현해보는 혹은 사용해보는 문제였습니다. 풀이방법 1. a,b를 오름차순으로 정렬합니다. 2. 모든 a의 원소들에 대해서 이분탐색을 시행합니다. a의 원소가 b의 원소 이하가 되는 index 지점을 찾게 된다면 해당 index지점까지 생명체 a는 b생명체를 먹을 수 있습니다. 이를 다르게 표현하자면 a의 원소값의 lower_bound 지..
(C++) - 백준(BOJ) 2776번 : 암기왕 답 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 입출력이 많기 때문에 c의 헤드들과 동기화를 끊어줘야 합니다. 그 후 이분탐색하시면 됩니다. 풀이방법 찾았다면 flag = 1로 만들어주고 찾기 못했다면 flag가 초기값 그대로인 0이므로 이분탐색 시행 후 flag를 return 해주면 됩니다. Code #include #define fastio ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); using namesp..
(C++) - 백준(BOJ) 1756번 : 피자 굽기 답 www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net 이분탐색 구현방법을 생각해야하는 문제였습니다. 풀이방법 1. 이분탐색은 정렬이 되었을 때 할 수 있기 때문에 구불구불한 오븐을 정리해야합니다. 위에서 봤을 때 오븐의 중간층은 넓어도 그 위의 층들이 중간층보다 좁을 때 중간층이 튀어나온 부분을 확인할 수 없습니다. 여기서 착안해서 오븐을 위에서 봤을 때 위층부터 너비의 내림차순으로 오븐 너비를 수정할 수 있습니다. 2. 이분탐색 시행 : 이전에 놓았던 오븐의 너비 보다 ..
(C++) - 백준(BOJ) 2428번 : 표절 답 www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 * 모든 파일이 크기가 1억으로 동일할 경우 파일의 개수가 10만개라면 pair의 개수가 int범위를 초과할 수 있으니 long long형으로 답과 함수 자료형을 선언했습니다. 1. 입력 file값을 오름차순으로 정렬합니다. 2. 현재 index를 가장 큰 값으로 가정, 0 ~ index - 1까지 파일사이즈가 ..
(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

티스토리툴바