이분 탐색

백준 2110 풀이 (공유기 설치, 이분 탐색)

진짜 주우우우우ㄹㄹㄹ라라라아아아아ㅏ아아 어려웠다. 맨날 힙합들으면서 풀다보니 집중도가 낮은 편이었는데 이번 문제는 도저히 머리가 안돌아가서 뉴에이지 들으면서 풀었다. 혼자 푼건 아니고 다른 고수들의 풀이를 참고했다. 우선 문제를 잘 읽어야 한다. 여기 보면 가장 인접한 두 공유기 사이의 거리를 가능한 크게 한다고 적혀있다. 이게 도대체 무슨 소리인가 고민을 해보면 그냥 적당히 띄어 두겠다라는 소리같다. 그럼 이걸 어떻게 구하는가? 예제를 보자 [1,2,4,8,9]의 위치에 집이 존재하기 때문에 공유기를 설치 가능하다. 그렇다면 공유기를 설치할 수 있는 경우의 수는 5C3이다. 10개의 경우의 수가 존재한다. 거기에 공유기가 3개이기 때문에 루프를 돌면서 3번씩 돌아서 최댓값을 찾는다고 가정하면 굉장히 많..

백준 2805 풀이 (나무 자르기, 이분 탐색)

문제는 그냥 머랄까 톱이 하나 있고 높이를 정해서 일괄적으로 잘라버린다. 이후에 잘린 나머지의 값의 합이 m보다 크게 만드는 최댓값을 구하면된다. 이분 탐색으로 높이를 탐색하며 적절한 높이를 구하면된다. 저번 문제와 아주 유사해서 딱히 중요한게 없었다. 1. L과 R을 정한다. 2. mid값으로 일괄적으로 자르고 남은 값이 m보다 큰지 비교한다. 3. L과 R을 갱신한다. n,m = map(int, input().split()) tree = list(map(int,input().split())) l = 0 r = max(tree) mid = (l+r+1)//2 while l != r: # clac sum = 0 for t in tree: tmp = t - mid if tmp > 0: sum += (t-m..

백준 1920 풀이 (수 찾기, 이분 탐색)

오늘 알고리즘 수업시간에 교수님이 설명해 주셨던 이분 탐색문제다. 문제는 원리는 크게 어렵지 않다. 1. start와 end의 중간인 mid를 정한다. 2. mid의 위치에 찾으려는 i 값과 비교한다. 3. 같으면 리턴한다. mid보다 i의 값이 크면 start=mid+1, mid보다 i가 작으면 end = mid-1을 해준다. 4. 찾을때까지 반복하다가 start < end를 만족하지 않으면 루프를 벗어난다. 이걸 코드로 짜면 아래와 같다. 단, 비교하려고 하는 리스트가 정렬되어 있는 경우에만 사용가능하다. n = int(input()) A = list(map(int, input().split())) A.sort() m = int(input()) B = list(map(int, input().split..