投稿した質問数 57

1

안녕하세요, eoyeong님!

말씀하신 대로 cur = -1인 경우를 따로 예외처리하는 것도 좋은 방법입니다.

하지만, 저 같은 경우는 함수 내에서 cur에 대해 처리하는 것이 아닌 함수 밖에서 cur을 처리하는 방식을 선호합니다. 이와 관련한 내용은 아래에 적혀져 있습니다.

매개변수 탐색 더 잘 이용하기

일단 매개변수 탐색 형식으로 구현한 경우에 (숫자 K에 대해) 함수의 의미는 "배열의 원소 중에서 K인 값을 찾는다" 라는 의미보단 "배열의 원소 중에서 K보다 작거나 같은 가장 오른쪽 인덱스를 반환한다"라는 의미로 받아들이는 것이 좋습니다.

따라서, 저 같은 경우는 매개 변수 탐색 방법을 이용한다면, 예외처리 없이 cur을 반환하게 한 후에 cur을 처리하는 방식을 많이 사용합니다. (아래의 코드 참조)

def get_idx(arr, num): # arr[idx] ≤ num인 가장 큰 idx를 반환
    cur = -1
    step = len(arr)
    
    while step != 0:
        while (cur + step < len(arr) and arr[cur + step] <= num): 
            cur += step
        step //= 2
        
    return cur


arr = [1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16]
num1 = -10
num2 = 6
num3 = 13

idx1 = get_idx(arr, num1)
# idx1은 -1이 나오게 된다. 즉, -10보다 작거나 같은 가장 오른쪽 인덱스가 -1이니 배열에 존재하지 않는다는 의미이다.
# 동시에, 배열에 -10보다 작거나 같은 원소가 없다는 의미이다. (= 배열의 모든 원소가 -10보다 크다는 의미)

idx2 = get_idx(arr, num2)
# idx2은 4가 나오게 된다. 즉, 6보다 작거나 같은 가장 오른쪽 인덱스가 4이다.
# 따라서 arr[0] ~ arr[idx2]는 6보다 작거나 같음을 만족하는 상태이다. (arr[idx2] < num2인 경우, 배열에 num2가 존재하지 않음.)

idx3 = get_idx(arr, num3)
# idx3는 10이 나오게 된다. 즉, 10보다 작거나 같은 가장 오른쪽 인덱스가 10이다.
# 따라서 arr[0] ~ arr[idx3]는 10보다 작거나 같음을 만족하는 상태이다. (arr[idx3] = num3인 경우, 배열에 num3가 존재함.)

위의 예시 코드에서 각 케이스 별로 뜻을 적어 놓았습니다. 함수의 의미가 "배열의 원소 중에서 K보다 작거나 같은 가장 오른쪽 인덱스를 반환한다"라는 점을 인지한다면 각 케이스마다 적어 놓은 의미가 당연하다는 생각이 드실 겁니다.
이를 활용하여 문제에 적용하는 더 디테일한 내용이 궁금하시면, 이분 탐색 알고리즘 [문제풀이] : BOJ 3020 강의의 2번째 풀이 코드를 참고하시면 좋을 것 같습니다.

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄