백준 10815 파이썬 (이진탐색, Binary Search)

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

 

python의 in을 이용하여 풀려고 하면 시간초과가 나는 문제입니다. 문제에서 입력값이 "-10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다"라고 되어있기 때문에 이렇게 큰 수가 포함된 배열 문제는 이진탐색을 이용하면 좋습니다. 매 단계마다 범위를 절반으로 줄이기 때문입니다.

 

개념

이진탐색(Binary Search)은 정렬된 배열이나 리스트에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 이진탐색은 다음과 같은 방식으로 작동합니다:

1. 초기 설정: 배열의 시작 인덱스(left)와 끝 인덱스(right)를 설정합니다. 일반적으로 left는 0, right는 배열의 마지막 인덱스입니다.
2. 중간값 계산: 중간 인덱스(mid)를 계산합니다. mid = (left + right) // 2
3. 값 비교:
   • 배열의 중간값과 찾고자 하는 값을 비교합니다.
   • 중간값이 찾고자 하는 값과 같으면 검색을 종료합니다.
   • 중간값이 찾고자 하는 값보다 크면, 검색 범위를 중간값의 왼쪽 반으로 좁힙니다. (right = mid - 1)
   • 중간값이 찾고자 하는 값보다 작으면, 검색 범위를 중간값의 오른쪽 반으로 좁힙니다. (left = mid + 1)
4. 반복 또는 종료:
   • 위 과정을 값을 찾을 때까지 또는 left가 right보다 커질 때까지 반복합니다.
   • 만약 left가 right보다 커진다면, 배열에 찾고자 하는 값이 없다는 뜻입니다.

이진탐색은 매 단계마다 검색 범위를 절반으로 줄이기 때문에, 시간 복잡도는 O(log n)입니다. 이는 선형 탐색의 O(n) 보다 훨씬 효율적입니다.

예를 들어, 정렬된 배열 [1, 3, 5, 7, 9, 11]에서 값 7을 찾는 과정을 살펴보면 다음과 같습니다:

1. 초기 설정: left = 0, right = 5
2. 중간값 계산: mid = (0 + 5) // 2 = 2, 배열[2] = 5
3. 값 비교: 5 < 7이므로 left = mid + 1 = 3
4. 다시 중간값 계산: mid = (3 + 5) // 2 = 4, 배열[4] = 9
5. 값 비교: 9 > 7이므로 right = mid - 1 = 3
6. 다시 중간값 계산: mid = (3 + 3) // 2 = 3, 배열[3] = 7
7. 값 비교: 7 == 7이므로 값을 찾음.

 

백준 10815 code

def binary_tree(target, sang_card):
    left = 0
    rigth = len(sang_card) - 1
    while(left <= rigth):
        mid = (left + rigth) // 2
        if sang_card[mid] == target:
            return 1
        elif sang_card[mid] > target:
            rigth = mid - 1
        else:
            left = mid + 1
    return 0


n = int(input())
sang_card = list(map(int,input().split()))
m = int(input())
compare_card = list(map(int,input().split()))

sang_card.sort()

for target in compare_card:
    print(binary_tree(target, sang_card))