[2022 동계] 6회차 개인 목표 및 결과

LONGNEW·2022년 2월 5일
0

모각코

목록 보기
12/19

목표 :

  • 인프런 - 운영체제 강의 수강
  • 트리, 구간 트리, 세그먼트 트리에 대한 알고리즘 풀이

결과 :

  • 세그먼트 트리
def init():
    elem_idx = int(pow(2, height - 1))
    for i in range(n):
        idx = elem_idx + i
        tree[idx] = data[i]

    for i in range(elem_idx - 1, 0, -1):
        tree[i] = min(tree[i * 2], tree[i * 2 + 1])

# s : search, t : target
def query(tree_idx, s_l, s_r, t_l, t_r):
    if tree_idx <= 0 or tree_idx >= length:
        return float("inf")
    if s_r < t_l or s_l > t_r:
        return float("inf")
    if t_l <= s_l and s_r <= t_r:
        return tree[tree_idx]

    mid = (s_l + s_r) // 2
    left = query(tree_idx * 2, s_l, mid, t_l, t_r)
    right = query(tree_idx * 2 + 1, mid + 1, s_l, t_l, t_r)

    return min(left, right)

0개의 댓글