이진 탐색(binary search) 알고리즘 파이썬, 백준 2343 파이썬

파이썬 코딩테스트 정복기 3탄입니다.

파이썬 코딩에 대해 기본적인 지식이 필요합니다.

 

각 단원마다 개념을 모두 포함하는 예제 한 문제만 풀이할 예정이니 참고해주세요.

 

1. 스택 + DFS + 이분 그래프

2. 큐 + BFS + 트리의 지름

3. 우선순위 큐와 그리디
4. 유니온 파인드 + 최소 신장 트리
5-1. 최단 거리 찾기[1] - 다익스트라 알고리즘

5-2. 최단 거리 찾기[2] - K번째 최단 거리

5-3. 최단 거리 찾기[3] - 벨만 포드

5-4. 최단 거리 찾기[4] - 플로이드 워 셜
6. 이진 탐색 + 트라이
7. 투포인터 + 슬라이딩 윈도우
8. 구간 합 + 세그먼트 트리
9. 에라토스 테네스의 체 + 오일러 피 함수
10. 유클리드 호제법 + 확장 유클리드 호제법
11. 조합 + 다이나믹 프로그래밍

---

 

이진탐색 알고리즘 개요

 

데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 특징은 아래와 같습니다.

• 데이터 탐색에 사용
• 중앙값 비교하여 대상을 축소
• 시간복잡도 O(logN)

구현 방법

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

오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복합니다.

1. 현재 데이터의 중앙값을 선택
2. 중앙값 > 타깃 데이터일 때 중앙값 기준 왼쪽 데이터셋을 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준 오른쪽 데이터셋을 선택
4. 중앙값과 타깃데이터가 같아서 탐색이 종료될때까지 반복

쓰이는 곳

• 정렬 데이터에서 데이터 탐색

백준 2343

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 블루레이가 될 수 있는 최소 크기(마지막 원소의 크기)부터 최대 크기까지(한번에 다 넣는 크기)
start = max(A)
end = sum(A)
m = 0
while start < end:
    m = (start + end) // 2
    cnt_m = 0
    sum_lesson = 0
    for lesson in A:
        sum_lesson += lesson
        if sum_lesson > m:
            sum_lesson = lesson
            cnt_m += 1
    cnt_m += 1
    # m에 더해지는 값이 다른 이유
    # 주어진 블루레이보다 많이 담기면 무조건 그 값도 안되는 값
    # 주어진 블루레이보다 적게 담기면
    if cnt_m < M:
        end = m -1
    elif cnt_m == M:
        end = m
    else:
        start = m + 1

print((start + end) // 2)