Algorithm/Binary Search (44) 썸네일형 리스트형 (C++) - 백준(BOJ) 3151 : 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학생 수 n, 정답을 출력할 변수 ans, 코딩 실력을 저장할 vector v를 선언한 후 적절히 입력받습니다. 이후 v를 오름차순으로 정렬해줍니다. 📔 풀이과정 n이 1만이므로 brute force로 3중 for loop를 수행하면 O(4억)이 넘어 4초 초과로 틀리게 됩니다. O(n^2log(n))으로 2개의 수를 결정했으면 나머지 한 개의 수.. (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의 .. 이전 1 2 3 4 5 6 다음
