Notion에서 작성된 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] Search in a Binary Search Tree

[Search in a Binary Search Tree]

Solution 1. Recursion $O(\text{detph})$

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        if val < root.val:
            return self.searchBST(root.left, val)
        elif val > root.val:
            return self.searchBST(root.right, val)
            
        return root

• 재귀를 이용한 풀이이다. BST의 정의에 따라, 해당 노드의 val이 찾으려는 val보다 작다면 왼쪽 트리에서 다시 찾고, 찾으려는 val보다 크다면 오른쪽 트리에서 다시 찾고, val과 같다면(찾았다면) 반환한다.
• BST가 “Balanced” BST일 경우 값을 찾는 데에 걸리는 시간은 $O(\lg n)$이지만, 트리가 한 쪽으로 치우친 경우, 극단적으로 [1, 2, 3, 4, 5]와 같은 경우는 값을 찾는 데 $O(n)$ (depth만큼) 이 소요된다.

Solution 1-2. Recursion $O(\text{detph})$

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        
        return self.searchBST(root.left if val<root.val else root.right, val)

• root가 None일 때 None을 반환한다는 점과, root.val이 val과 같을 때 root를 반환한다는 점을 고려하여, Short Circuit Rule을 생각해 주면 위와 같이 축약할 수 있다.

Solution 2. loop $O(\text{depth})$

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root and root.val != val:
            root = root.left if val<root.val else root.right

        return root

• 전체적인 흐름은 같다. root가 존재하며 그 root.val이 찾고자 하는 val이 아닐 때 계속해서 트리의 왼쪽 또는 오른쪽으로 움직여가며 값 찾기를 시도한다.

---

[Middler] 숫자 카드

[숫자 카드]

Solution 1. Hash $O(n+m)$

input()
cards = {*input().split()}
input()

for s in input().split():
    print(int(s in cards), end=' ')

• 해시를 이용한 풀이이다. 가지고 있는 숫자 카드의 집합을 만들어 놓으면, 가지고 있는 카드인지 아닌지를 매번 Amortized $O(1)$에 판별할 수 있게 된다.

Solution 2. Binary Search $O(n \lg n + m \lg n)$

n = int(input())
cards = sorted(map(int, input().split()))
input()

def bs(s):
    l, r = 0, n-1
    while l<=r:
        m = (l+r)//2
        if s == cards[m]: return 1
        if s < cards[m]:
            r = m-1
        else:
            l = m+1
    return 0

for s in map(int, input().split()):
    print(bs(s), end=' ')

• 오늘의 키워드가 이분 탐색이니까,,,!! 이분 탐색으로도 풀어봤다.
• 가지고 있는 카드에 대해, 이분 탐색으로 소유 여부를 확인할 수 있도록 정렬한다.
• 그 후 이분 탐색을 진행한다. 찾으려는 카드가 갖고 있는 카드라면 1을 반환하고, 이분 탐색을 마칠 때까지 카드를 찾지 못하면 0을 반환한다. 이분 탐색을 이용하여 매 쿼리마다 $O(\lg n)$에 처리할 수 있게 된다.

---

[Challenger] 입국 심사

[입국 심사]

[BOJ 3079. 입국심사] 와 같은 문제이다.

Solution. Binary Search + Parametric Search $O(n \cdot \lceil\lg10^{18}\rceil) = O(60n)$

def solution(n, times):
    def check(n, m):
        for t in times:
            n -= m//t
            if n<=0: return True
        return False

    l, r = 1, max(times)*n
    while l<=r:
        m = (l+r)//2
        if check(n, m):
            r = m-1
        else:
            l = m+1
            
    return l

• “이분 탐색” 이라는 키워드를 보지 않고 풀 수 있었을까? 하고 뒤돌아 보니 못 풀었을 것 같다. 전에 두세문제 정도 Parametric Search 문제들을 풀어본 경험을 통해 억지로 “결정 문제로 변환”하려고 노력해서 풀었다.
  • 관련 문제들을 더 풀어보면서 어느 상황에서 Parametric Search를 떠올릴 수 있는지 발상적인 부분을 훈련해야겠다.

결정 문제로 변환

• 이분 탐색을 통해 어떤 시간(m)을 정하고, 이 시간 내에 “입국심사를 모두 마칠 수 있는지” 의 결정 문제로 변환했다.
• 입국심사를 모두 마칠 수 있는지를 어떻게 판단할 수 있을까?
  • 각 심사관별로 정해진 시간(m) 내에 몇 명까지 심사를 할 수 있는지 계산하여 합친 값이 입국심사를 기다리는 사람의 수 $n$ 이상이라면 해당 시간 내에 입국심사를 마칠 수 있는 것이다.
  • 이를 조금 더 최적화하면, 입국심사를 기다리는 사람의 수 $n$에서 심사관마다 정해진 시간(m) 내에 몇 명까지 심사를 할 수 있는지 계산하여, 심사한 인원들을 빼줌으로써 $n$을 갱신해 주다가, $n$이 $0$ 이하가 된다는 것은 더이상 입국심사를 기다리는 사람이 없다는 것이므로 바로 True를 return하여 조기종료해준다.
    • 그렇다면 “일 잘하는 사람(…) (입국심사에 소요되는 시간이 짧은 심사관)” 부터 입국심사를 시키면 조기종료가 앞당겨지지 않을까? → 당연히 그렇지만 sort해주는 데에 $O(n \lg n)$ 시간이 소요되므로, $O(n)$으로 순회하며 $n$을 갱신해주는 것보다 느려진다.

이분 탐색 적용

• 이분 탐색할 범위를 설정하기 위해 제한사항을 살펴보면,
  • 입국심사를 기다리는 사람은 1명 이상, 심사관도 1명 이상, 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상이므로, 어떤 상황에서 아무리 빨라도 1분은 소요된다는 것을 알 수 있다.
  • 입국심사를 기다리는 사람은 10억명 이하, 각 심사관이 한 명을 심사하는데 걸리는 시간은 10억분 이하, 심사관은 1명 이상이므로, 최악의 경우 심사관이 단 한 명 존재하는데 그 심사관이 한 명을 심사하는데 걸리는 시간이 10억분이며 입국심사를 10억명이 기다리고 있는 상황(🐶판)이다.
    • 이 때 모두를 심사하기 위해서는 10억명 * 10억분 = $10^{18}$분이 소요되기 때문에 아무리 오래 걸려도 $10^{18}$분이 소요된다는 것을 알 수 있다.
    • 정말 놀랍게도… $\lceil\log_2 {10^{18}}\rceil=60$이므로 60번 안에 입국심사를 모두 마칠 수 있는 최소의 시간을 구할 수 있다.
    • 이 상한을 $10^{18}$이 아닌 max(times)*n 으로 설정해주면 범위를 탐색 초기부터 타이트하게 잡게 되어 이분 탐색의 횟수를 줄여주기 때문에(매 탐색마다 $O(n)$으로 check() 를 수행하기 때문에 탐색의 횟수를 줄이는 것이 실행 시간 면에서 유의미함) $\lceil \log_2{\{\max(\text{times})\cdot n}\}\rceil <59$인 경우 더 빠르다. (times의 최댓값을 구하는 데 $O(n)$이 소요되므로)
• 조건을 만족하는 최솟값을 구하기 위해 Lower Bound를 이용했다.

---

Memo

Challenger.

• 심사하는 데 소요되는 시간이 같은 심사관이 많을수록 Counter 또는 defaultdict를 이용하여 파라미터 계산을 더 최적화할 수 있다.
  • 이를 통해 특정 테스트케이스에서 더 빠르게 동작시킬 수 있으나, 일반적인 테스트케이스에서는 Counter 객체 자체를 만드는 데에 추가로 시간이 소요되고, 곱셈 연산까지 추가로 하게 되므로 unique한 소요시간이 많을수록 오히려 기존 방식보다 느려지는 경향을 보인다.