99클럽 코테 스터디 _ 2일차 TIL (이분탐색)

 

< 문제 >

[백준] 1654. 랜선 자르기 / 실버2

---

< 풀이 >

코드 변수 정의

• lans : 가지고 있는 랜선 길이 리스트
• cnt : 특정 길이를 만족하는 랜선의 총 개수
• max_length : N개를 만들 수 있는 랜선의 최대 길이(반환값)

---

Binary Search
시간복잡도 : O(N * log(max(lans)))

def binary_search(K, N, lans):
    left, right = 1, max(lans)
    max_length = 0

    while left <= right:
        mid = (left + right) // 2
        cnt = sum(lan//mid for lan in lans)

        if cnt >= N:
            max_length = mid
            left = mid + 1
        else:
            right = mid - 1
    return max_length

def f():
    K, N = map(int, input().split())
    lans = [int(input()) for _ in range(K)]
    print(binary_search(K, N, lans))

f()

• 이분 탐색
  • 탐색 범위 : 1 ~ (랜선 길이 중 최대 길이)
    • N개 이상의 랜선을 만드는 랜선의 최대 길이를 구하는 것이므로 
  • (작동 방식)
    1. 최대 길이 랜선(max(lans))의 절반 길이(mid)로 모든 랜선을 나누었을 때 생성되는 같은 길이 랜선의 개수(cnt)를 구한다.
    2. cnt가 N개보다 많거나 같은 경우 → 더 긴 길이로 cnt 구하기
       • 탐색 범위 : mid + 1 ~ max(lans))
       • max_length를 현재 mid 값으로 업데이트한다.
    3. cnt가 N개보다 적은 경우 → 더 작은 길이로 cnt 구하기
       • 탐색 범위 : 1 ~ mid - 1

---

< 회고 >

이 문제는 왜 이분 탐색일까? 에 대한 고민

 

1. 탐색 범위가 정렬되어 있다.
   • (문제에서) " 랜선을 자른 길이 "는 1 ~ 가장 긴 랜선의 길이까지의 값 중 하나
   • 각 길이를 기준으로 가능한 랜선 개수를 계산할 때, 길이가 길어질수록 만들 수 있는 랜선의 개수가 감소한다.
2. 조건을 만족하는 최대 길이를 찾는 문제이다.
   • (목표) 특정 길이가 조건을 만족하는지 확인 + 조건을 만족하는 최대 길이 찾기
   • 이분 탐색으로 조건을 만족하는 범위를 좁혀가며 최적의 값을 빠르게 찾는다.
3. 중간값(mid)으로 효율적인 탐색을 한다.
   • mid 길이로 랜선을 자를 때 생성 가능한 랜선 개수를 계산한다.
   • 생성 가능 랜선 개수 ≥ N
     • 길이를 늘려도 조건을 만족하는지 확인 (탐색 범위를 mid 기준 우측으로 이동)
   • 생성 가능 랜선 개수 ≤ N 
     • 길이를 줄이면 조건을 만족하는지 확인 (탐색 범위를 mid 기준 좌측으로 이동)
4. 시간 복잡도 비교
   • 완전 탐색 : O(max(lans)) * K)
     • 가능한 모든 길이를 일일이 확인하는 방식 → 비효율
   • 이분 탐색 : O(log(max(lans)) * K)