Computer Science32 Segment Tree Segment Tree 구간 트리는 자료를 이진트리의 형태로 조직화한 트리로서 동적인 구간 질의에 효율적으로 답하기 위한 자료구조이다. 여기서 동적이라는 말은 자료를 갱신해 가면서 질의에 답할 수 있어야 한다는 뜻이다. 구간질의란 데이터가 저장된 자료구조(여기서는 선형적 예를 들어 배열을 다룰 것이다.)에서 임의의 구간이 주어 졌을때 그 구간에 대한 질의를 뜻한다. 예를 들어 구간 최소질의(RMQ, Range Minimum Query)가 이해 해당된다. RMQ는 해당되는 칸의 최솟값의 인덱스를 구하는 문제이다. 다시말해 구간트리를 이용하여 이같은 문제를 효율적으로 해결할 수 있다는 것이다. 구간트리는 이진 트리의 형태로서 모든 노드의 자식은 둘 이하이다. 구간 트리는 각 노드가 해당되는 구간에대한 질의의.. 2018. 1. 18. Union Find Disjoint Set (UFDS) 유니온 파인드 상호배타적 집합 상호 베타적인 집합들을 모델랑하는 자료구조이다. 여기서 상호베타적이라는 말은 임의의 두 집합의 교집합이 공집합이라는 뜻이고 이는 각집합이 서로 서로소임과 동치이다. 이 자료구조를 이용하면 어떤 원소가 어느 집합에 속해 있는지를 판별하는 작업, 혹은 두 원소가 동일한 집합에 속하는지 판별하는 작업, 그리고 상호 베타적인 두 집합을 더 큰 하나의 집합으로 합치는 작업을 거의 O(1)이라는 시간 복잡도에서 해낼 수 있다. 이를 이용하여 해결할 수 있는 대표적인 문제로는 무방향 그래프의 연결된 컴포넌트를 찾는 문제를 풀 수 있다. 각 그래프의 정점을 별개의 상호 베타적 집합으로 초기화 하고, 두 정점을 잊는 간선을 탐색하며 두정점이 속한 집합을 하나의 집합으로 합친다. 이와 같은 .. 2018. 1. 18. GRID https://algospot.com/judge/problem/read/GRID 문제 We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled. Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-.. 2017. 10. 17. DICT https://algospot.com/judge/problem/read/DICT 문제 (주의: 이 문제는 TopCoder SRM428 Div2 Hard 의 번역 문제입니다.) a 와 b 로만 이루어진 단어들을 담고 있는 사전이 있다. 이 사전은 n 개의 a 와 m 개의 b 로 이루어진 단어들을 _전부_ 포함하는데, 예를 들어 n=2, m=2 인 경우, 사전에는 aabb, abba 등의 단어들이 포함된다. n 과 m 이 주어질 때, 이 사전의 k 번째 단어를 출력하는 프로그램을 작성하라. 단어들은 사전 순서대로 정렬되어 있다고 가정한다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C ( m >> k; if (c[n + m][n] < k || (n == 0 && m == 0)) { cout 2017. 10. 14. 이전 1 2 3 4 5 6 7 8 다음