[Algorithm] 이진 탐색(Binary Search)

1. 이진 탐색 개념
2. 이진 탐색 동작과정
3. 백준 10815번
4. 번외 (list vs set)

1. 이진 탐색 개념

이진 탐색은 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 내가 찾고자 하는 값이 선택될 때까지 탐색하는 알고리즘입니다. 또한,

이진 탐색 알고리즘은 입력 데이터가 많거나(1000만 단위 이상) 탐색 범위의 크기가 매우 넓을 때 효과적으로 문제를 해결 할 수 있습니다.

(반드시 정렬이 되어 있어야합니다.)

 

2. 이진 탐색 동작 과정

다음과 같이 오름차순으로 정렬 되어있는 배열이 있다고 가정해 보겠습니다.

 

이진 탐색은 배열을 반복해서 반으로 나누기 때문에 초기값, 끝값, 중간값이 필요합니다. 이 값들을 그림에 표시해보면

이런식으로 나타낼 수 있습니다. 배열의 초기 인덱스와 마지막 인덱스를 나타내는 변수로 start와 end를 사용하고, 이 두 값을 더한 후 2로 나누어 중앙 인덱스를 구한후 mid로 표시하였습니다. 여기서 타겟을 6으로 가정해보겠습니다.

이제 mid(중앙값)를 기준으로 3가지를 확인하면 됩니다.

 

1. target이 mid에 위치하는가?

2. 그렇지 않다면 target이 mid보다 큰 값인가?

3. 그렇지 않다면 target이 mid보다 작은 값인가?

 

1번의 경우에는 큰 문제가 없겠지만, 그렇지 않으면 추가적인 작업이 필요합니다. 주어진 예시는 2번에 해당합니다. 이 경우에는 start가 가리키는 값을 mid의 다음 인덱스로 변경하여, 다시 타겟 넘버와 mid가 일치하는지 확인합니다.

이전 mid의 값이 2였고 start를 mid의 다음 인덱스로 변경한다고 하였으니 3이 되었고 이를 기준으로 동일한 방법으로 mid값을 구해줍니다. 이제 mid의 값이 타겟 넘버와 일치하고 배열에 타겟 넘버가 포함되어 있다는 사실을 확인할 수 있습니다.

 

3, 백준 10815문제

사실 제가 위에 예시로 작성한 그림은 백준 10815 문제의 예제입니다.

 

위에서 얘기했던 이진 검색을 사용하면 쉽게 문제를 풀 수 있습니다. 코드는 아래와 같습니다.

 

N = int(input())
arr1 = list(map(int, input().split()))
M = int(input())
arr2 = list(map(int, input().split()))

arr1.sort()

def binary(i):
    start, end = 0, len(arr1) - 1

    while start <= end:
        mid = (start + end) // 2
        if arr1[mid] == i:
            return 1
        elif arr1[mid] < i:
            start = mid + 1
        else:
            end = mid - 1
    return 0


for i in arr2:
    print(binary(i), end=' ') #1 0 0 1 1 0 0 1

 

4. list vs set

위의 문제는 이진 검색 방법 외에도 다른 방법으로 풀 수 있는데, 저는 처음에 두개의 입력 값을 리스트로 만들고 값을 하나씩 if문을 사용하여 안에 값이 있는지 확인하는 코드를 작성하였습니다.

N = int(input())
arr1 = list(set(map(int, input().split())))
M = int(input())
arr2 = list(map(int, input().split()))

for i in arr2:
    if i in arr1:
        print(1,end=' ')
    else:
        print(0,end=' ')

 

이렇게 작성을 하였더니 시간 초과가 나왔고, 여기서 더 시간을 단축 시킬 수 있는 방법이 떠오르지않아 다른 사람의 해답을 보았습니다.

아래는 해답을 바탕으로 제 코드를 수정한 정답입니다.

N = int(input())
arr1 = set(map(int, input().split()))
M = int(input())
arr2 = list(map(int, input().split()))

for i in arr2:
    if i in arr1:
        print(1,end=' ')
    else:
        print(0,end=' ')

 

차이가 보이시나요? 바로 arr1 배열을 list가 아닌 set으로 만든 것 입니다. set으로 만들면 중복이 없기때문에 수가 더 적어지겠다는 생각은 했었지만 그렇다고 실행 시간에 차이가 있을정도는 아니라고 생각이 들어서 좀 더 알아보았습니다. 그러다 list와 set의 차이에 대해 알게 되었습니다.

 

결론부터 말하자면 list와 set은 내부적으로 데이터를 저장하고 검색하는 방식이 다르기 때문에 시간 복잡도에서 차이가 발생하는 것 입니다.

리스트 (list):

1. 저장 방식: 리스트는 순서가 있는 데이터를 저장하는데, 각 요소는 인덱스를 가지고 있습니다.
2. 검색 시간 복잡도: 리스트에서 특정 원소를 찾기 위해서는 해당 원소의 인덱스를 알아야 합니다. 리스트는 인덱스로 직접 접근하는 것이 가능하므로 검색 시간 복잡도는 O(N)입니다. 여기서 N은 리스트의 길이입니다.

집합 (set):

1. 저장 방식: 집합은 중복을 허용하지 않고, 순서가 없는 데이터를 저장합니다. 각 요소는 해시 함수를 사용하여 해시값에 매핑되어 저장됩니다.
2. 검색 시간 복잡도: 집합은 해시 테이블을 사용하여 각 요소에 대한 해시 값을 계산하고, 이를 기반으로 빠르게 요소를 검색할 수 있습니다. 일반적으로 검색 시간 복잡도는 O(1)입니다.

위와같은 차이로 중복을 허용하지 않아야 하고 검색 속도가 중요한 경우에는 list보다 set을 사용하는 것이 유용합니다.

 

 

참고자료

https://heytech.tistory.com/64

https://code-angie.tistory.com/3