[TIL_Carrotww] 26 - 22/10/07

📝Carrotww의 코딩 기록장

🧲 알고리즘 이분탐색

🔗 프로그래머스 징검다리 건너기
이번주 풀었던 이분탐색 문제를 정리해 보았다.

def solution(stones, k):
    left, right = 1, 200000
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        for st in stones:
            if st - mid <= 0:
                cnt += 1
            else:
                cnt = 0
            if cnt >= k:
                break
        if cnt >= k:
            right = mid - 1
        else:
            left = mid + 1

    return left

🔗 프로그래머스 입국 심사

def solution(n, times):
    result = 0
    left, right = min(times), max(times) * n
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        for ti in times:
            cnt += mid // ti
            if cnt >= n:
                break
        if cnt >= n:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    return result

print(solution(6, [7, 10]))

💡 느낀점

🔍 징검다리 건너기 문제는 처음에 브루트포스로 풀어, 효율성에서 실패하여 못 풀었던 문제인데, 알고보니 이분탐색 문제였었다. 이분탐색 알고리즘 강의를 다시 복기한 후 문제를 푸니 문제에 대한 아이디어를 떠올리기 쉬웠다.
🔍 징검다리 건너기 문제 후에 이분탐색 문제를 찾아 입국 심사 문제를 풀어보았다.
해당 문제는 이분탐색으로 접근해야지 하고 생각하며 풀었지만 입국 심사관 개별로 소요시간을 접근하여 아이디어를 떠올리기가 쉽지 않았다. 접근 방식을 알고도 풀지 못한게 너무 아쉬웠다 ㅠ 풀었던 문제들을 복기 하고 다시 풀어봐야겠다.