[코딩테스트] 7주차: 고급 자료구조

고급 자료구조

학습 주제

• 세그먼트 트리
• 펜윅 트리 (Fenwick Tree)
• 우선순위 큐와 힙

학습 목표

• 세그먼트 트리와 펜윅 트리의 개념을 이해하고, 다양한 쿼리 문제에 적용할 수 있다.
• 우선순위 큐와 힙을 사용하여 효율적으로 데이터 구조를 관리하고, 관련 문제를 해결할 수 있다.

학습 자료

• 세그먼트 트리의 개념 및 구현 방법
• 펜윅 트리의 개념 및 구현 방법
• 우선순위 큐와 힙의 개념 및 활용

실습 문제

1. 세그먼트 트리를 사용한 범위 쿼리 문제

• 주어진 배열에 대해 세그먼트 트리를 사용하여 범위 합 쿼리를 처리하는 함수를 작성하세요.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        index += self.n
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def range_query(self, left, right):
        left += self.n
        right += self.n
        sum = 0
        while left < right:
            if left % 2 == 1:
                sum += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                sum += self.tree[right]
            left //= 2
            right //= 2
        return sum

# Test
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
print("Range Query (1, 5):", seg_tree.range_query(1, 5))  # 24
seg_tree.update(1, 10)
print("Range Query (1, 5):", seg_tree.range_query(1, 5))  # 31

 

2. 펜윅 트리를 사용한 빠른 업데이트와 쿼리 문제

• 주어진 배열에 대해 펜윅 트리를 사용하여 범위 합 쿼리를 처리하는 함수를 작성하세요.

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        sum = 0
        while index > 0:
            sum += self.tree[index]
            index -= index & -index
        return sum

    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)

# Test
data = [1, 3, 5, 7, 9, 11]
fenwick_tree = FenwickTree(len(data))
for i, val in enumerate(data):
    fenwick_tree.update(i + 1, val)
print("Range Query (1, 5):", fenwick_tree.range_query(2, 5))  # 24
fenwick_tree.update(2, 7)  # Update index 2 with 7
print("Range Query (1, 5):", fenwick_tree.range_query(2, 5))  # 31

 

3. 힙을 이용한 우선순위 큐 문제

• 주어진 작업들에 대해 우선순위 큐를 사용하여 작업을 처리하는 함수를 작성하세요.

import heapq

def process_tasks(tasks):
    pq = []
    for task in tasks:
        heapq.heappush(pq, task)
    
    while pq:
        task = heapq.heappop(pq)
        print("Processing task:", task)

# Test
tasks = [(2, "low priority task"), (1, "high priority task"), (3, "medium priority task")]
process_tasks(tasks)
# Output:
# Processing task: (1, 'high priority task')
# Processing task: (2, 'low priority task')
# Processing task: (3, 'medium priority task')​

추가 학습 자료:

• Segment Tree - GeeksforGeeks
• Fenwick Tree - GeeksforGeeks
• Heap Data Structure - GeeksforGeeks

---

추천 문제

백준 (Baekjoon)

1. 문제명: 구간 합 구하기
   • 설명: 주어진 수열에서 특정 구간의 합을 구하고, 수열의 값도 수정할 수 있는 문제입니다. 세그먼트 트리를 활용합니다.
   • 문제 유형: 세그먼트 트리
   • 난이도: 골드 I
   • 주소: 구간 합 구하기
2. 문제명: 수들의 합 5
   • 설명: 주어진 수열에서 특정 구간의 합이 주어진 값이 되는 경우의 수를 구하는 문제입니다.
   • 문제 유형: 펜윅 트리 (Fenwick Tree)
   • 난이도: 골드 III
   • 주소: 수들의 합 5
3. 문제명: 최소 힙
   • 설명: 주어진 명령에 따라 최소 힙을 구현하여 데이터를 삽입하고 삭제하는 문제입니다.
   • 문제 유형: 힙, 우선순위 큐
   • 난이도: 실버 II
   • 주소: 최소 힙

프로그래머스 (Programmers)

1. 문제명: 징검다리 건너기
   • 설명: 주어진 징검다리에서 건널 수 있는 사람의 최대 수를 구하는 문제입니다. 이분 탐색과 세그먼트 트리를 활용할 수 있습니다.
   • 문제 유형: 세그먼트 트리
   • 난이도: 레벨 3
   • 주소: 징검다리 건너기
2. 문제명: 순위 검색
   • 설명: 주어진 조건에 맞는 순위를 검색하는 문제로, 효율적인 쿼리 처리가 요구됩니다. 펜윅 트리를 활용할 수 있습니다.
   • 문제 유형: 펜윅 트리 (Fenwick Tree)
   • 난이도: 레벨 2
   • 주소: 순위 검색
3. 문제명: 이중우선순위큐
   • 설명: 주어진 명령에 따라 최대 힙과 최소 힙을 동시에 구현하여 데이터를 삽입하고 삭제하는 문제입니다.
   • 문제 유형: 힙, 우선순위 큐
   • 난이도: 레벨 3
   • 주소: 이중우선순위큐