[탐색 알고리즘 #3] 코딩 테스트 연습문제 풀이

📌 탐색 알고리즘

- 이진 탐색
- 순차 탐색
- 코딩 테스트 연습문제 풀이 ✔

 

실전 코딩 테스트 - 탐색 알고리즘

---

[백준 1920번]

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

1920번: 수 찾기

• 시간복잡도 O(n^2)

n = 5
n_list = [4, 1, 5, 2, 3]
m = 5
m_list = [1, 3, 7, 9, 5]

for item in m_list:
    if item in n_list:
        print(1)
    else:
        print(0)

• 시간복잡도 O(logn) - 이진 탐색

n = 5
n_list = [4, 1, 5, 2, 3]
m = 5
m_list = [1, 3, 7, 9, 5]

n_list.sort()

def binary_search(value, start, end):
    if start > end:
        return False

    median = (start + end) // 2
    if n_list[median] > value:
        return binary_search(value, start, median - 1)
    elif n_list[median] < value:
        return binary_search(value, median + 1, end)
    else:
        return True

for item in m_list:
        if binary_search(item, 0, n - 1):
            print(1)
        else:
            print(0)

n = int(input())
n_list = list(map(int, input().split()))
m = int(input())
m_list = list(map(int, input().split()))

n_list.sort()

def binary_search(value, start, end):
    if start > end:
        return False

    median = (start + end) // 2
    if n_list[median] > value:
        return binary_search(value, start, median - 1)
    elif n_list[median] < value:
        return binary_search(value, median + 1, end)
    else:
        return True

for item in m_list:
        if binary_search(item, 0, n - 1):
            print(1)
        else:
            print(0)