[백준 2805번] 나무 자르기 - 파이썬

 

① 문제 링크

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

② 알고리즘 분류

이분 탐색, 매개 변수 탐색

---

③ ★문제풀이 Point★

- 이분 탐색(이진 탐색)의 개념을 알고 있는지 여부

---

④ 풀이

이 문제는 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하는 문제다.

이 문제를 풀기 위해서는 이분 탐색 알고리즘에 대해 알아야 한다.

 

이분 탐색 / 이진 탐색 (Binary Search)이란?

Binary Search 예시

이분 탐색: 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

다음 그림은 이분 탐색으로 원하는 숫자 77을 찾는 과정이다.

77을 찾아라

1. 50부터 탐색을 시작한다. (시작 지점 1과 끝 지점 100의 중간 위치는 50)

2. 77은 50보다 크므로 왼쪽 포인터 1(시작지점)를 오른쪽 50(중간 부분)으로 이동한다.

- 다음은 75(50과 100의 중간 부분)다.

3. 77은 75보다 크므로 마찬가지로 왼쪽 포인터 50(시작 지점)을 오른쪽 75(중간 부분)로 이동한다.

- 다음은 87(75와 100의 중간 부분)이다.

4. 77은 87보다는 작으므로 이번에는 오른쪽 포인터 100(끝 지점)을 왼쪽 87(중간 부분)로 이동한다.

5. 이런 식으로 점점 범위를 좁혀 나가면 7번 이내에 무조건 숫자 77을 맞출 수 있게 된다.

 

이분 탐색의 시간 복잡도

이분 탐색의 시간 복잡도는 O(logN)이다. (여기서 log는 log₂를 의미)

단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 보장한다.

예를 들어 처음 데이터의 개수가 16개라면, 이론적으로 1단계를 거치면 약 8개, 2단계에서 약 4개, 3단계에서 약 2개의 데이터만 남게 된다.

 

이분 탐색 알고리즘 Python 기본 코드

1. 반복문 

# 비재귀적 이진탐색의 Python 코드 (반복문)
def binary_search (arr, val):
    first, last = 0, arr.len()
    while first<=last:
        mid = (first + last) // 2
        if arr[mid] == val: return mid
        if arr[mid] > val: last = mid - 1
        else: first = mid+1
    return -1

 

2. 재귀

# arr는 오름차순으로 정렬된 리스트
def binary_search(arr, target, low=None, high=None):
    low, high = low or 0, high or len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] > target:
        return binary_search(arr, target, low, mid)
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)

 

이제 백준 2805번 나무 자르기 문제를 풀어보며 이분 탐색 알고리즘에 대해 공부해보자.

위의 이분 탐색(Binary Search)의 기본 알고리즘 코드를 이용하면 쉽게 해결할 수 있다.

 

⑤ 코드

다음 코드는 PyPy3로 작성하였습니다.

# 2805 나무 자르기

n, m = map(int, input().split())
trees = list(map(int, input().split()))
start, end = 1, sum(trees)

# start와 end가 같아질 때까지 반복
while start <= end:
    mid = (start + end) // 2 # 중간 위치
    cnt = 0
    # 나무 자르기
    for tree in trees:
        # 나무의 높이가 절단기 높이보다 크다면
        if tree > mid:
            # 자르기
            cnt += tree - mid
    # 자른 나무들의 길이가 목표값 이상이라면
    if cnt >= m:
        # 시작점 조정
        start = mid + 1
    # 목표값 이하라면
    else:
        # 끝점 조정
        end = mid - 1
 # 답 출력
print(end)

 

2805번 파이썬 채점결과

---

백준 2805번 나무 자르기

 

Reference:

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89