이진탐색
-
2805 나무 자르기알고리즘/백준 2022. 3. 23. 10:26
백준 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 이 문제는 이분탐색으로 풀 수 있는 문제다 이분 탐색 참고 -> https://wh514.tistory.com/20 [코드 작성 전] 우선, 높이를 입력받으며 미리 나무 중 가장 높은 높이(hmax)를 저장한다. 탐색 범위를 0 ~ hmax로 설정하고 이분 탐색을 진행한다. 중간 값(cutter)를 절단기 설정 높이로 가정하고 ..
-
1920 수 찾기(이분탐색)알고리즘/백준 2022. 3. 23. 09:48
백준 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 [개념] 이분탐색 : (정렬된 리스트에서) 탐색범위를 절반으로 좁혀가며 데이터를 탐색하는 방법 - 이진탐색, Binary search 라고도 한다. 예시로, 상대방의 0~100 까지 숫자 중 생각해둔 숫자를 맞출 때, 내가 말한 숫자에 대해 up down을 해주면 범위를 점점 좁혀가며 숫자를 맞추는 경우가 있다. 여기서, ..