탐색 알고리즘 (백준 1920번)

무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세 가지 알고리즘이 있다.
 

선형 탐색(linear searching)

복잡도 : O(N)
선형 탐색은 N개의 수를 하나씩 차례대로 x인지 비교하는 방법이다. 이는 가장 간단한 알고리즘이지만 N이 커질 때 복잡도가 크게 늘어난다. 파이썬의 in 연산자가 선형 탐색을 이용한다.

이진 탐색(binary searching)

복잡도 : O(logN)
정렬된 리스트에서 사용 가능한 알고리즘으로, 아래의 순서로 진행된다.

1. 리스트의 중간 인덱스를 잡고, 해당 인덱스의 값을 x와 비교하여 같으면 종료한다.
2. 다르다면, 크기를 비교하여 절반의 데이터를 날려 버린다.
3. 크기가 절반으로 줄어든 데이터에서 1~2의 과정을 다시 수행한다.

해시 탐색(Hash searching)

복잡도: O(N) -> O(1)
리스트를 인덱스와 묶어, set나 dictionary 같은 해시 구조에 저장해놓고 불러오는 탐색 방법이다. 이 방법은 해싱 자체는 O(N)의 복잡도가 들어가지만, 탐색은 O(1)의 복잡도로 아주 빠르게 수행할 수 있다.
 

백준 1920번: 수 찾기

 
백준 1920번은 전형적인 탐색 알고리즘 문제이다. 뭔가 단순한 선형 검색을 사용하면 시간 초과가 날 것 같은 냄새가 났다.

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

 
또한 이진 검색을 이용 가능하도록 배열이 정렬되어 있지도 않았다. list.sort()의 시간 복잡도를 찾아보니, 최선의 경우 O(N), 최악의 경우 O(NlogN)까지 나온다고 한다. sort한 뒤 이진 탐색을 사용하는 것도 좋은 전략은 아닌 것 같다. python에는 이진 탐색 알고리즘을 쓰는 bisect라는 모듈이 존재하긴 하지만, N개의 데이터를 sort한 후 M개에 대해 이진 탐색을 하나씩 하면 시간이 너무 오래 걸릴 것 같았다.
 
그래서 set 자료형을 이용하기로 했다. 정수열 A를 받아서 바로 set로 만든다면 자동 정렬, 중복값 삭제가 이루어진다. 또한, list와 달리 set은 각 원소에 해시값이 있어, 해시 탐색으로 O(1)만에 검색이 가능하다!!

import sys

N = int(sys.stdin.readline())
A = set(map(int, sys.stdin.readline().strip().split()))
M = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().strip().split()))

for i in nums:
    print(int(i in A))

 
이전 문제와 마찬가지로, 시간을 조금이라도 아껴보고자 input() 대신에 표준 모듈 sys에서 sys.stdin.readline()을 사용하였다.