https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 주의할 점은 문제에서 포커스를 맞춰야 할 곳이 절단기에 설정할 높이를 구하는 것이고, 절단기에 설정한 높이를 나무의 길이에서 빼준 값으로 비교해야 한다는 점이다. 이분탐색이 이해가 잘 안간다면 아래의 알고리즘 설명글을 참고하면 좋을 것 같다! https://go2gym365.tistory.com/87 [Algor..
이분탐색 알고리즘
1. 이분탐색이란? 이분 탐색 알고리즘은 정렬되어 있는 배열에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 알고리즘이다. 이분탐색은 결정 문제의 답이 이분적일 때 사용할 수 있는데 대표적인 예시로 카드 뽑기 문제가 있다. 결정 문제란 답이 Yes or No인 문제를 의미한다. 시간 복잡도 : O(logN) 카드 뽑기 문제는 1 ~ 50까지 오름차순으로 정렬된 카드묶음에서 28번 카드를 찾는 문제를 예시로 들어보겠다. 첫번째 카드부터 n번째 카드는 card[i], 우리가 찾고자 하는 카드인 28은 val로 가정한다. 이때 문제를 푸는 방법에 v[i] >= val 인가를 잡으면 답은 1~27까지는 False, 28이후로는 True가 나오게된다. 이때 우리가 찾고자 하는 값은 처음으로 card[i] >= ..
