[Algorithms] 백준 2805 풀이 - 왜 이진 탐색(Binary Search)으로 해결할까?

TL; DR

이분 탐색(Binary Search)은 정렬이 되어있는 데이터 셋에서,
특정 값을 확인할 범위를 절반으로 줄여가며 탐색하는 알고리즘이다.

1) 범위가 엄청나게 넓은 데이터셋에서 어떤 값을 탐색해야한다면,  
2) 해당 데이터셋이 순서대로 정렬이 되어있어서, 값의 대소를 비교확인 할 수 있다면,  

범위를 logN 단위로 줄여주는 이분 탐색을 활용하는 것이 효율적이다.

백준의 나무자르기 문제에서  
절단기의 높이는 0이상의 양의 정수이며,  
이 절단기의 높이에 따라 벌목의 결과 값이 결정된다.  

이는 곧,  
절단기 높이의 범위 배열이  
벌목의 결과 값에 대한 index로 쓰일 수 있다는 것.  

따라서,  
백준의 나무자르기 문제는  
절단기 높이의 범위를 절반으로 줄여가며, 벌목의 결과 값을 찾으면 된다.

 

백준 2805 나무 자르기 문제 풀이

• 문제 링크
• 핵심 요구
  : 들쭉날쭉한 높이의 나무들을,
    처음 설정한 높이로 한꺼번에 베어버리는 절단기를 사용할 때,
    최소한의 벌목 목표 길이를 만족하는,
    절단기 높이의 최댓값을 구하는 함수를 만들어라.
  
  
• input values
  • N(treeCnt): 나무 개수 (나무 별 높이 데이터를 담을 배열의 크기)
  • M(aimLen): 벌목할 나무의 총 길이
  • array(treeHeigts): 나무 별 높이 데이터 배열
    
    
• 문제 상황의 data의 형태
  • 절단기 높이의 case: [0, 1, ... , max(trees)]
  • 벌목된 총길이 case: [sum(trees), ... , 0]
    
    
• 문제 접근법
  • 1) 분석
      - 절단기 높이 case를 나열한 배열은 0부터 가장 키 큰 나무 높이까지 1씩 커지는 양의 정수가 담길 것이다. index같이 생긴 데이터 셋!
      - 벌목된 나무의 총길이 case를 담은 배열은 각각의 절단기 높이 case에 하나씩 대응되는 결과 데이터를 담을 수 있다.
      - 벌목된 나무의 총길이 case를 담은 배열은 절단기가 높아짐에 따라 값이 작아지므로, 정렬된 데이터 셋!
  • 2) 접근
      - 절단기 높이 case를 나열한 배열이, 예상되는 벌목 총길이 case를 담은 배열의 index라고 상상하기
      - 예상되는 벌목 길이들의 배열은 정렬된 데이터이므로, 문제의 input값인 벌목 목표 길이와 동일한 예상 벌목 길이에 대응되는 절단기 높이의 범위(index)를 절반씩 줄여가며 탐색할 수 있는, Binary Search 알고리즘을 활용하기

 

• 풀이
  1. 초기 shortCutter은 가장 짧은 0, longCutter은 가장 높은 나무 높이인 max(treeHeights)로 할당
  2. 벌목 예상 길이(expectedLen)를 구할 절단기의 높이를, 가능한 최소길이와 최대길이의 중앙값으로 설정
  3. 중앙값 절단기 높이(midCutter)에 대응되는 벌목 예상 길이(expectedLen)와 input으로 들어온 벌목 목표 길이(aimLen)를 비교
  4. 벌목 예상 길이(expectedLen)가 벌목 목표 길이(aimLen)보다 길거나 같으면, 절단기의 최저 높이를 늘리기. 즉, 벌목 예상 길이(expectedLen)가 나열된 배열에서, 탐색에 쓸 최소 index값을 중앙값의 다음 값으로 이동.
  5. 4와 반대로, 벌목 예상 길이(expectedLen)가 벌목 목표 길이(aimLen)보다 짧으면, 절단기의 최고 높이를 줄이기. 즉, 벌목 예상 길이(expectedLen)가 나열된 배열에서, 탐색에 쓸 최대 index값을 중앙값의 이전 값으로 이동.
  6. 4번 혹은 5번에서 업데이트된 최저//최고 절단기 높이를 기반으로, 최적의 절단기 높이를 반복 탐색.
  7. highCutter < lowCutter 경우에 도달하면, index가 수렴된 시점이므로, 절단기 높이를 변동하는 반복 작업을 멈추고, 해당 시점의 최대 절단기 높이를 도출.

 

# Python

treeCnt, aimLen = map(int, input().split())
treeHeights = list(map(int, input().split()))

lowCutter = 0
highCutter = max(treeHeights)

while lowCutter <= highCutter:
    midCutter = (lowCutter + highCutter) // 2

    expectedLen = 0
    for tree in treeHeights:
        if tree >= midCutter:
            expectedLen += tree - midCutter

    if expectedLen >= aimLen:
        lowCutter = midCutter + 1

    else:
        highCutter = midCutter - 1

print(highCutter)