파이썬 Python | 알고리즘 | 백준 수 찾기

⭕ 파이썬 Python | 알고리즘 | 백준 수 찾기

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 리스트에서 특정 값이 존재하는지 확인해야 한다.
• 처음 문제를 접했을 때 가장 먼저 생각한 방법은 리스트를 순차적으로 탐색하며 값을 확인하는 선형 탐색(Linear Search) 방법이었다. 리스트의 각 요소를 하나씩 확인하여 찾고자 하는 값이 있는지 판단하는 방식으로, 구현이 매우 간단하다. 그러나, 입력 크기 N과 M이 최대 100,000까지 주어지므로 선형 탐색의 시간 복잡도 O(M*N)은 매우 비효율적이라는 생각이 들었다. N=100,000, M=100,000이라면, 총 10억 번의 비교 연산이 필요하게 된다. 따라서, 시간제한 1초를 초과하게 된다.
• 다음으로 떠올린 방법은 이분 탐색(Binary Search)이다. 이분 탐색은 정렬된 리스트에서 탐색 범위를 절반으로 줄여가며 원하는 값을 찾는 방법이다. 시간 복잡도는 O(M logN)으로, 각 쿼리에 대해 더 빠르게 값을 찾을 수 있다. 다만, 이분 탐색을 사용하기 위해서는 먼저 리스트를 정렬해야 하므로 O(N logN)의 추가 작업이 필요하다. 

 

 

➡️ 코드 설계하기

1. 리스트 A의 크기 N, 리스트 A의 요소들, 쿼리의 개수 M, 쿼리의 리스트를 입력하고 저장한다.
2. 이분 탐색을 수행하기 위해 리스트 A를 오름차순으로 정렬한다.
3. 이분 탐색 구현: 리스트의 중간 값을 선택하고, 찾고자 하는 값과 동일한지 확인한다. 만약 중간 값이 찾고자 하는 값보다 크다면, 리스트의 왼쪽 절반으로 검색 범위를 좁힌다. 만약 중간 값이 찾고자 하는 값보다 작다면, 리스트의 오른쪽 절반으로 검색 범위를 좁힌다. 이 과정을 반복하여 값을 찾는다. 찾으면 1을, 찾지 못하면 0을 출력한다.

 

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차 

• 시간 초과
• 처음에는 가장 직관적인 방법인 선형 탐색을 선택하였다. 리스트 A에서 각 쿼리 값을 하나씩 확인하면서 존재 여부를 판단할 수 있었다. 선형 탐색은 시간 복잡도가 O(M*N)으로, 주어진 입력 크기에서 시간 초과가 발생할 수밖에 없었다.

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

for query in queries:
    if query in A:  
        print(1)
    else:
        print(0)

---

2회 차

• 시간 168ms
• Set은 리스트보다 빠르게 값을 찾을 수 있으므로, 시간 복잡도를 O(M)으로 줄일 수 있었다. 이분 탐색보다 빠른 성능을 보였다.

import sys

N = int(sys.stdin.readline())
A = set(map(int, sys.stdin.readline().split()))  # 리스트를 집합으로 변경
M = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

for query in queries:
    if query in A:  
        print(1)
    else:
        print(0)

 

---

3회 차

• 시간 188ms
• 리스트를 정렬하는 데는 O(NlogN)이 필요하지만, 이후 각 쿼리에 대해 O(logN)의 시간 복잡도로 탐색할 수 있어 최종 시간 복잡도가 O(MlogN)으로 선형 탐색에 비해 크게 줄었다.
• 시간은 이분탐색보다 Set을 사용하는 것이 더 효율적이지만, 정렬된 리스트에서 특정 값의 위치를 찾는 문제에서는 더욱 이분탐색이 유용할 것이다!

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

# A 배열 정렬
A.sort()

#이분 탐색
for query in queries:
    left, right = 0, len(A) - 1
    found = False
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == query:
            found = True
            break
        elif A[mid] < query:
            left = mid + 1
        else:
            right = mid - 1

    if found:
        print(1)
    else:
        print(0)

---

4회 차

• 시간 216ms
• 이분 탐색을 직접 구현하는 대신, bisect 라이브러리를 사용하여 코드의 간결하게 하고자 했다. bisect 라이브러리를 사용한 이분 탐색은 시간 복잡도가 O(logN)으로 동일하지만, 실제 실행 시간은 직접 구현한 이분 탐색보다 조금 더 소요되었다. 라이브러리 함수 호출에 따른 시간으로 생각된다.

import sys
import bisect

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

# A 리스트 정렬
A.sort()

# 이분 탐색
for query in queries:
    idx = bisect.bisect_left(A, query)
    if idx < len(A) and A[idx] == query:
        print(1)
    else:
        print(0)

 

 

➡️ 정답 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

# A 배열 정렬
A.sort()

#이분 탐색
for query in queries:
    left, right = 0, len(A) - 1
    found = False
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == query:
            found = True
            break
        elif A[mid] < query:
            left = mid + 1
        else:
            right = mid - 1

    if found:
        print(1)
    else:
        print(0)