Competitive Programming 3rd(Uva Judge)8 Fenwick Tree(Binary Indexed Tree, BIT) FenwickTree 펜윅트리는 동적인 누적 빈도수 테이블을 구현할 때 유용한 자료구조이다. 여기서 동적인 누적 빈도수 테이블이란 다음의 예를 보면 쉽게 이해할 수 있다. 학생11명이 시험을 본다. 당연히 11개의 시험 결과과 나온다. 시험점수는 0 ~ 10점 사이이다. 학생들은 0점부터 10점까지의 점수를 받게되며 각 점수당 0 ~ 11명 사이의 학생이 해당점 수를 받을 수 있다. 즉, 0점을 받은학생, 1점을 받은학생, ... 10점을 받은학생을 다더하면 11명이된다. 그렇다면 0점을 받은 학생의 수, 1점을 받은학생의 수, 2점 ..., 10점을 받은 학생의 수를 알때 이에대한 누적합을 구하려고 한다. 여기서 누적합이란. "누적합(0)"은 0점을 받은 학생의 수이다. "누적합(1)"은 0점을 받은 .. 2018. 1. 19. Uva 11902 - Domanitor Problem link https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=229&problem=3053&mosmsg=Submission+received+with+ID+20625091 Description Problem 위 문제는 시작점이 무조건 0이고, '지배하다'의 뜻만 이해하면 된다. 노드 x가 노드 y를 지배한다면 다음을 만족해야된다. 0 에서 x를 거치지 않고서는 y로 갈 수 없다. 즉, y로가는 모든 경로는 x를 거쳐야 된다. Algorithm to Solve Problem 해당 문제를 해결하기 위하여 DFS(Depth first Search)알고리즘을 이용한다.해당 문제에.. 2018. 1. 18. Segment Tree Segment Tree 구간 트리는 자료를 이진트리의 형태로 조직화한 트리로서 동적인 구간 질의에 효율적으로 답하기 위한 자료구조이다. 여기서 동적이라는 말은 자료를 갱신해 가면서 질의에 답할 수 있어야 한다는 뜻이다. 구간질의란 데이터가 저장된 자료구조(여기서는 선형적 예를 들어 배열을 다룰 것이다.)에서 임의의 구간이 주어 졌을때 그 구간에 대한 질의를 뜻한다. 예를 들어 구간 최소질의(RMQ, Range Minimum Query)가 이해 해당된다. RMQ는 해당되는 칸의 최솟값의 인덱스를 구하는 문제이다. 다시말해 구간트리를 이용하여 이같은 문제를 효율적으로 해결할 수 있다는 것이다. 구간트리는 이진 트리의 형태로서 모든 노드의 자식은 둘 이하이다. 구간 트리는 각 노드가 해당되는 구간에대한 질의의.. 2018. 1. 18. Union Find Disjoint Set (UFDS) 유니온 파인드 상호배타적 집합 상호 베타적인 집합들을 모델랑하는 자료구조이다. 여기서 상호베타적이라는 말은 임의의 두 집합의 교집합이 공집합이라는 뜻이고 이는 각집합이 서로 서로소임과 동치이다. 이 자료구조를 이용하면 어떤 원소가 어느 집합에 속해 있는지를 판별하는 작업, 혹은 두 원소가 동일한 집합에 속하는지 판별하는 작업, 그리고 상호 베타적인 두 집합을 더 큰 하나의 집합으로 합치는 작업을 거의 O(1)이라는 시간 복잡도에서 해낼 수 있다. 이를 이용하여 해결할 수 있는 대표적인 문제로는 무방향 그래프의 연결된 컴포넌트를 찾는 문제를 풀 수 있다. 각 그래프의 정점을 별개의 상호 베타적 집합으로 초기화 하고, 두 정점을 잊는 간선을 탐색하며 두정점이 속한 집합을 하나의 집합으로 합친다. 이와 같은 .. 2018. 1. 18. 이전 1 2 다음