[Python] 알고리즘 개념15 퀴즈 - 세그먼트 트리

 

 

📌 퀴즈 개요

다음 퀴즈를 통해 세그먼트 트리(Segment Tree) 개념을 정확히 이해하고 있는지 확인해 보세요! 😊

---

 

 

🧩 1. 개념 이해 문제

 

(1) 세그먼트 트리의 특징으로 옳지 않은 것은?

1. 세그먼트 트리는 배열의 특정 구간 정보를 빠르게 처리하는 자료구조이다.
2. 세그먼트 트리는 이진 트리 기반으로 동작한다.
3. 세그먼트 트리의 업데이트 연산의 시간복잡도는 O(n)이다.
4. 세그먼트 트리는 RMQ(Range Minimum Query) 문제 해결에 유용하다.

 

(2) 세그먼트 트리의 동작 방식에 대한 설명으로 옳지 않은 것은?

1. 세그먼트 트리는 트리를 미리 구성한 후 구간 쿼리를 O(log n) 시간에 처리할 수 있다.
2. 세그먼트 트리는 루트 노드가 전체 배열의 정보를 저장하고, 리프 노드가 개별 원소를 저장한다.
3. 특정 원소 값을 변경하는 경우, 해당 리프 노드만 수정하면 된다.
4. 세그먼트 트리의 크기는 일반적으로 입력 배열의 4배 크기로 설정된다.

---

 

 

🧩 2. 실전 문제

 

(3) 다음 배열을 세그먼트 트리로 구축하고, 구간 합 쿼리(2~4)를 수행한 결과는?

배열: [1, 3, 5, 7, 9, 11]

1. 21
2. 24
3. 22
4. 20

 

(4) 다음 코드의 실행 결과는?

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2 * node + 1, start, mid)
            self.build(arr, 2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.tree[0])

1. 31
2. 36
3. 30
4. 34

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

(1) 정답: 3
✅ 세그먼트 트리의 업데이트 연산은 O(log n)으로 수행됩니다.

(2) 정답: 3
✅ 특정 원소 값을 변경하면 리프 노드뿐만 아니라 부모 노드도 갱신해야 합니다.

(3) 정답: 3
✅ 배열 [1, 3, 5, 7, 9, 11]에서 2~4의 합은 5 + 7 + 9 = 22입니다.

(4) 정답: 2
✅ 세그먼트 트리의 루트 노드에는 배열 전체 합이 저장되므로 1 + 3 + 5 + 7 + 9 + 11 = 36이 출력됩니다.

---