실버4

문제 1920

해당 문제 링크

정답

이분탐색

시간 복잡도 O(log n)

def binary(arr, value):
    left = 0
    right = len(arr)-1

    while(left <= right):
        mid = (left+right) //2
        if arr[mid] == value:
            return 1
        elif  arr[mid] > value:
            right=mid-1
        else :
            left=mid+1
    return 0

n= int(input())
a=list(map(int,input().split(' ')))
a.sort()
m= int(input())
b=list(map(int,input().split(' ')))

for i in range(m):
    print(binary(a, b[i]))

퀵정렬

: 대표적인 '분할 정복' 알고리즘
: 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다.
: 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.
: 평균 속도 = 시간복잡도 O(n*logn)

#퀵정렬
n=int(input())
a=set(map(int, input().split())) #탐색 시간을 줄이기 위해 set으로 받음
m=int(input())
b=list(map(int, input().split()))

for i in b:
    if i in a:
        print(1)
    else :
        print(0)
        
    # print(1) if num in A else print(0)

파이썬 'in' 연산자 시간 복잡도(Time Complexity) = Set

시간 복잡도 평균 : O(1) 최악 O(n)
내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생한다.
참고 사이트

풀이

시행착오 - 단순 구현 => 시간 초과

시간 복잡도 O(n)

n= int(input())
a=list(map(int,input().split(' ')))
    
m= int(input())
b=list(map(int,input().split(' ')))

for i in range(m):
    if b[i] in a:
        print(1)
    else:
        print(0)

파이썬 'in' 연산자 시간 복잡도(Time Complexity) = List

시간 복잡도 O(n)
하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 된다
참고 사이트