Algorithm/Binary Search (43) 썸네일형 리스트형 (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++) - 백준(BOJ) 2470번 : 두 용액 답 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net Two Pointer 문제였습니다. 풀이방법 1. 두 용액의 특성값을 더했을때 기존에 있던 결과값보다 작다면 갱신 2. 두 용액의 특성값 합이 0이하면 left pivot을 ++ 3. 두 용액의 특성값 합이 0초과면 right pivot을 -- 4. 최종 결과값 출력 Code #include #include #include #include using namespace std; .. (C++) - 프로그래머스(Programmers) : 징검다리 답 https://programmers.co.kr/learn/courses/30/lessons/43236?language=cpp 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이분탐색 문제였습니다. 풀이방법 바위 사이의 거리를 mid로 생각해 해당 조건을 찾았을 때의 거리들의 max값을 찾는 이분탐색을 시행하였습니다. 1. mid보다 바위 사이의 거리가 작다면 제거해준다. removeCount값을 증가시킵니다. 2. 모든 바위를 제거했을때의 removeCount값이 n보다 크면 너무 많이 지웠으므로.. (C++) - 프로그래머스(Programmers) : 입국심사 답 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr answer가 될 수 있는 최대 범위를 잘 정해야하는 이분탐색 문제였습니다. 절반 테케에서 시간초과가 계속나 2시간 날렸습니다.^^ 시간초과가 자꾸 뜰 경우 : 자료형의 범위를 초과할 경우 시간초과로 처리하는 것 같습니다. 이거 때문에 이분탐색 로직을 계속 고민하여 시간을 쓸데없이 버렸습니다. 풀이방법 : 걸리는 시간을 찾아야 되는 값이라고 상정한 후 그에 대.. (C++) - 프로그래머스(Programmers) : 예산 답 https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그�� programmers.co.kr 상한액을 잘 배정해야되는 이분탐색 문제였습니다. 풀이방법 : 다음과 같이 두가지의 경우로 나누어 해결했습니다. 1. 상한액을 배정할 필요가 없는 경우 : 즉 총 예산 M보다 budgets에 담긴 전체 예산이 더 적을 경우엔 budgets들 중 가장 큰 값을 반환합니다. 저의 경우 이 부분이 없어 계속 틀렸습니다. 2. 상한액을 이분탐색을 통해 배정해야되는 경우 :.. (Text) - 백준(BOJ) 15641번 : SUPER SUPER BINARY SEARCH DELUXE 2.5 ~ https://www.acmicpc.net/problem/15641 15641번: SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2: T 1 이상 100 이하의 자연수를 출력한다. 단, 하나의 자연수만 정답이다. 정답은 맞은 사람이 나타날 때마다 바뀐다. 정답보다 작은 수를 출력하면 33% 부근에서 "틀렸습니다"를 받는다. 정답보다 큰 수를 출력하면 66% 부근에서 "틀렸습니다"를 받는다. www.acmicpc.net 1~100까지의 숫자를 이분탐색하며 제출합니다. 이분탐색 시간 복잡도가 O(logN)이므로 9번만에 답을 찾을 수 있습니다. 답은.. 이전 1 2 3 4 5 6 다음
