이분탐색

Charpter. 0 자료구조

이해

자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 문제없이 빠르게 실행할 수 있는 코드를 작성하고 전문성을 키우려면 자료구조를 알고 성능에 미칠 영향을 이해해야 한다. 비슷해 보이는 배열과 집합을 통해 두 자료구조를 분석한다.

Charpter. 1 배열

1. 연산

배열은 기초적인 자료 구조 중 하나이다.

array = ["white", "black", "red" , "blue", "green"]

대부분의 자료구조는 네가지 기본 방법을 사용하며 연산이라고 부른다.

읽기 : 자료구조내 특정 위치를 찾는다. ex) 인덱스 값 찾기
찾기 : 특정값이 배열에 들어가 있는지 확인한다. ex) "red"가 배열에 있는가
삽입 : 자료 구조에 새로운 값을 추가한다. ex) "brown"을 추가
삭제 : 자료 구조에서 값을 제거한다. ex) "black"을 제거

2. 연산 단계

연산이 빠른가는 연산에 걸리는 시간 관점이 아니라 얼마나 많은 단계가 필요한가로 접근해야한다.

읽기 : 배열에서 읽기는 한단계가 필요하다. 컴퓨터는 특정 인덱스에 한번에 접근가능하다.
검색 : 배열에서 값을 찾을 때 인덱스 0에서 값을 확인 후 다음 인덱스로 이동하여 찾을 때까지 이를 반복한다. 이를 선형 검색이라 한다(한번에 한셀식 확인하는 방법)
삽입 : 배열의 끝에 값을 추가한다면 한단계면 충분하다. 그러나 처음이나 중간일 경우 데이터 조각을 이동시켜야한다.
삭제 : 삽입과 비슷하나 순서가 반대이다. 삭제하는 것은 한단계이지만 공간을 없애려면 데이터를 이동시켜야한다.

Chapter. 2 집합

1. 연산 단계

배열 기반 집합과 배열의 유일한 차이점은 중복 값을 절대 허용하지 않는다는 것이다.

읽기 : 배열과 동일
검색 : 배열과 동일
삽입 : 집합에서는 배열에서와는 다르게 이 값이 집합에 있는지 검색이 선행되어야 한다. 이후에는 동일하다.
삭제 : 배열과 동일

Chapter 3. 정렬된 배열

1. 연산 단계

정렬된 배열은 항상 값이 순서대로 있어야 한다.

읽기 : 배열과 동일
검색 : 정렬된 배열에서 선형 검색은 값이 배열에 들어 있지 않을 떄 검색을 더 빨리 멈출 수 있다. 정렬된 배열의 장점은 이분탐색을 쓸 수 있다는 점이다.
삽입 : 삽입 전에 검색을 먼저 수행해서 삽입할 올바른 위치를 정해야 한다. 수행할 위치 앞 뒤 값을 비교한다.
삭제 : 배열과 동일

2. 이분 탐색

임의의 숫자 맞추기 게임을 한적이 있을것이다. 1에서 100까지의 숫자중 임의의 숫자를 맞춰야 한다면 우리는 직관적으로 어떻게 해야하는지 알고있다. 가장 빠르게 정답에 접근하기 위해 1을 고르는 사람은 없을 것이다.
다음은 python으로 구현한 이분탐색이다.

def binary_search(array, value):
    
    # 찾으려는 값의 상한선과 하한선을 정한다.
    # 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.
	lower_bound, upper_bound = 0 , len(array)
 	
    # 상한선과 하한선 사이의 가운데에서 값을 계속해서 확인하는 루프를 시작한다.
    while lower_bound <= upper_bound:
		
        # 중간 지점을 찾는다.
    	mid = ( lower_bound + upper_bound) // 2
        
        # 중간 지점의 값을 확인한다. 찾는 값이라면 검색을 끝낸다.
        # 그렇지 않으면 상한선이나 하한선을 바꾼다.
        if array[mid] == value:
        	return mid 
        elif array[mid] > value:
        	upper_bound = mid - 1
        else:
        	lower_bound = mid + 1
# 만약 해당 탐색이 끝날 때 까지 반환이 되지 않았다면 주어진 리스트에 조건이 없다는 의미입니다.

작은 크기의 정렬된 배열이라면 이진검색이 선형검색보다 크게 나은점은 없다. 하지만 배열이 커질수록 단계수는 달라진다. 100개일 때의 선형검색은 최대 100단계를 필요로 하지만 이진검색일 경우 7단계만을 필요로 한다. 10000개인 배열에서는 이진검색일 경우 최대 20단계면 된다. 정렬된 배열에 이분 탐색을 쓸 수 있으니 항상 정렬된 배열만을 써야하는 것은 아니다. 상황에 따라 빠르게 처리하는 자료 구조를 이용하자.

마치며

이 포스트는 도서 누구나 자료 구조와 알고리즘을 읽고 정리한 내용을 작성한 글입니다.