99클럽 코테 스터디 _ 1일차 TIL (해시, 이분탐색)

 

< 문제 >

[백준] 2776. 암기왕 / 실버4

---

< 풀이 >

코드 변수 정의

• ynum : 연종이의 '수첩1'
• dnum : 동규의 '수첩2'

---

Hash
시간복잡도 : O(T * (N1 + N2))

def f():
    N1 = int(input())
    ynum = set(map(int, input().split())) # 집합 변환 -> 해시 기반 탐색
    N2 = int(input())
    dnum = list(map(int, input().split()))
    for num in dnum:
        print(1 if num in ynum else 0)

def solution():
    T = int(input())
    for _ in range(T):
        f()

solution()

• 해시 기반 탐색을 하기 위해 ynum을 집합으로 변환한다.
• dnum에 있는 숫자들이 ynum에 있는지 확인한 후, 있으면 1 없으면 0을 출력한다.

 

Binary Search
시간복잡도 : O(T*(N1logN1+N2logN1))

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False # ynum에 들어있지 않음

def f():
    N1 = int(input())
    ynum = sorted(map(int, input().split())) # 이진탐색 전 정렬 필요
    N2 = int(input())
    dnum = list(map(int, input().split()))
    for num in dnum:
        print(1 if binary_search(ynum, num) else 0)

def solution():
    T = int(input())
    for _ in range(T):
        f()

solution()

• 이진 탐색 전 ynum을 오름차순 정렬한다.
• dnum에 있는 숫자들을 binary_search 함수로 ynum에 있는지 확인한다.

---

< 회고 >

1. 시간초과 문제
   • ynum을 list로 받아오니 시간초과 문제가 발생했다.
   • (해결)
     • ynum을 set로 받아와서 Hash로 풀이하니 시간초과 해결 👍🏻
       
       
2. Binary Search
   • 검색 간격을 반으로 반복적으로 나누어 정렬된 배열로 사용하는 알고리즘.
   • (작동 방식)
     • 배열의 중간 요소를 Target과 비교한다.
       • Target을 찾으면 프로세스 종료
     • Target을 찾지 못한 경우 다음 탐색 공간을 배열의 절반 선택한다.
       • Target이 Mid 요소보다 작으면 → Mid를 기준으로 왼쪽 사용
       • Target이 Mid 요소보다 크면    → Mid를 기준으로 오른쪽 사용