[백준 / python] 1920번 수 찾기

오늘은 이분 탐색 유형인 백준 1920번 문제, 수 찾기를 풀어보겠습니다!

 

< 문제 확인 >

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

 

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

이 문제는 두 번째 줄에 입력한 배열A의 숫자를 기반으로 마지막 줄에 입력한 숫자들이

포함되는지의 여부를 파악하는 문제입니다.

 

해당 숫자가 있는지 없는지를 파악하기위한 여러 가지 방법이 있지만

그중 이분 탐색을 통해 배열A를 탐색해 보도록 하겠습니다!

 

✔️ 이분 탐색이란?

검색 범위를 줄여나가며 특정 데이터를 검색하는 방식으로, 정렬된 정수의 리스트를 같은 크기의

두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다.

 

리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지

판단하여 맨 앞부터 검색하거나 중간부터 검색하여 범위를 줄여나가는 것입니다.

 

✔️ 가능한 시간복잡도

N개의 정수 배열을 정렬하는 데 O(logN), M개의 숫자 각각 이분 탐색을 적용하는데

O(log M)의 시간이 소요되므로, 전체 시간복잡도는 (Nlog N + Mlog N)입니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 자연수 N과 배열 A를 입력받고 정렬합니다.

2. 이어서 자연수 M을 입력받고 해당 숫자만큼 정수를 입력받습니다.

3. 각 원소에 대해 배열A에서 이분 탐색을 수행하여 존재 여부에 따라 1 또는 0을 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

에러 발생 원인은 이분 탐색 함수 binary_search를 호출할 때, end 값을 잘못 설정했기 때문입니다.

N은 배열의 길이이므로 까지 실행할 경우, 배열의 인덱스를 초과하게 되어 IndexError가 발생합니다.

# 배열A에 속하는지 확인 후 결과 출력
for target in M_list:
    if binary_search(A, target, 0, N): # end 값을 잘못 입력함
        print(1)
    else:
        print(0)

---

📌 정답 코드

N = int(input())
A = list(map(int, input().split()))
A.sort()  # 배열A 정렬

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

# 이분탐색 알고리즘
def binary_search(arr, target, start, end):
    while (start <= end):
        mid = (start + end) // 2
        if (arr[mid] == target): return True
        elif (arr[mid] < target): start = mid + 1
        else: end = mid - 1
    return False

# 배열A에 속하는지 확인 후 결과 출력
for target in M_list:
    if binary_search(A, target, 0, N-1):
        print(1)
    else:
        print(0)

오늘은 이분 탐색 알고리즘을 사용한 문제를 풀어보았습니다!

가장 대표적인 유형을 해결해 보았는데 더 응용할 수 있는 문제도 풀어볼 예정입니다 ^_^

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no