BOJ | 파이썬 | Sliver | 1920번 수 찾기 (with. 이진 탐색 알고리즘)

BOJ | Sliver | 1920번 수 찾기

문제

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

1920번: 수 찾기

코드

import sys

n = int(input())
numbers = list(map(int, sys.stdin.readline().split(' ')))
numbers.sort()

m = int(input())
check_numbers = list(map(int, sys.stdin.readline().split(' ')))

for chk in check_numbers:
    res = False
    start = 0
    end = n - 1
    
    while start <= end:
        mid = (start + end) // 2

        if numbers[mid] == chk:
            res = True
            break
        elif numbers[mid] < chk:
            start = mid + 1
        else:
            end = mid - 1
    
    if res == False:
        print(0)
    else:
        print(1)

풀이

이 문제를 보고 제일 먼저 떠오르는 방법은 탐욕 알고리즘(Greedy Algorithm)을 이용하는 방법일 것이다. (필자가 그렇게 풀고자 하였으나 불가능했다.) 탐욕 알고리즘 방법을 이용하기엔 주어지는 수의 범위가 크기 때문에 시간초과가 발생할 수 밖에 없었고, 시간초과를 해결하기 위해 이진 탐색 방법을 이용하였다.

• for문과 while문을 조합하여 문제를 해결
  • for문 : 목표로 하는 값을 변화시키기 위한 반복문
  • while문 : 이진탐색을 구현하기 위한 반복문

---

이진 탐색(Binary Search) 알고리즘

이진 탐색은 정렬된 배열에서 특정한 값을 찾을 때 사용할 수 있는 알고리즘이다. 배열의 중간 값과 찾고자 하는 값(target)을 비교하여, 중간 값이 찾고자 하는 값보다 크면 배열의 왼쪽 반을 탐색하고, 중간 값이 찾고자 하는 값보다 작으면 배열의 오른쪽 반을 탐색한다.

 

이진 탐색 알고리즘은 배열을 반으로 나누며 탐색 범위를 반으로 줄여가기 때문에, 탐색 범위가 반복문을 반복할 때마다 절반으로 줄어들게 된다. 이러한 이유로 시간 복잡도는 \( O(\log n) \)으로 나타낼 수 있으며, 탐색 방법 중에 효율적인 알고리즘이라고 할 수 있다. 

 

이진 탐색은 다음과 같이 반복문을 이용하여 구현할 수 있다.

def binary_search(arr, target):
    left = 0                          # 1. 왼쪽 인덱스를 초기화
    right = len(arr) - 1              # 2. 오른쪽 인덱스를 초기화

    while left <= right:              # 3. 왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같은 동안 반복
        mid = (left + right) // 2     # 4. 중간 인덱스를 계산
        if arr[mid] == target:        # 5. 중간 값이 찾고자 하는 값과 같다면,
            return mid                # 6. 중간 인덱스를 반환
        elif arr[mid] < target:       # 7. 중간 값이 찾고자 하는 값보다 작다면,
            left = mid + 1            # 8. 왼쪽 범위를 중간 값의 다음으로 설정
        else:                         # 9. 그 외의 경우에는,
            right = mid - 1           # 10. 오른쪽 범위를 중간 값의 이전으로 설정
    return -1                         # 11. 값을 찾지 못한 경우 -1을 반환합니다.

 

이진 탐색은 효율적인 알고리즘이지만, 다음과 같은 단점도 존재한다.

• 정렬된 배열이 필요 : 배열이 정렬되어 있지 않은 경우에는 이진 탐색을 적용할 수 없다.
• 삽입 및 삭제 시 추가적인 시간 소요 : 정렬된 배열이 필요하기 때문에 새로운 값이 배열에 추가되는 경우, 데이터를 새롭게 정렬하는데 추가적인 시간이 소요된다.
• 중복된 값 처리의 어려움 : 중복된 값이 있는 경우 이진 탐색을 사용하는 것이 어려울 수 있다.