Algorithm/Binary Search (43) 썸네일형 리스트형 (C++) - 백준(BOJ) 1920번 : 수 찾기 답 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분탐색을 구현해보는 문제였습니다. 풀이방법 1. STL binary_search함수를 사용해 key값을 찾았다면 1을 아니라면 0을 출력하도록 합니다. 2. 직접 이분탐색을 구현하는 방법도 있습니다. * 입출력이 많으므로 c와 동기화를 풀어줘야 시간초과가 나지 않습니다. Code 1. STL 사용 #include #include #include #.. (C++) - 백준(BOJ) 13702번 : 이상한 술집 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 이분탐색(Binary Search)문제입니다. 개인적으로 변수 l은 1과 무척 헷갈리므로 대문자 L로 사용하심을 추천합니다. 저거 하나 때문에 뇌핏줄에 심각한 손상이 올 수 있습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, k를 입력받습니다. 각각 주전자 개수, 친구들의 수 입니다. 2. n만큼 loop를 돌며 주전자의 용량을 입력받습니다. 입력받을 때마다 a배열에 저장해줍니다. 그리고 big에.. (C++) - 백준(BOJ) 2805번 : 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색(Binary Search) 문제입니다. 풀이방법 1. 나무길이의 정보를 배열에 입력받고 오름차순으로 정렬합니다. 2. 찾으려는 절단기의 높이를 mid로 정해 이분탐색을 시행합니다. O(100만log100만)으로 시간제한에 걸리지 않습니다. 자른 나무들의 합이 m보다 작다면 다많이 잘라야하므로 절단기의 높이를 낮춰야합니다. 그 반대의 경우 절단기의 높.. 이전 1 ··· 3 4 5 6 다음