본문 바로가기
Algorithm/Concepts

이분 탐색(Binary Search)

by 컴돈AI 2023. 10. 14.

목차

    이분 탐색(Binary Search)

    • 이분 탐색(Binary Search)은 정렬된 배열에서 특정한 원소(또는 해당하는 위치의 인덱스)를 찾아내는 탐색 알고리즘입니다. 
    • 정렬된 배열의 중간에 있는 원소를 선택하여 찾고자 하는 값과의 크기를 비교하며 원하는 원소를 찾아냅니다.
      • 정렬된 배열의 중앙값과 찾고자 하는 값을 비교합니다.
      • 만약 중앙값이 찾는 값보다 크면, 중앙을 기준으로 왼쪽 부분 배열에서 탐색을 이어갑니다.
      • 만약 중앙값이 찾는 값보다 작으면, 중앙을 기준으로 오른쪽 부분 배열에서 탐색을 이어갑니다.
      • 원하는 값을 찾거나, 탐색할 부분 배열의 크기가 0이 될 때까지 이 과정을 반복합니다.
    • 또는 어떤 연속적인 값의 범위가 주어지고, 그 안에서 임의로 값을 지정해서 찾을 때도 이분 탐색을 적용할 수 있습니다. (입력값과 결과가 단조 증가 함수 관계이거나, 단조 감소 함수 관계가 있는 완전 탐색 문제(O(N))는 이분 탐색을 통해 O(logN)만에 탐색 가능)
      • 예를 들어, 값의 범위가 1부터 10억까지 주어져 있을때 사용이 가능합니다.
      • 해당 문제가 값이 증가할때 결과도 증가하거나 감소하는 등 단조 증가 감소 함수 관계에 있을 때 적용이 가능합니다.(또는 값이 감소할 때 결과도 감소하거나 증가하는 경우)
      • 만약 완전 탐색으로 찾게 되면 총 10억의 시간이 걸리지만, 가운데 값을 계속 집어넣으면서 값을 증가해야 할지 감소해야 할지 판단하면서 진행하게 되면 log(10억) 시간만에 해결이 가능합니다.
      • 단, 주의할 점은 값에 따라 결과가 방향성 없이 변화한다면 이분탐색을 적용할 수 없습니다. 어떤 범위가 큰 문제에서 이분탐색으로 문제를 풀고 싶을 때는 반드시 값이 증가할 때 결과가 증가하거나 감소하는 방향성이 존재해야 합니다.(반대로 값이 감소할 때 결과가 감소하거나 증가해야 합니다.)
      • 단조 증가 함수
        • x1 < x2 -> f(x1) <= f(x2)
      • 단조 감소 함수
        • x1 < x2 -> f(x1) >= f(x2)
    • 이분 탐색의 시간 복잡도
      • 탐색 범위를 절반씩 줄여나가며 비교 연산을 수행하기 때문에 O(log N)의 시간복잡도를 가집니다.
      • 그러나 이분탐색을 수행하기 전에 배열이 정렬되어있지 않다면 그 배열을 정렬하는데 시간복잡도가 O(N log N)이 걸리게 됩니다. 따라서 이분 탐색은 정렬되어 있지 않는 배열에는 효과적이지 않습니다.
      • 정리하면, 이분 탐색은 정렬된 배열에서 O(log N)만에 원하는 값을 찾아낼 수 있습니다.
    • 찾는 부분에 따라 이분 탐색의 코드가 달라 질 수 있습니다.
      • [input에 따라 output이 단조 증가하는 경우 (x1 < x2 -> f(x1) <= f(x2)) ]

          • input 좌표가 증가할수록 output값은 단조 증가할것입니다.
        • 오름차순으로 정렬된 array에 대해 index를 찾는 과정을 예시로 들어보겠습니다. (이때 input은 index가 될것이고, 오름차순으로 정렬됐기 때문에 array[index]의 결과는 단조 증가 함수가 됩니다.)
          • 1. target값보다 output값이 작은 값 중 input이 최댓값
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] < target:
            start = mid + 1
        else:
            end = mid
    return start - 1

              • 코드를 살펴보게 되면 결국 start>=end 인 지점에서 종료되게 됩니다.
                • start는 output값이 target값하고 같아지면 더이상 업데이트 되지 않습니다. (target하고 같아지기 전 start는 start=mid+1로 output이 target과 같아지기 시작하는 input의 시작점(최솟값)까지 업데이트 됩니다.)
                • end의 경우는 output값이 target보다 작아지면 더이상 업데이트 되지 않습니다. (target보다 작아지기 전 end는 end=mid로 output이 target과 같아지기 시작하는 input의 시작점(최솟값)까지 업데이트 됩니다.)
                • 결국 start, end 모두  output이 target과 같아지기 시작하는 input의 시작점(최솟값)까지 업데이트가 됩니다. (같아지면 while 문 종료)
              • 따라서 target값보다 output값이 작은 값 중 최댓값은 start-1을 return 하면 됩니다.
          • 2. target값과 output값이 같은 값 중 input이 최솟값 (target값을 만족하는 경우가 없다면 target보다 output 값이 큰 값중 input이 최솟값)  [= output이 target값보다 크거나 같은 값중 input 최솟값 구하기]
            • output이 target값보다 크거나 같은 값중 input 최솟값
              • = (output이 target값보다 작은값 중 최댓값 +1 )
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] < target:
            start = mid + 1
        else:
            end = mid
    return start
              • 1번과 모두 동일하고 return 값만 start-1이 아닌 start를 return 합니다. ( start, end 모두 output이 target과 같아지기 시작하는 input의 시작점(최솟값)이기 때문입니다.)
              • target과 같은 지점이 없다면 target보다 커지기 시작하는 input의 시작점을 return 할 것입니다.
          • 3. target값과 output값이 같은 값 중 input이 최댓값 ( target값을 만족하는 경우가 없다면 target보다 output 값이 작은 값중 input이 최댓값 ) [= output이 target값보다 작거나 같은 값중 input 최댓값 구하기] 
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return start - 1
              • 코드를 살펴보게 되면 결국 start>=end 인 지점에서 종료되게 됩니다.
                • start는 output값이 target값보다 커지면 더이상 업데이트 되지 않습니다. (target보다 커지기 전 start는 start=mid+1로 output이 target보다 커지기 시작하는 input의 시작점(최솟값)까지 업데이트 됩니다.)
                • end의 경우는 output값이 target과 같아지면 더이상 업데이트 되지 않습니다. (target과 같아지기 전 end는 end=mid로 output이 target보다 커지기 시작하는 input의 시작점(최솟값)까지 업데이트 됩니다.)
                • 결국 start, end 모두 output이 target보다 커지기 시작하는 input의 시작점(최솟값)까지 업데이트가 됩니다. (같아지면 while 문 종료)
              • 따라서 target값과 output값이 같은 값 중 input이 최댓값은 start-1을 return 하면 됩니다. ( start, end 모두 output이 target보다 커지기 시작하는 input의 시작점(최솟값) 이기 때문입니다.)
              • target과 같은 지점이 없다면, 결국에는 target보다 작은 값 중 최댓값이 구해질것입니다. (start-1이기 때문에)
          • 4. target값보다 output값이 큰 값 중 input이 최솟값
            • target값보다 output값이 큰 값 중 input이 최솟값
              • = (output값이 target값보다 작거나 같은 값 중 input이 최댓값 +1 )
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return start
              • 3번과 모두 동일하고 return 값만 start-1이 아닌 start를 return 합니다. ( start, end 모두 output이 target보다 커지기 시작하는 input의 시작점(최솟값)이기 때문입니다.)
      • [input에 따라 output이 단조 감소하는 경우 (x1 < x2 -> f(x1) >= f(x2)) ]

          • input 좌표가 증가할수록 output값은 단조 감소할것입니다.
        • 내림차순으로 정렬된 array에 대해 index를 찾는 과정을 예시로 들어보겠습니다. (이때 input은 index가 될것이고, 내림차순으로 정렬됐기 때문에 array[index]의 결과는 단조 감소 함수가 됩니다.) 
          • 단조 증가에 대한 코드에서 부등호 방향만 반대로 바꿔주면 나머지 코드들은 모두 동일합니다.
            • 간단히 생각해보면 input이 증가할때 array[mid]는 단조 감소입니다. 따라서 output 값이 target보다 크다면 input은 현재 원하는 값보다 작은 상태입니다. 따라서 start를 키워줘야합니다.
          • 1. target값보다 output값이 큰 값 중 input이 최댓값
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] > target:
            start = mid + 1
        else:
            end = mid
    return start - 1
          • 2. target값과 output값이 같은 값 중 input이 최솟값 (target값을 만족하는 경우가 없다면 target보다 output 값이 작은 값중 input이 최솟값)  [= output이 target값보다 작거나 같은 값중 input 최솟값 구하기] 
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] > target:
            start = mid + 1
        else:
            end = mid
    return start
          • 3. target값과 output값이 같은 값 중 input이 최댓값 ( target값을 만족하는 경우가 없다면 target보다 output 값이 큰 값중 input이 최댓값 ) [= output이 target값보다 크거나 같은 값중 input 최댓값 구하기] 
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] >= target:
            start = mid + 1
        else:
            end = mid
    return start - 1
          • 4. target값보다 output값이 작은 값 중 input이 최솟값
            • def find(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end) // 2
        if array[mid] >= target:
            start = mid + 1
        else:
            end = mid
    return start
      • 주의할 점
        • start와 end를 처음 세팅할때는 start는 포함되는 범위, end는 포함되지 않는 범위
        • 즉, start<= 될 수 있는 값들 < end 입니다. 
        • 이거를 생각해서 end 값의 범위를 지정해주어야합니다.
        • 코드를 start 기준으로 작성하였기 때문에, 만약 end를 포함되는 범위의 값(즉, 최댓값)으로 설정했다면, start가 변화하다가 end에 도달해서 end 값을 한번 더 체크를 진행해야하는데 start=end일때, while문이 종료되므로 올바르지 않는 결과가 나올 수 있습니다. 
        • 따라서 항상 start<= 될 수 있는 값들 < end 이것을 생각해서 초깃값 세팅을 진행해주어야합니다.
        • 연산도중에도 end는 값의 최대범위+1입니다. 즉, 될 수 있는 값들의 범위가 계속해서 start<=될 수 있는 값들의 범위 < end 로 축소되고 있는 것입니다. 결국 종료는 될수 없는 값인 end에서 종료가 될것입니다.
          • 될 수 없는 값이란 while문 안의 첫번째 if문 안의 범위를 벗어나는 값을 의미합니다. 
          • while문은 결국엔 start=end 인지점에서 종료될것이고 이때는 될 수 없는 값이기때문에 최댓값의 경우에는 start-1을 하면되고, 만약 최솟값을 구하라고 하는것이라면 그 최댓값을 구하고 난 뒤 그 최댓값에서 1을 더한 값이 된것입니다.(즉 start-1+1 = start)
            • 따라서 1번과 2번의 코드가 동일하고 return 값에서 start-1과 start의 차이가 존재하는 것입니다.
            • 마찬가지로 3번과 4번코드도 코드가 동일하고 return 값에서 start-1과 start의 차이가 존재하는 것입니다.
    • 정리
      • start<= 될 수 있는 범위 < end 로 start와 end 초기 범위 설정 
      • while문안에서 if 문은 조건을 만족시킬수있는 최댓값 기준으로 작성해줍니다. (최솟값을 구하라고 하면, 그 반대범위의 최댓값 기준으로 작성)
        • 예시 
          • 단조 증가이면서, target값보다 output값이 작은 값 중 input이 최댓값 
            • if output < target:
    start=mid+1
            • 결과는 return start-1 이 됩니다.
              • 최종 결과 start는 우리가 원하는 범위보다 1이 클것이기 때문입니다.
          • 단조 증가이면서, target값보다 output값이 큰 값 중 input이 최솟값
            • 최솟값을 구하라고 한다면 반대범위를 생각
              • target보다 output값이 큰 값 -> target보다 output 값이 같거나 작은 값
            • if output <= target:
    start = mid+1
            • 결과는 return start 입니다.
              • 최종 결과 start는 output<=target 범위보다 1이 클것이기 때문에 결국엔 start 자체가 output>target이 되는 최솟값이 됩니다.
          • 단조 감소이면서, output이 target값보다 작거나 같은 값중 input 최솟값 구하기
            • 최솟값을 구하라고 한다면 반대범위 생각
              • output이 target값보다 작거나 같은 값  -> output이 target보다 큰값
            • if output > target:
    start = mid+1
            • 결과는 start
              • 최종 결과 start는 output > target 범위보다 1이 클것이기때문에 결국엔 start 자체가 output<=target이 되는 최솟값이 됩니다. (단조감소인것 생각)
          • 단조 감소이면서, output이 target값보다 크거나 같은 값중 input 최댓값 구하기 
            • if output>=target:
    start=mid+1
            • 결과는 start-1
              • 최종 결과 start는 output>=target 범위보다 1이 클것이기 때문에 결국엔 start 자체가 output<target이 되는 최솟값입니다. 따라서 start-1을 해줘야 output>=target을 반족시키는 최댓값이 됩니다.
    • bisect_left와 bisect_right로 보는 이분 탐색
      • bisect_left와 bisect_right는 모두 특정 배열에서 값을 삽입할 위치를 위치를 찾습니다. 차이점은 아래와 같습니다.
        • bisect_left(array,x) 
          • x와 같은 값이 이미 배열에 있을 경우, x를 이미 존재하는 같은 값들의 왼쪽에 삽입할 위치를 반환합니다. 즉, x의 삽입 위치는 x와 같은 값 중 가장 왼쪽 인덱스입니다.
          • x가 배열에 없으면 x보다 작고, x보다 큰 값 사이에 삽입하면 됩니다. 해당 위치의 인덱스는 x보다 큰 값중 가장 작은 값의 인덱스가 될 것 입니다.
          • 결국, bisect_left는 단조증가기준 2. target 값을 만족하면서 최솟값 ( target값을 만족하는 경우가 없다면 target보다 큰 값중 최솟값)  [결국, target값보다 크거나 같은 값중 최솟값 구하기] 의 경우가 됩니다.
        • bisect_right(array,x) 
          • x와 같은 값이 이미 배열에 있을 경우, x를 이미 존재하는 같은 값들의 오른쪽에 삽입할 위치를 반환합니다. 즉, x의 삽입 위치는 x와 같은 값 중 가장 오른쪽 위치의 다음 위치입니다. 결국 x보다 큰 값 중 가장 작은 값의 인덱스를 반환한다고 이해할 수 있습니다.
          • x가 배열에 없으면 x보다 작고, x보다 큰 값 사이에 삽입하면 됩니다. 해당 위치의 인덱스는 x보다 큰 값중 가장 작은 값의 인덱스가 될 것 입니다.
          • 결국 bisect_right의 경우 x보다 큰 값 중 가장 작은 값의 인덱스를 반환하면 됩니다. ( 단조증가기준 4. target 값보다 큰 값 중에 최솟값 의 경우가 됩니다.)
      • bisect_left / bisect_right 예시 코드 
        • from bisect import bisect_left, bisect_right

arr = [1, 2, 4, 4, 4, 5, 6, 7, 8, 9, 10]
print(bisect_left(arr, 2))   # 1
print(bisect_right(arr, 2))  # 2

print(bisect_left(arr, 3))   # 2
print(bisect_right(arr, 3))  # 2

print(bisect_left(arr, 4))   # 2
print(bisect_right(arr, 4))  # 5
      • bisect_left / bisect_right를 직접 구현한 경우
        • bisect_left -> 단조증가, target값보다 크거나 같은 값중 최솟값  
          • 최솟값은 반대범위 생각하고 최댓값 구한 start값 바로 return
            • arr[mid]<target 찾고 return 하기
          • def bisect_left(arr, target):
    start, end = 0, len(arr) - 1
    while start < end:
        mid = (start + end) // 2

        if arr[mid] < target:
            start = mid + 1
        else:
            end = mid

    return start
        • bisect_right -> 단조증가, target 값보다 큰 값 중에 최솟값
          • 최솟값은 반대범위 생각하고 최댓값 구한 start값 바로 return
            • arr[mid]<=target 찾고 return 하기
          • def bisect_right(arr, target):
    start, end = 0, len(arr) - 1
    while start < end:
        mid = (start + end) // 2

        if arr[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return start

    예시

    • [백준 1654] 랜선 자르기.
      • K개의 랜선을 일정한 크기로 잘라내서 길이가 같은 N개의 랜선을 만들어야 합니다. 랜선의 길이는 2^31-1 보다 작거나 같은 자연수이기 때문에 완전 탐색으로 찾아내기에는 엄청난 시간이 걸리게 됩니다.
        • 길이 1로 잘랐을때 잘라진 랜선의 개수, 길이 2로 잘랐을때 잘라진 랜선의 개수  길이 3으로 잘랐을때, 잘라진 랜선의 개수, ... 이런식으로 모든 길이에 대해서 완전탐색으로 해결 부가능합니다.
      • 하지만, 랜선을 일정한 크기로 잘라낼 때 일정한 크기가 작아지면 더 많은 수의 랜선을 만들 수 있고, 크기가 커지면 더 적은 수의 랜선을 만들 수 있습니다. 즉, 잘라내는 크기와 랜선의 수는 단조 감소 관계를 가지고 있습니다. 따라서 이분탐색을 통해 시간을 줄여 해결할 수 있게 됩니다.
        • 특정 값에 따라 결과가 단조 증가 / 단조 감소 관계 -> 이분탐색 적용가능
        • (O(N) -> O(log(N)) 단축
      • 찾는 부분이 위 설명의 4가지중 어디에 속하는지 확인이 필요합니다.
        • 우선 단조 감소 함수 (랜선의 길이가 늘어나면 -> 개수의 수는 줄어듭니다.) 
        • N개를 만들 수 있는 랜선의 최대 길이를 출력하기 (=최댓값)
          • 즉, target(N)개(또는 target(N)개보다 많이)를 만들면서 값이 최대인것 찾기.
          • 즉 output값이 target값과 같거나 작으면서 최댓값을 찾기
            • if output>=target 으로 한뒤에 return start-1 을 해주면 됩니다.
      • 코드 
        • import sys

input = sys.stdin.readline

k, n = map(int, input().split())

arr = [int(input()) for _ in range(k)]


def find(arr, n):
    start, end = 1, max(arr) + 1

    while start < end:
        mid = (start + end) // 2

        output = sum([item // mid for item in arr])
        if output >= n:
            start = mid + 1
        else:
            end = mid

    return start - 1


print(find(arr, n))
    • [프로그래머스] 징검다리
      • 문제에서 10억 이런 범위가 보인다면, log(N)문제를 생각할 수 있습니다. 대표적으로 이분탐색이 있기 때문에 이분탐색을 생각해서 문제를 접근해볼 수 있습니다.
      • n개의 바위를 제거했을때 구한 거리의 최솟값중 가장 큰 값을 구해야합니다.
        • input은 돌 사이의 최소거리
        • output은 해당 돌 사이 거리를 적용했을때 돌 사이의 최소거리보다 작은 돌들을 제거했을때, 제거한 돌의 개수
        • output과 input은 단조 증가 관계입니다.
        • input(돌 사이 최소거리)이 증가하면 output(제거한 돌의 개수)은 더많아집니다.  (돌 사이 최소 거리가 증가했다는 것은 그만큼 돌을 더 많이 제거해야합니다.)
        • 이 output이 target n개 이하로 나오면 됩니다.
          • 돌을 더 적게 제거해도 input인 돌 사이의 최소거리를 다 만족한다면 아무거나 추가적으로 제거해줘도 되기 때문입니다.
        • 즉, output<=target 인 input의 최댓값을 구하면 됩니다.
      • 코드 
        • def solution(distance, rocks, n):
    rocks = sorted(rocks)+[distance]
    
    start,end = 1,distance+1
    
    while start<end:
        mid = (start+end)//2
        
        output = 0
        before_point = 0
        
        for d in rocks:
            if d-before_point>=mid:
                before_point=d
            else:
                output+=1
        
        if output<=n:
            start = mid+1
        else:
            end = mid
            
    return start-1
    • [백준 2110] 공유기 설치
      • 좌표가 10억까지 나타나져있습니다. 이를 보고 이분탐색을 생각해볼 수 있습니다.
      • input  : 가장 인접한 두 공유기 사이의 거리(즉, 두 공유기 사이의 거리들 중에서 최솟값)
      • output : 설치가능한 집의 개수
      • target : C개
      • 단조 감소함수
        • 가장 인접한 두 공유기 사이의 거리(input)가 증가하면 설치 가능한 집의 개수가 줄어들게 됩니다. 
        • 가장 인접한 두 공유기 사이의 거리가 작을 경우 설치 가능한 집의 개수가 많아지게 됩니다.
      • output>=target 일때 input의 최댓값을 구하기
      • 코드
        • import sys

input = sys.stdin.readline

n, c = map(int, input().split())

arr = [int(input()) for _ in range(n)]
arr.sort()
start, end = 1, arr[-1] - arr[0] + 1

while start < end:
    mid = (start + end) // 2

    output = 1
    before_point = arr[0]
    # 제일 처음을 설치해야 가장 인접한 두 공유기 사이의 거리가 최대
    # 굳이 2번째이상부터 설치할 필요가 없습니다. 
    # 2번째 이상부터 설치할거를 제일 처음에 설치하면 
    # 가장 인접한 두 공유기 사이의 거리가 더 커질것이기 때문입니다.
    for i in range(1, n):
        if arr[i] - before_point >= mid:
            output += 1
            before_point = arr[i]

    if output >= c:
        start = mid + 1
    else:
        end = mid

print(start - 1)
    • [백준 1450] 냅색문제
      • 물건은 최대 30개 입니다. 
      • 물건을 넣거나 안넣거나 즉,  모든 경우의 수는 2^30이 됩니다. 그러므로 모든 경우의 수를 체크하는 것은 어렵습니다.
        • 2^24 정도까지만 연산은 가능합니다. ( 2^24 = 약 2000만)
      • 물건 N개를 A,B 세트로 N/2개 씩 나눕니다.
        • N/2로 나누게 되면 N/2의 최대 모든 경우의 수는 2^15가 됩니다.
        • 이는 약 3만정도로 충분히 계산할 만합니다.
      • A총무게 + B세트총무게 <= 가방 최대무게 이면 되기 때문에 A세트의 약 3만개에 대해서 B세트 무게리스트중 가방최대무게 - (A세트 특정값) 보다 작은 값들을 이분탐색을 통해 찾습니다.
        • 이런식으로 너무 많은 조합이 있을 경우 절반으로 나눠서, 가능한 값을 이분탐색으로 찾아주면 훨씬더 빠르게 찾을 수 있습니다.
      • 코드 
        • import sys
from itertools import combinations
from bisect import bisect_right

input = sys.stdin.readline

n, c = map(int, input().split())

arr = list(map(int, input().split()))

A_list = arr[: n // 2]
B_list = arr[n // 2 :]


def get_weights_list(arr):
    weights = []
    for i in range(len(arr) + 1):
        for comb in combinations(arr, i):
            weights.append(sum(comb))

    return sorted(weights)


A_weights_list = get_weights_list(A_list)
B_weights_list = get_weights_list(B_list)

count = 0
for a in A_weights_list:
    remain = c - a
    if remain >= 0:
        idx = bisect_right(B_weights_list, remain)
        count += idx

print(count)
    • [프로그래머스] 주사위 고르기
      • 이 문제 또한 위 문제처럼 생각해볼 수 있습니다.
      • 주사위를 n개중 n//2를 고른뒤 나머지 주사위의 가능한 결과와 뽑은 주사위의 가능한 결과를 모두 비교해서 승패결과를 작성해야합니다.
      • 이럴 경우 우선 n개중 n//2를 선택하는 nC(n//2)의 시간이 소요될 것입니다. 최대 n은 10개이므로 10C5
      • 여기서 추가적으로 5개의 주사위의 모든 경우의수 6**5, 나머지 주사위의 모든 경우의수 6**5가 소요될 것입니다.
      • 여기서 이제 6**5과 6**5의 모든 원소를 비교한다면 시간복잡도 개념으로 O(N^2)이 소요될것입니다.
      • 하지만 만약 여기서 나머지 주사위의 모든 경우의 수 6**5의 원소에 대해서 먼저 정렬을 수행한뒤에 이분탐색을 통해 비교를 진행하게 되면 O(NlogN)의 시간복잡도로 해결이 가능합니다.
        • 처음 6**5 를 정렬할때 시간이 NlogN 소요  
        • 6**5개의 모든 원소에 대해서(N) 정렬된 6**5의 원소에 이분탐색을 진행(logN) -> NlogN
        • 결국 O(NlogN) + O(NlogN) = O(NlogN)으로 O(N^2)보다 시간이 효율적으로 됩니다.
      • 이처럼 정렬이 되어 있지 않더라도, 만약에 탐색을 자주해야하는 경우에는 즉, N^2이 걸리는 경우에는 한 원소를 정렬해두고 탐색을 진행하면 정렬할때 NlogN이 걸리지만, 탐색할때는 logN이 걸려 N^2이 아닌 총 NlogN 만에 해결가능합니다.
      • 따라서 무조건 이분 탐색을 정렬이 되어 있지 않다면 사용하지 않기보다는 문제의 상황을 고려하여 효율성을 판단해서 사용해야합니다. (즉, 정렬되어 있지 않더라도 정렬해서 사용할 수 있음.)
      • 코드 
        • from itertools import combinations, product
from bisect import bisect_left
def solution(dice):
    answer = []
    n = len(dice)
    idx_list = [i for i in range(n)]
    idx_set = set(idx_list)
    
    max_count = 0
    max_comb = 0
    for comb in combinations(idx_list,n//2):
        available_list_1=[sum(item) for item in product(*[dice[idx] for idx in comb])]
        
        diff_comb = idx_set-set(comb)
        available_list_2=[sum(item) for item in product(*[dice[idx] for idx in diff_comb])]
        available_list_2.sort()
        total_len = len(available_list_2)
        count=0
        for item in available_list_1:
            count += bisect_left(available_list_2,item)
        if count>max_count:
            max_count = count
            max_comb = comb
    
    answer = sorted(list(max_comb))
    answer = [item+1 for item in answer]
    
    return answer

    'Algorithm > Concepts' 카테고리의 다른 글

    BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색)  (0) 2023.10.16
    동적 계획법(DP, Dynamic Programming)  (0) 2023.10.15
    분할 정복(Divide and Conquer)  (0) 2023.10.12
    탐욕법(Greedy)  (1) 2023.10.10
    큐(Queue), 스택(Stack)  (1) 2023.10.10

    관련글

    티스토리툴바