Algorithm/Binary Search (47) 썸네일형 리스트형 (C++) - LeetCode (easy) 278. First Bad Version https://leetcode.com/problems/first-bad-version/description/ First Bad Version - LeetCode First Bad Version - You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions leetcode.com 이분 탐색 문제였습니다. 📕 풀이방법 📔 풀이과정 처음으로 isBadV.. (C++) - LeetCode (easy) 374. Guess Number Higher or Lower https://leetcode.com/problems/guess-number-higher-or-lower/ Guess Number Higher or Lower - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이분탐색 문제였습니다. 📕 풀이방법 📔 풀이과정 1. 1초는 1억연산이므로 n이 2^31승인 경우 O(n) 인 시간복잡도를 가지는 brute force로 해결할 수 없습니다. O(logn)인 이분탐색을 사용해야합니다. 2. 1 ~ n-1까지의 범위를 이분탐.. (C++) - LeetCode (easy) 35. Search Insert Position https://leetcode.com/problems/search-insert-position/ Search Insert Position - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이분탐색 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 target이상의 값이 나온 원소의 iterator를 lower_bound함수를 이용해 구해줍니다. 이 값을 지역변수 idx 선언 후 저장합니다. 📔 풀이과정 1. target이상의 값이 num에 없으면 lower_boun.. (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. 현재 몸무게를 .. 이전 1 2 3 4 5 6 다음 목록 더보기
