Algorithm/Binary Search (43) 썸네일형 리스트형 (Python) - 백준(BOJ) 13706 : 제곱근 https://www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n을 선언 후 입력받습니다. 📔 풀이과정 n이 800자리이므로 big int가 지원되는 언어가 구현하기 쉽습니다. math.sqrt함수로는 800자리의 n을 인자로 받을 수 없습니다. overflowerror를 출력하므로 틀리게 됩니다. 해당 issue는 하기 링크에 있습니다. https://stackoverflow.com/questions/28239978/python-sqrt-limit-for-very-large-numb.. (C++) - 백준(BOJ) 1253번 : 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 이분탐색으로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, ans, 일차원 배열 num을 선언 후 n만큼 수를 입력받습니다. 2. num을 오름차순으로 정렬해줍니다. 📔 풀이과정 오름차순으로 정렬되어 있으니 i번째 수를 두 수의 합으로 나타내려면 그 두 수의 위치는 무조건 0 ~ i-1 사이에 존재합니다. num[i+1]부터는 하나의 수 만으로도 num[i]를 넘기 때문에 두 개의 수에 대한 합으로 표현할 수 .. (C++) - 백준(BOJ) 17266번 : 어두운 굴다리 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 이분탐색 문제였습니다 📕 풀이방법 📔 입력 및 초기화 1. n, m, 가로등의 위치를 저장할 일차원 배열 lamp를 선언합니다. 2. n, m을 입력 받고 m개의 lamp 위치를 입력받습니다. 📔 풀이과정 가로등의 적절한 위치를 mid로 두어 이분탐색을 시행합니다. 가로등이 제대로 n만큼의 굴다리 길이를 비추는 지 확인하기 위해 구역을 3군데로 나눕니다. 1. 0번 위치 ~ lamp[0] : 길이는 .. (C++) - 백준(BOJ) 1484번 : 다이어트 https://www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 이분탐색 문제입니다. 📕 풀이방법 📔 입력 및 초기화 1. g를 선언, 하나도 답을 찾지 못했을 때를 알기 위한 bool 변수 flag, 제곱수들을 저장할 vector형 변수 square를 선언합니다. 2. g를 입력 후 10만까지의 제곱수를 square에 저장합니다. *10만 * 10만은 100억이므로 int범위를 초과합니다. 수는 long long형으로 저장해줍니다. 📔 풀이과정 1. 현재 몸무게를 .. (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.. 이전 1 2 3 4 5 6 다음
