[알고리즘] 이진 검색, 두 배열의 교집합 , 이진탐색 문제풀이

 

 

이진검색

https://leetcode.com/problems/binary-search/description/

정렬된 배열을 받는다.

그 배열에 n이 존재한다면 n의 위치를,

n이 존재하지 않는다면 -1를 return 한다. 

구현

def binary_search(nums, target):
    def bs(start, end):
        if start > end:
            return -1

        mid = (start + end) // 2

        if nums[mid] < target:
            return bs(mid + 1, end)
        elif nums[mid] > target:
            return bs(start, mid - 1)
        else:
            return mid

    return bs(0, len(nums) - 1)


assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=9) == 4
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=2) == -1

 

 

내장 (Python,Java)

일부 코딩테스트에서, bisect 라이브러리 사용을 금지하는 경우가 있습니다. 직접 구현하면서 익숙해지는 것을 추천드립니다.

def binary_search_builtin(nums, target):
    idx = bisect.bisect_left(nums, target)
    # idx == len(nums) 가능하기 떄문.
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if idx < len(nums) and nums[idx] == target:
        return idx
    else:
        return -1

 

bisect_left

[-1, 1, 2, 2, 2, 3] 2 ➡️  2 # 찾는 값이 있는데 여러개 있다면 가장 왼쪽 요소의 자리를 반환

 

<내가 찾는 값이 없는 경우>

[-1, 1, 3, 3, 5] 2  ➡️ 2 # 그요소보다 같거나 큰 녀석이 있는 자리를 반환

[-5, -4, -3, -2, -1] 2 ➡️ 5

[3, 4, 5, 6, 7] 2 ➡️ 0

 

bisect_right  bisect_left 만큼 중요하진 않고, 이런게 있다 정도만 알면 된다.

[-1, 2, 2, 2, 3, 4] 2 ➡️ 3 4

 

회전 정렬된 배열 검색

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

 

input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
output: 4

# nums = [4, 5, 6, 7, 0, 1, 2]

def bs_rotated(nums, target):
    def bs(lst, start, end):
        if start > end:
            return -1

        mid = (start + end) // 2
        if lst[mid] < target:
            return bs(lst, mid + 1, end)
        elif lst[mid] > target:
            return bs(lst, start, mid - 1)
        else:
            return mid

    if not nums:
        return -1
    
    # 리스트가 회전된 부분을 찾기
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    # 리스트를 회전 전 형태로 만듦
    # [4, 5, 6, 7, 0, 1, 2, 4, 5, 6, 7]
    added = nums + nums[:left]

    # 원래 리스트가 아닌 합쳐진 리스트에서 target을 찾으므로 이진 탐색의 결과가 added 리스트의 인덱스가됨
    result = bs(added, left, len(added) - 1)
    # 합쳐진 리스트의 인덱스이므로, 원래 리스트의 인덱스로 변환하기 위해 result % len(nums)
    return result if result == -1 else result % len(nums)

 

---

 

두 배열의 교집합

https://leetcode.com/problems/intersection-of-two-arrays/description/

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted. (순서는 상관x)

 

def intersec_arrays(nums1, nums2):
    if not nums1 or not nums2:
        return []
    
    # 중복 허용x. 유니크한 값만 저장하는 자료형 set 사용
    result = set()
    # 내장함수 sort는 시간복잡도 N*O(logN) 이하
    nums2.sort()
    # 이진탐색 (N*O(logN))
    for n1 in nums1:
        idx = bisect.bisect_left(nums2, n1)
        if len(nums2) > idx and n1 == nums2[idx]:
            result.add(n1)

    return list(result)

 

➡️ 전체 시간복잡도는 N*O(logN)

 

이중포문(O(N***2))으로 찾을수도 있지만,

이진탐색으로 풀면 시간복잡도가 훨씬 빠르게 풀 수 있다!

 

이진탐색은 정말 많이 사용하며 매우 중요하므로 꼭 능숙하게 사용할 수 있을 정도로 알아두자!

---

이진탐색 문제풀이

 

정렬된 배열에서 특정 수의 개수 구하기

def count_number(lst, target):
    left_idx = bisect.bisect_left(lst, target)
    
    # 찾는 값이 배열에 없다면 -1 반환
    if not (0 <= left_idx < len(lst) and lst[left_idx] == target):
        return -1

    right_idx = bisect.bisect_right(lst, target)
    return right_idx - left_idx


assert count_number(lst=[1, 1, 2, 2, 2, 2, 3], target=2) == 4
# 만약 그 수가 없다면 -1 반환
assert count_number(lst=[1, 1, 2, 2, 2, 2, 3], target=4) == -1

bisect_left, bisect_right를 잘 이해하면 간단하게 풀 수 있는 문제

---

고정점 찾기

# 인덱스와 인덱스의 값이 같은 한 지점을 찾아서 반환하기
# 없을 경우엔 -1 반환
# 시간복잡도 O(logN)제한 -> for문(O(N))으로 풀 수 없다!

def fixed_point(lst):
    lo = 0
    hi = len(lst)

    # 결과값 lo 는, i < lo 인 모든 i 에 대하여 lst[i] < i
    while lo < hi:
        # 중간 값을 잡는다.
        mid = (lo + hi) // 2
        # 값이 인덱스보다 작을 경우
        if lst[mid] < mid:
            # 오른쪽으로 간다
            lo = mid + 1
        # 값이 인덱스보다 클 경우
        else:
            # 왼쪽으로 간다
            hi = mid

    # 범위를 벗어나거나, 교차점이 없는 경우.
    # lo 는 0에서부터 출발하므로, lo < 0 인 것은 검사하지 않아도 됩니다.
    if lo >= len(lst) or lo != lst[lo]:
        return -1
    return lo


assert fixed_point([-1, 1, 3, 5, 7]) == 1
assert fixed_point([-15, -6, 1, 3, 7]) == 3
assert fixed_point([-15, -4, 2, 8, 9, 13, 15]) == 2
assert fixed_point([-15, -4, 3, 8, 9, 13, 15]) == -1
assert fixed_point([-15, -6, 1, 2, 5]) == -1
assert fixed_point([-15, -6, -5, -4, -3]) == -1
assert fixed_point([3, 4, 5, 6, 7]) == -1

index와 value가 만나는 저 지점이 바로 fixed point!.

 

배열의 중간값인 mid와 중간값을 비교하여 왼/오 어디쪽 탐색할지 결정

배열의 값이 인덱스에 비해 클 경우, 왼쪽에 교차점이 있는 것 ➡️ 왼쪽 탐색

배열의 값이 인덱스에 비해 작을 경우, 오른쪽에 교차점이 있는 것. ➡️ 오른쪽 탐색

---

공유기 설치

https://www.acmicpc.net/problem/2110

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다

def install_router(lst, C):
    # 1. 이분탐색을 위한 정렬
    lst.sort()

    # 2. 이분탐색 대상은 '최대거리'.
    # 최대거리의 최솟값은 1, 최댓값은 양 끝값의 차이.
    lo = 1
    hi = lst[-1] - lst[0]
    min_gap = 0

    # 3. 최대 거리를 찾을 때까지 이분탐색
    while lo <= hi:
        # mid : 공유기간 허용된 최대거리
        # 중간 거리를 시험해본다.
        mid = (lo + hi) // 2

        # 0번째 요소에 항상 설치하므로 1개를 깔고 간다. (거리를 최대화 하려면 0번째는 무조건 설치해야함)
        cnt = 1
        # 0번째 요소부터 시작.
        cur = lst[0]

        # 1번째 ~ 마지막 요소를 연결시켜본다.
        for i in range(1, len(lst)):
            # 연결만 된다면 더 멀리 있는 것도 괜찮다
            # 이해가 안된다면 문제의 예시인
            # [1, 2, 4, 8, 9] 를 최대거리 3으로 연결하는 경우를 찬찬히 생각해보자.
            # (1, 4, 8)에 설치한 경우, 1~4 거리는 3, 4~8 거리는 4다.
            # 가장 인접한 두 점의 최대 거리가 3이므로 4가 괜찮은 것이다.
            if lst[i] >= cur + mid:
                cur = lst[i]
                cnt += 1

        if cnt >= C:
            min_gap = mid
            lo = mid + 1
        else:
            hi = mid - 1

    return min_gap

# 설치하는 라우터 간의 거리가 최대가 되어야 한다. -> 최대 거리를 출력
assert install_router([1, 2, 8, 4, 9], 3) == 3