99클럽 코테 스터디 13일차 TIL + 이분 탐색 그리고 정렬을 곁들인..

[오늘의 학습 키워드 및 문제]
- 백준의 "숫자 카드" 문제를 풀었다.
- 오늘 주제는 "이분 탐색"이다.
- 근데 오늘 문제는 세 가지 방법으로 풀어봤다. 더 있을지 모르겠는데 암튼 세 개다.

[나의 코드]

# 첫 번째 풀이

n = int(input())
given = set(list(map(int, input().split())))
m = int(input())
holded = list(map(int, input().split()))

for num in holded:
    if num in given:
        print(1, end=" ")
    else:
        print(0, end=" ")

다음 코드는 집합(Set)을 이용하여 푼 풀이다.
아마 이 코드가 가장 직관적이고 바로 떠올릴 수 있는 코드일 것이다.

근데 시간 초과가 날 것이다.
왜냐하면 holded와 given 둘 다 최대 500,000개인데, 탐색도 곱하기 두 번 해야 하니 제한 시간 안에 실행되기 어렵다.

여기서 집합(Set)을 쓰면 된다. 집합은 평균적으로 O(1) 시간 복잡도로 원소의 존재 여부를 확인할 수 있다고 한다.
배열을 집합으로 변환하는 과정은 O(n)이다.

집합을 활용한 풀이법이 가장 빨랐다. 참고로 시간 복잡도는 O(n + m)이다.

# 두 번째 풀이

n = int(input())
given = list(map(int, input().split()))
m = int(input())
holded = list(map(int, input().split()))

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if target == given[mid]:
            return 1
        elif target > given[mid]:
            start = mid + 1
        elif target < given[mid]:
            end = mid - 1
    return 0

given.sort()    
for num in holded:
    print(binary_search(num, given), end=' ')

이 풀이는 이분 탐색을 이용하여 푼 풀이다. (오늘의 주제!)
예전에 시험본다고 이분 탐색 코드를 손으로 그려가며 외운 덕에 코드는 금방 짰다.

이분 탐색은 탐색 원소의 개수를 반으로 줄이니까 O(log N) 만큼 걸린다.
근데 이분 탐색에서 가장 중요한 점은 배열이 미리 정렬이 돼있어야 한다는 것이다.

그리고 이분 탐색 풀이법의 실행 시간이 가장 느렸다. (그래 보인다.)

# 세 번째 풀이

n = int(input())
given = list(map(int, input().split()))
m = int(input())
holded = list(map(int, input().split()))

answer = {}

for i in holded:
    answer[i] = 0

print(answer)

for num in given:
    if num in answer:
        answer[num] = 1

for result in answer.values():
    print(result, end=' ')

마지막으로 해시(딕셔너리)를 이용한 풀이다.
이 풀이는 얼핏 보면 첫 번째 풀이법이랑 비슷해 보일 것이다. 코드가 절대 어렵지 않다는 소리다.

딕셔너리도 집합과 마찬가지로 탐색 속도가 O(1) 이다. (List 만 엄청 느리다. O(N))
그래서 저런 식으로 코드를 짜도 시간 초과가 일어나지 않는다.

내가 왜 이 풀이법으로 풀었냐 하면 '알고리즘 분류'에 해시로도 풀 수 있다고 나와 있어서다.
^^;;;

참고로 시간 복잡도는 O(n + m)이다. 집합 풀이법보다 조금 더 걸렸다. 근데 비슷할 거다.

[오늘의 회고]
- 이분 탐색을 한 달만에 기억 속에서 끄집어 봤는데, 다시 상기할 수 있어서 좋은 시간이었다.
- 집합과 해시의 탐색 속도에 대해서 알 수 있게 되었다. 역시 많이 알 수록 풀이가 다양해지는 것 같다.
- 시간 복잡도 계산하는 연습을 좀 더 할 필요가 있어 보인다. 끝!