[TIL] Algorithm - 이분탐색(Binary Search) + 직접 주소 테이블이란?

1. 이분탐색  또는 이진검색

정렬된 리스트를 계속해서 반으로 나눠 원하는 값의 위치를찾는 알고리즘

<출처> Wiki

• 장점 : 검색이 반복될 때마다 목표값을 찾을 확률이 2배가 되므로 속도가 빠르다. → 시간복잡도 O(logN)
• 단점 :  정렬된 리스트에서만 사용이 가능하다.

이진 탐색 과정 참고 사이트
https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

Binary Vs Linear Search Through Animated Gifs

1. python 구현

'''
이분 탐색
list : 오름차순으로 정렬된 배열에 사용
key : 찾으려는 값

return
0 이상의 정수일 경우 :  찾으려는 값은 인덱스
None : 리스트 안에 존재하지 않는다.
'''
def binary_search(list, key) :
    # 탐색 범위 지정을 위한 변수
    left, right = 0, len(list)-1
    
    # left가 right보다 크면 이미 모든 영역 탐색 완료
    while left <= right :
        # 현재 탐색 범위 중간 인덱스
        middle = (left+right) // 2
        
        # 찾았으면
        if list[middle] == key :
            return middle
        # 찾으려는 값이 중간값 보다 작으면 right 변경
        elif list[middle] > key : 
            right = middle-1
        # 찾으려는 값이 중간값 보다 크면 left 변경
        else :
            left = middle+1

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :    
    nums = [1, 2, 3, 4, 5] 
    print(binary_search(nums, 5))

 

2. 이분 탐색 백준 문제 풀이

1. 1920번 - 수찾기

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

M = int(sys.stdin.readline())
target = list(map(int, sys.stdin.readline().split()))

def binarySearch(nums, key) :
    left, right = 0, len(nums)-1
    
    while left <= right :
        middle = (left+right)//2
        if nums[middle] == key :
            return 1
        elif nums[middle] > key :
            right = middle - 1
        else :
            left = middle + 1
    return 0

for key in target :
    print(binarySearch(nums, key))

2. 2805번 - 나무 자르기

import sys

N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

tree.sort()

def treeCut(tree, M) :
    left, right = 0, tree[N-1]
    height = 0
    
    while left <= right :
        # 현재 절단기의 높이
        middle = (left+right) // 2
        
        #현재 높이에서 나무를 잘랐을 때 구할 수 있는 나무 길이
        sum = 0
        for i in tree :
            if i > middle :
                sum += (i - middle)
        
        # 구한 나무의 길이가 필요한 만큼 딱 맞았을 경우
        if sum == M :
            return middle
        # 구한 나무의 길이가 부족할 경우 -> 높이를 낮춰줘야 한다.
        elif sum < M :
            right = middle - 1
        # 구한 나무의 길이가 이미 충분히 많은 경우 -> 높이를 높여야 한다.
        else :
            height = max(height, middle)
            left = middle + 1
            
    return height

print(treeCut(tree, M))

3. 2110번 - 공유기 설치

import sys

N, C = map(int, sys.stdin.readline().split())

house = []
for i in range(N) :
    house.append(int(sys.stdin.readline()))

house.sort()

def wifi(house, c) :
    # 공유기를 설치할 수 있는 최소 거리, 최대 거리
    min_len, max_len = 1, house[N-1] - house[0]
    length = 0
    
    while min_len <= max_len :
        # 현재 공유기를 설치할 수 있는 거리
        mid_len = (min_len + max_len) // 2
        
        # 설치된 공유기 개수
        count = 1
        current = house[0]
        for i in range(1, N) :
            # 현재 위치에서 공유기를 설치할 수 있는 거리보다 멀리 있으면
            if current + mid_len <= house[i]:
                count += 1
                current = house[i]
        
        # 현재 설치된 공유기의 개수가 가지고 있는 공유기의 개수보다 많은 경우
        # 즉, 더 멀찍이 설치할 수 있다.
        if count >= c :
            min_len = mid_len + 1
            length = max(length, mid_len)
        # 현재 설치된 공유기의 개수가 가지고 있는 공유기의 개수보다 적은 경우
        # 설정된 거리가 너무 멀기에 좀 가까워져야한다.
        else :
            max_len = mid_len -1
    return length

print(wifi(house, C))

4. 2470번 - 두 용액

import sys

N = int(sys.stdin.readline())

liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()

def search(liquid) :
    left, right = 0,  N-1
    # 최대한 0과 가까운 값 저장
    result = sys.maxsize
    
    # 반환할 값 - 특성값이 0에 가까운 용액을 만들어내는 값들
    result_left, result_right = 0, 0
    
    while left < right :
        # 특성값
        sum = liquid[left] + liquid[right]
        
        # 0에 최대한 가깝게 -> 비교를 쉽게 절댓값 사용
        if abs(sum) < result :
            result = abs(sum)
            result_left, result_right = liquid[left], liquid[right]
            # 특성값이 0이 된 경우
            if sum == 0 :
                return result_left, result_right
        # 특성값이 음수인 경우 -> 음수의 크기를 줄인다.
        if sum < 0 :
            left += 1
        # 양수인 경우 -> 양수의 크기를 줄인다.
        else :
            right -= 1
    return result_left, result_right

l, r = search(liquid)
print(f'{l} {r}')

---

위의 문제를 풀며 이분 탐색의 기법의 원리는 확실하게 알 수 있었다.
그러나 평소에 그냥 리스트에 접근할 인덱스를 가지고 주로 이분탐색을 공부했는데 실제 문제는 인덱스가 아닌 계산한 값 등 다양한 것들을 가지고 탐색을 해야하는 경우가 더 많았다. 
그래서 어떤 것을 이분 탐색을 할 것인지 직접 생각해보고 정하는 연습을 해야겠다.

---

2. 직접 주소화 방법

키들의 전체 집합 U가 적당히 작은 경우에 잘 동작하는 단순 기법

• 직접 주소 테이블 : 입력받은 value가 곧 key가 되는 데이터 매핑 방식
  • 키 k를 갖는 원소는 위치 k에 저장된다.
  • 장점 : 기본 사전적 연산(삽입, 수정, 삭제)은 구현하기 쉽다.
              찾고자 하는 값(value) = 테이블의 인덱스(key) 이므로 값이 저장된 공간에 바로 접근 가능 → 시간복잡도 O(1)
  • 단점 : 공간의 효율성이 좋지 않다.
             테이블에 넣고자 하는 데이터의 값의 범위 > 값의 개수 일 경우  공간은 할당되어 있지만 값은 없는 상태가 만들어진다.
             즉, 값의 개수 / 테이블 크기 = 적재율, 적재율이 낮을 경우 매우 비효율 적이다.

 

직접 주소 테이블을 너무나 잘 설명해주는 이미지

예를 들어 헬스장 신발장이 1번 부터 100번 까지 지정되어 있다.

각 회원마다 번호가 존재하는데 현재 회원은 3, 7, 98번 회원만 존재한다고 생각해보자

3번 회원의 사물함 = 3번 사물함 

7번 회원의 사물함 = 7번 사물함 

98번 회원의 사물함 = 98번 사물함 

그렇다면 나머지 사물함은 비어 있는 상태로 존재만 한다는 것이다.

직접 주소 테이블을 적절히 설명해주고 있는 사이트
https://velog.io/@kbm940526/자료구조-Hash-Table-너를-알아보자

자료구조 Hash Table 너를 알아보자 ~

이와 같은 문제점을 보완하기 위해 나온 방법이 Hashing 이라는 것이다.

내일 이어서 해시에 대해 공부해야겠다.