[알고리즘] 탐색 알고리즘 관련 코딩

문제

백준 1920번을 풀어보자.

풀이

시간 복잡도를 고려하지 않은 풀이

아래 풀이는 단순해보이지만, 시간 복잡도는 $O(n^2)$ 이다.

N = int(input())
nList = list(map(int, input().split()))
M = int(input())
mList = list(map(int, input().split()))

for x in mList:
    if x in nList:
        print(1)
    else:
        print(0)

시간 복잡도를 고려한 풀이

이진 탐색으로 수를 찾는다면, $O(log(n))$ 까지 시간 복잡도를 낮출 수 있다.

# 시간 복잡도를 낮추는 방법 -> 이진 탐색 알고리즘
N = int(input())
nList = list(map(int, input().split()))
M = int(input())
mList = list(map(int, input().split()))

nList.sort() # 이진 탐색을 하기 위해서는 정렬이 되어있어야 한다!

def binarySearch(find, start, end):
#     print(find, start, end) # 각각의 반복에서 start 와 end 가 어떻게 변하는지 확인해보기
    if start > end:
        return False
    
    mid = (start + end) // 2
    if nList[mid] > find:
        return binarySearch(find, start, mid-1)
    elif nList[mid] < find:
        return binarySearch(find, mid+1, end)
    else:
        return True

for x in mList:
    if binarySearch(x, 0, N-1):
        print(1)
    else:
        print(0)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기