본문 바로가기

Computer Science/Algorithms & Problem Solving

(3)
최대 부분합과 쿼리 최대 부분합 문제를 $O(n)$에 푸는 것은 쉬운 일이다. 하지만, 배열을 업데이트 하는 질의가 주어진다면, 이는 쉬운 일이 아니다. 이와 관련한 문제가 근 몇 년간 여러 대회에 출제되었으며, 신기하게도 한국인들 사이에서는 유독 잘 알려져 있는 테크닉이다. 이 글에서는 다음 두 가지 쿼리를 $O(n \log n)$ 전처리 후 쿼리당 $O(\log n)$에 처리하는 방법을 제시한다. update(i, value) - 배열의 i번째 index의 값을 value로 업데이트한다 maxsum(left, right) - [left, right] 범위의 최대 부분합을 반환한다 기본적으로, 세그먼트 트리를 응용하여 문제를 해결한다. 세그먼트 트리의 노드를 다음과 같이 정의해주자. struct Node{ int left..
Kruskal's Algorithm과 MST의 성질 어떤 가중치 있는 (연결) 그래프 $G = (V, E, w)$가 있을 때, 트리 $T$가 $G$의 스패닝 트리 임은 $T$가 $G$의 부분 그래프이고, $V(T) = G(T)$(정점 집합이 같음)으로 정의된다. 최소 스패닝 트리(Minimum Spanning Tree, MST)는 스패닝 트리 가운데 모든 간선의 가중치의 합($\sum_{e \in E(T)} w(e)$)이 최소인 것을 의미한다. (최소 스패닝 트리는 여러개가 있을 수도 있다.) 예를 들어, 7개의 정점으로 이루어진 그래프 $G$가 있다고 하자. 이 때, 이 그래프의 MST는 다음과 같다: MST는 다음과 같은 알고리즘을 통해 $O(E \log E)$ 시간에 구할 수 있으며, 이는 Kruskal 알고리즘이라 불린다. 편의상 모든 간선의 가중..
[UCPC 2018 예선 B] 카드 합체 놀이 보호되어 있는 글입니다.