이것저것

이분탐색이란? 보통 간단하게 배열을 탐색하고자 한다면 선형탐색 (Linear Search)를 많이 사용하곤 한다. 하지만 배열의 길이가 굉장히 길거나 배열을 여러번 탐색해야한다면 선형탐색은 매우 느리다. 선형탐색보다 탐색시간을 조금더 줄일 수 있는 것이 바로 이분탐색 (Binary Search) 이다. 이분탐색은 탐색할 배열의 중간의 값을 확인하여 탐색 범위를 절반씩 줄여나가며 탐색하는 알고리즘이다. 예를들어, [1,3,5,7,9] 인 배열에서 7을 찾는다고 하면 check 함수를 다음과 같이 설정하고 [check() = 7보다 크거나 같은 수이면 True, 그렇지 않으면 False] 배열의 중간값인 5를 먼저 확인한다. check(5) = False 이므로 5보다 배열 왼쪽에 있는 1, 3은 확인하지 ..

이 문제는 이분탐색을 활용하는 문제다. 이분탐색을 통해 가장 긴 조각의 최소값을 찾을 수 있다. 1~L(통나무전체길이) 까지의 길이 중 검사할 길이를 이분탐색으로 정하고 통나무의 가장 긴 조각이 이보다 작은지 검사해서 가장 긴 조각의 최소값을 찾으면 된다. 그런데 통나무의 모든 조각이 특정 길이보다 작은지 검사할 수 있는 방법이 생각이 안났다. 그래서 아래 질문 글의 코드를 참고하여 그 방법을 알아보았다. https://www.acmicpc.net/board/view/51740 간단하게 말하면 그냥 한쪽끝에서 통나무조각이 검사하는 길이에 최대한 가깝게 자르면 된다. 처음에는 잘 이해가 안됐는데 생각보다 간단했다. 그림과 같이 길이가 L인 통나무가 있고 통나무의 모든 조각이 S보다 작은지 확인해보자 x <..