백준 - 1920번 수 찾기 python 문제풀이 [Hellfer]

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

1920번: 수 찾기

🔷 알고리즘 분류 - 이분 탐색, 시간 복잡도 O(logN)   

난이도 - 실버 4

이진 탐색(Binary Search) 알고리즘은 정렬된 데이터 집합에서 특정 값을 빠르게 찾아내는 탐색 알고리즘입니다. 

이진 탐색 알고리즘은 데이터 집합의 중간 요소와 찾고자 하는 값을 비교하여 탐색 범위를 절반씩 줄여나가며 값을 찾습니다.

이진 탐색 알고리즘의 과정은 다음과 같습니다:

1. 데이터 집합의 중간 요소를 선택합니다.

2. 중간 요소와 찾고자 하는 값이 같으면 탐색을 종료합니다.

3. 중간 요소가 찾고자 하는 값보다 크면, 중간 요소보다 작은 범위를 대상으로 탐색을 계속합니다.

4. 중간 요소가 찾고자 하는 값보다 작으면, 중간 요소보다 큰 범위를 대상으로 탐색을 계속합니다.

5. 이 과정을 반복하여 찾고자 하는 값을 찾거나, 탐색 범위가 없어질 때까지 계속합니다.

이진 탐색 알고리즘의 시간 복잡도는 O(logN)으로, 큰 데이터 집합에서도 효율적으로 탐색을 수행할 수 있습니다. 

하지만 이진 탐색을 수행하려면 데이터 집합이 미리 정렬되어 있어야 합니다. 

이진 탐색은 배열이나 리스트와 같은 순차적으로 접근 가능한 데이터 구조에서 특히 유용합니다.

 

아래는 이분 탐색 알고리즘의 기본 구조 코드입니다.

 

def binary_search(array, target):  # 이진 탐색 함수 정의. array는 탐색 대상 리스트, target은 찾고자 하는 값
    start = 0  # 시작점을 리스트의 첫번째 인덱스로 설정
    end = len(array) - 1  # 끝점을 리스트의 마지막 인덱스로 설정

    while start <= end:  # 시작점이 끝점보다 작거나 같은 동안 반복
        mid = (start + end) // 2  # 중간점을 계산 (시작점과 끝점의 중간)

        if array[mid] == target:  # 중간점의 값이 찾고자 하는 값이라면
            return mid  # 중간점의 인덱스 반환
        elif array[mid] < target:  # 중간점의 값이 찾고자 하는 값보다 작다면
            start = mid + 1  # 시작점을 중간점보다 하나 뒤로 이동
        else:  # 중간점의 값이 찾고자 하는 값보다 크다면
            end = mid - 1  # 끝점을 중간점보다 하나 앞으로 이동

    return None  # 탐색 대상이 리스트에 없는 경우 None 반환

🔶문제풀이 - 이분 탐색을 이용한 풀이,  시간 복잡도 O(logN)

import sys
input = sys.stdin.readline  # 입력을 빠르게 받기 위해 sys.stdin.readline을 사용합니다.

# 이진 탐색 함수
def binary_search(array, target, start, end):
    while start <= end:  # 시작점이 끝점보다 작거나 같을 동안 반복
        mid = (start + end) // 2  # 중간점을 구합니다.
        # 찾은 경우 1 반환
        if array[mid] == target:
            return 1
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return 0  # 원소를 찾지 못한 경우 0 반환

n = int(input())  # 원소의 개수 입력 받기
array = list(map(int, input().split()))  # 전체 원소 입력 받기
array.sort()  # 이진 탐색을 수행하기 위해 사전에 정렬 수행
m = int(input())  # 찾고자 하는 원소의 개수 입력 받기
x = list(map(int, input().split()))  # 찾고자 하는 원소 입력 받기

# 찾고자 하는 원소를 하나씩 확인
for i in x:
    print(binary_search(array, i, 0, n - 1))  # 각 원소에 대하여 이진 탐색을 수행하고 결과를 출력

🔶 문제 이해하기

# 이진 탐색 함수
def binary_search(array, target, start, end):
    while start <= end:  # 시작점이 끝점보다 작거나 같을 동안 반복
        mid = (start + end) // 2  # 중간점을 구합니다.
        # 찾은 경우 1 반환
        if array[mid] == target:
            return 1
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return 0  # 원소를 찾지 못한 경우 0 반환

 

다음과 같이 오름차순으로 정렬된 리스트와 찾고자 하는 값을 가정해 봅시다:

 

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7

 

이진 탐색 함수를 호출하면 다음과 같습니다:

 

print(binary_search(array, target, 0, len(array)-1))

 

이 함수는 리스트 array에서 target 값을 찾으려고 시도하며, 시작점(start)은 리스트의 첫 인덱스인 0이고, 끝점(end)은 리스트의 마지막 인덱스인 9입니다.

함수가 처음 호출되면, mid = (start + end) // 2는 (0 + 9) // 2 = 4가 되어 중간 인덱스를 가리킵니다. 리스트의 4번째 인덱스에 있는 값은 5입니다.

찾고자 하는 값인 7은 중간값 5보다 크므로, start를 mid + 1인 5로 업데이트하고 탐색을 계속합니다.

다음 반복에서 mid는 (5 + 9) // 2 = 7이 되어, 리스트의 7번째 인덱스를 가리키게 됩니다. 이 위치에는 우리가 찾고자 하는 값인 7이 있으므로, 함수는 1을 반환하며 종료합니다.

따라서, 위의 binary_search 함수 호출은 1을 출력하게 됩니다. 이는 target 값 7이 리스트 array 내에 존재함을 의미합니다.

 

🤗파이팅입니다~ 여러분!!🤗