[백준 2776번: 암기왕] 파이썬 풀이_이분탐색

2776번: 암기왕

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

 

---

풀이1:: 반복문 이용 코드

T = int(input()) # 테스트 케이스의 개수 

for _ in range(T):
  N = int(input()) # 수첩1 정수의 개수 
  N_list = set(map(int, input().split())) # 수첩1 정수 리스트 (*set으로 구현)
  M = int(input()) # 수첩2 정수의 개수
  M_list = list(map(int, input().split())) # 수첩2 정수 리스트

  for j in M_list: # 수첩2에 있는 정수를 하나씩 꺼내서 확인
    if j in N_list: # 수첩2에 있는 정수가 N_list에 있다면, 1을 출력
      print(1)
    else:
      print(0) # 아니면 0을 출력

 

풀이2:: 이분탐색 이용 코드

import sys

def binarySearch(arr, x):
    start = 0
    end = len(arr) - 1
    while True:
        if start > end:
            return -1
        index = (start + end) // 2
        if arr[index] < x:
            start = index + 1
        elif arr[index] > x:
            end = index - 1
        else:
            return index           

T = int(input()) # 테스트 케이스의 개수 

for i in range(T):
    N = int(sys.stdin.readline()) # 수첩1 정수의 개수 
    N_list = list(map(int, input().split())) # 수첩1 정수 리스트
    N_list.sort()
    M = int(sys.stdin.readline())  # 수첩2 정수의 개수
    M_list = list(map(int, input().split())) # 수첩2 정수 리스트

    for j in M_list:
        if binarySearch(N_list, j) >= 0:
            print(1)
        else:
            print(0)

---

💡 Challenge

잘못된 풀이 (list 이용)

T = int(input()) # 테스트 케이스의 개수 

for i in range(T):
  N = int(input()) # 수첩1 정수의 개수 
  N_list = list(map(int, input().split())) # 수첩1 정수 리스트
  M = int(input()) # 수첩2 정수의 개수
  M_list = list(map(int, input().split())) # 수첩2 정수 리스트

  for j in M_list: # 수첩2에 있는 정수를 하나씩 꺼내서 확인
    if j in N_list: # 수첩2에 있는 정수가 N_list에 있다면, 1을 출력
      print(1)
    else:
      print(0) # 아니면 0을 출력

 

리스트를 이용해 구현했는데 시간 초과가 뜸

 

시간 복잡도

• list, tuple Average: O(n)하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.
• set, dictionary Average: O(1), Worst: O(n)내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

 

셋이 리스트보다 시간복잡도 낮음 ->  N_list 부분을 리스트로 바꾸었더니 해결!

---

이분탐색이란?

이분 탐색(Binary Search)은 특정한 값을 찾는 탐색 알고리즘 중 하나로, 주로 정렬된 배열에서 사용된다. 배열 내에서 원하는 값을 효율적으로 찾는 방법으로, 각 단계마다 탐색 범위를 반으로 줄여가며 탐색하는 특징을 가지고 있다. 이로 인해 탐색 속도가 매우 빠르며, 탐색 범위가 큰 경우에도 빠른 검색이 가능하다.

 

이분 탐색의 동작 원리

1. 정렬된 배열에서 시작한다.
2. 배열의 중간 인덱스를 찾는다.
3. 중간 인덱스의 값을 확인하여 찾고자 하는 값과 비교합니다.

• 만약 중간 값이 찾고자 하는 값과 일치하면, 탐색을 종료하고 해당 인덱스를 반환한다.
• 중간 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반에서 탐색을 계속한다.
• 중간 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반에서 탐색을 계속한다.

4. 탐색 범위를 반으로 줄여가며 2단계로 돌아가 반복한다.

 

파이썬에서 이분탐색의 구현

(재귀함수 사용)

def binary_search_recursive(arr, target, low, high):
    if low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search_recursive(arr, target, mid + 1, high)
        else:
            return binary_search_recursive(arr, target, low, mid - 1)
    else:
        return -1

# 예시 사용
sorted_array = [2, 5, 7, 12, 16, 23, 32, 45, 50, 65]
target_value = 23

result = binary_search_recursive(sorted_array, target_value, 0, len(sorted_array) - 1)

if result != -1:
    print(f"타겟 값 {target_value}의 인덱스: {result}")
else:
    print("타겟 값이 배열에 존재하지 않습니다.")

(반복문 사용)

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 예시 사용
sorted_array = [2, 5, 7, 12, 16, 23, 32, 45, 50, 65]
target_value = 23

result = binary_search_iterative(sorted_array, target_value)

if result != -1:
    print(f"타겟 값 {target_value}의 인덱스: {result}")
else:
    print("타겟 값이 배열에 존재하지 않습니다.")

 

 

참고 링크

[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)

[Python] 리스트(list) 중복 제거 / 고유값

 

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)