🧚‍♂️알고리즘🧚‍♂️ - 이진탐색

이진 탐색(이분 탐색)

데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음

 

기본 틀

1. 데이터 오름차순(내림차순) 정렬하기
2. 현재 데이터셋의 중앙값(mid)  선택
3. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. (mid값을 바꾸는 방법 사용)
4. 중앙값 <  타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
5. 과정 2-4를 반복하다가 중앙값 = 타깃 데이터일 때 탐색을 종료한다.

 

완전탐색의 시간복잡도 ( O(N^2),  O(N!), 등) 

이분 탐색의 시간복잡도 ( O(logN))밑2

열심히만듦(doit 참고)

---

실버 4

1920

1920번: 수 찾기

---

실버1 

2343

2343번: 기타 레슨

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건 => 이진탐색 알고리즘 사용

 

중간값 = 블루레이의 크기

블루레이의 크기가 될 수 있는 최솟값 = 최대 길이의 레슨시간 = 시작인덱스

블루레이의 크기가 될 수 있는 최댓값 = 최대 길이의 레슨시간 = 종료인덱스

 

중앙값(블루레이) 크기로 모든 레슨을 저장할 수 있다면 종료인덱스 = 중앙값-1

중앙값(블루레이) 크기로 모든 레슨을 저장할 수 없다면 종료인덱스 = 중앙값+1

 

이진탐색 : 목표치를 찾을 때가 아닌 최솟값(최종 시작인덱스값)/최댓값(최종 종료인덱스값) 을 찾을 때도 사용 가능

from sys import stdin
N, M = map(int,stdin.readline().split()) #레슨 수  블루레이 개수
Llist = list(map(int,stdin.readline().split()))

start = max(Llist) # 블루레이의 최소크기후보, 최대 길이의 레슨시간  <= 여기에 가까워야 함
end = sum(Llist) # 블루레이의 최대크기후보, 모든 레슨시간의 합

while(start <= end):
    mid = (start+end)//2 #블루레이크기후보

    BlueNum = 1 # mid크기일 시 블루레이 개수
    oneBlue = 0 #각 블루레이크기 확인 변수
    for cha in Llist:
        if oneBlue+cha <= mid:
            oneBlue += cha
        else:
            oneBlue = cha
            BlueNum += 1
    
    if ( BlueNum <= M ): # 최소를 구해야 하므로 개수가 M과 같을 때도 값을 줄임
        end = mid-1
    else:
        start = mid + 1

print(start)

왜 start를 출력할까?

마지막에는 반드시 BlueNum <= M 조건에 걸림/ end가 감소함

왜 ㄱ렇냐면,

최종 시작/종료 인덱스 값은 start > end가 된 처음이므로, 홀리

 

 

 

항상 최종적으로 end랑 start는 1밖에 차이가 안 나므로 end+1을 해도 됨

왜 그렇냐면,

홀리카몰리난멍청이야

지금은 물러나지만 다음에 돌아와 조져주겟어 기다리도록

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

while문 조건을 뭐로 할지 ( start <= end, start < end, start + 1 < end ..)

정답으로 무엇을 출력해야 할지 (start, end...)

 많이 헷갈리는 이분탐색, 위 포스팅 보고 정리!

---

골드2

1300

1300번: K번째 수