이분탐색

백준 - 2805 나무 자르기 [이분 탐색]

2023.10.25

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 문제 요약 나무의 수 n, 가져가려고 하는 나무의 길이 m이 주어지고, 나무의 높이 수열이 주어진다. 자를 높이를 지정하면 해당 높이에 맞게 모든 나무가 잘리며, 지정한 높이 이하의 나무들은 잘리지 않는다. m을 만족하면서 자를 수 있는 나무의 높이의 최솟값을 구하시오. 2. 접근 방법 자르는 높이 별로 얻을 수 있는 나무의 길이를 수열이라 생각하고 이분 탐색을 활용하여 풀면 쉽게 풀 수 있습니다. 빨간색이 배열의 인..

개발일지/Algorithm

백준 - 10815 숫자 카드 [이분탐색]

2023.10.24

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 문제 요약 숫자 배열이 주어지고, 찾고자 하는 숫자가 주어졌을 때, 찾고자 하는 숫자가 배열에 존재하는지 판단하시오. 2. 접근 방법 이분 탐색 알고리즘을 사용합니다. 해당 알고리즘은 일반적으로 하는 up down 게임과 같은 원리입니다. 정렬된 상태에서 절반씩 소거하며 찾아내는 방법입니다. 오름차순으로 정렬된 배열에서 중간 부분을 탐색하고, 찾고자 하는 숫자보다 크면 해당 지점부터 끝부분까지의 중간 부분을 탐색합니다. 찾고자 ..

백준 - 2805 나무 자르기 [이분 탐색]

백준 - 10815 숫자 카드 [이분탐색]

티스토리툴바