본문 바로가기

Computer Science/Algorithms & Problem Solving

 (14)
최대 부분합과 쿼리 최대 부분합 문제를 $O(n)$에 푸는 것은 쉬운 일이다. 하지만, 배열을 업데이트 하는 질의가 주어진다면, 이는 쉬운 일이 아니다. 이와 관련한 문제가 근 몇 년간 여러 대회에 출제되었으며, 신기하게도 한국인들 사이에서는 유독 잘 알려져 있는 테크닉이다. 이 글에서는 다음 두 가지 쿼리를 $O(n \log n)$ 전처리 후 쿼리당 $O(\log n)$에 처리하는 방법을 제시한다. update(i, value) - 배열의 i번째 index의 값을 value로 업데이트한다 maxsum(left, right) - [left, right] 범위의 최대 부분합을 반환한다 기본적으로, 세그먼트 트리를 응용하여 문제를 해결한다. 세그먼트 트리의 노드를 다음과 같이 정의해주자. struct Node{ int left..
Patience Sort Patience sort는 다음과 같이 작동하는 정렬 알고리즘이다. (설명이 쉽지 않다. 더 아래에 있는 코드를 보는 것을 추천한다.) 작동 과정 $n$ 장의 카드 $C_1, C_2, \cdots, C_n$이 있고, 각 카드에 수가 적혀 있다고 할 때, 우리는 다음과 같은 과정을 수행하며, 각 카드를 차례로 카드 더미에 추가한다. (카드 더미를 스택이라 생각하면 좋다. 카드 더미들은 일렬로 나열되어 있다.) 초기에는 아무 카드 더미가 없다. 따라서, 처음에는 카드 1장으로 이루어진 카드 더미를 하나 만들고, 해당 더미에 $C_1$을 추가한다. 이후, $C_2$부터 차례로 카드 더미에 다음의 규칙을 따라 추가한다. 맨 위의 수가 자신보다 크거나 같은 카드 더미가 있다면, 그러한 카드 더미 중 가장 왼쪽의 ..
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] 카드 합체 놀이 보호되어 있는 글입니다.

티스토리툴바