[백준] 1920번 수 찾기 파이썬 (python)

 

1920번: 수 찾기

 

문제

---

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 

 

입력

---

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

---

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

정답 코드

---

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

N = int(input())
A = list(map(int, input().split()))
A.sort()  # 리스트 A를 정렬해야 이분 검색을 할 수 있음

M = int(input())
B = list(map(int, input().split()))

for i in B:
    if binary_search(A, i):
        print(1)
    else:
        print(0)

 

풀이

---

위 문제는 시간 복잡도를 O(n)에서 O(log n)으로 줄일 수 있냐 없냐를 물어보는 문제이다. 선형법으로 푼다면 간단하게 풀리는 문제이지만, 실버 4는 그렇게 간단하게 풀라고 주는 문제는 아닐 것이다. 

위 문제는 이분(이진) 검색을 사용하여 풀어야 한다. 이분 검색은 리스트의 처음부터 끝까지 순차적으로 검색하는 선형(순차) 검색과 다르게 매 단계마다 검색의 범위를 반으로 줄여가며 원하는 수를 찾는 알고리즘이며, 데이터베이스나 파일에서 특정 값을 검색할 때 효과적이다. 

 

이분 검색의 특징은 다음과 같다:

 

1. 검색의 범위를 반으로 줄이기 위해 먼저 배열을 정렬하는 것이 필요하다. 
2. 검색이 수렴할 때까지 반복한다. 

문제의 풀이로 더 자세한 내용을 알아보자.

 

함수 binary_research는 다음과 같은 기능을 수행한다. 

 

1. 시작과 끝 지점을 설정한다. 일반적으로 시작은 right, 끝은 left로 변수를 두며 각각 0과 배열의 길이 - 1의 인덱스를 가진다. 
2. 그다음은 반복의 조건을 설정한다. while left <= right:는 검색 범위의 시작 인덱스가 끝 인덱스보다 작거나 같을 때까지 반복한다는 의미이다. 
3. 먼저 중앙값을 계산하는데, 정수의 나눗셈에서는 소수점 이하를 버린다. 예를 들어 인덱스 6과 7의 중앙값은 6이 된다.
4. 만약 중앙값이 찾는 수와 동일하다면,
   
   
   • True를 반환한다.  
5. 만약 중앙값이 찾는 수보다 작다면,
   
   
   • 시작 인덱스를 중앙값보다 한 칸 오른쪽으로 초기화한다.
6. 만약 중앙값이 찾는 수보다 크다면,
   
   
   • 끝 인덱스를 중앙값보다 한 칸 왼쪽으로 초기화한다.
7. 반복이 끝나면 False를 반환한다.
   
   

느낀 점

---

 

시간복잡도의 개념에 대해서 자세하게 알아볼 수 있었다.