본문 바로가기

Algorithm/Binary Search

 (47)
(C++) - 백준(BOJ) 2230번 : 수 고르기 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, m, 수를 저장할 일차원 배열 a, 답을 저장할 변수 ans를 선언합니다. 2. n, m입력 후 n만큼 수를 a에 입력받습니다. 3. a를 오름차순으로 정렬해줍니다. 📔 풀이과정 n만큼 loop를 돌며 현재보는 값이 a[i]일 때 a[i] + m이상인 index를 a에서 찾습니다. a[i] + m 이상인 값이 존..
(C++) - 백준(BOJ) 2417번 : 정수 제곱근 https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 풀이과정 mid에 제곱을 한다면 long long범위를 초과할 수 있습니다. overflow발생을 막기 위해 num에 루트를 씌웁니다. sqrt(num)이상이 되는 mid를 찾는 것으로 해결할 수 있습니다. 이 mid는 이분탐색을 시행해 찾습니다. 📕 Code #include using namespace std; using ll = long long; ll num; ll binarySearch(){ ll l = 0; ll r = sqrt(num); while(l > num; c..
(C++) - 백준(BOJ) 14627번 : 파닭파닭 https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파 www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 s : 파의 개수 c : 주문된 파닭 수 ans : 정답(라면에 넣을 파의 양) greenOnion : 파의양을 입력받을 일차원 배열을 선언합니다. 📔 풀이과정 파닭에 넣을 파의 양을 mid로 두어 이분탐색을 시행합니다. 1. mid는 0 ~ s까지의 모든 i에 대해 greenOnion[i] / mid의 ..
(C++) - 백준(BOJ) 3649번 : 로봇 프로젝트 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 1. 입력 : 구멍의 단위가 cm으로 주어지기 때문에 nm으로 변경합니다. 1천만을 곱해주면됩니다. 이를 length라는 변수에 저장합니다. 이후 vector형 변수 lego에 n만큼 lego의 길이들을 입력받습니다. 2. lego를 오름차순으로 정렬합니다. 현재 확인하고 있는 한쪽 lego의 길이가 lego[i]일 때 length - le..
(C++) - 백준(BOJ) 2143번 : 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 이분탐색으로 푼 문제였습니다. 풀이방법 1. vector a, b에 입력을 받습니다. 2. i ~ j까지의 누적합을 a, b 각각에 저장합니다. 3. 이분탐색을 위해 b를 정렬합니다. 4. a + b = t이므로 모든 a에 대해 b가 t - a인 값을 찾습니다. 해당 값이 여러개 있을 수 있으므로 lower_bound..
(C++) - 백준(BOJ) 7453번 : 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 이분 탐색으로 해결한 문제였습니다. 풀이방법 1. 입력 받은 후 loop를 돌며 다음을 저장합니다. sums1에는 a[i] + b[j]들, sums2에는 c[i] + d[j]. 이렇게 a + b의 쌍들과 c + d의 쌍들이 저장되었습니다. 이 후 두 배열을 오름차순으로 정렬합니다. 2. 모든 sums1에 대해 sums2로부터 -sums1[i]인 값을 찾아 그 index를 구합니다..
(C++) - 백준(BOJ) 3896번 : 소수 사이 수열 https://www.acmicpc.net/problem/3896 3896번: 소수 사이 수열 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다. www.acmicpc.net 소수 찾기 + 이분탐색문제였습니다 풀이방법 1. 100000번째 소수까지 모두 구해놓습니다. 에라토스테네스의 체 방식을 이용하면 O(루트N)으로 빠르게 구할 수 있습니다. 2. 소수라면 0을 출력, 이분탐색으로 해당 수보다 큰 가장 가까운 소수에 해당하는 인덱스를 찾습니다. 그 후 해당인덱스 - (해당인덱스 - 1)의 값을 출력합니다. Code #include using namespa..
(C++) - 프로그래머스(2019 카카오 개발자 겨울 인턴십) : 징검다리 건너기 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 이분탐색으로 푼 문제입니다. 풀이방법 최대로 건널 수 있는 인원을 찾아야합니다. 1. 인원을 mid라고 생각했을 때 최대한으로 건넌 후의 각 돌들의 높이는 밟을 때마다 1씩줄어들기 때문에 결과적으로 돌높이 - 인원 수가 됩니다. 이 (돌높이 - 인원 수) 값이 0이하라면 건너뛰어야 하는 돌이 됩니다. 2. 모든 stones에 대해 연속되는 0이하의 구간들 중 최장구간의 길이를 cnt변수에 저장합니다. 3. cnt >= k라면 너무 많은 인원이 건넌 것이므로 right = mi..

티스토리툴바