펜윅 트리(Fenwick Tree) 펜윅 트리는 바이너리 인덱스 트리(Binary Indexed Tree)라고도 부른다. 순서를 갖는 데이터가 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 트리 형태의 자료구조이다. 기본 원리 https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 펜윅 트리를 구현하기 위해선 어떤 수를 이진수로 나타냈을 때 마..

스위핑 알고리즘(Sweeping Algorithm)공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료 지점까지 지나가는데, 마주치는 요소들에 대해 판단이 되는 기준을 적용해 정답을 구하는 방식이다.즉, 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 된다. 문제 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도www.acmicpc.net#include #include #include #include #include using na..

강한 연결 요소(Strongly Connected Component) 두 정점에 대해 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강 결합 컴포넌트(SCC)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존재하는 정점들은 같은 SCC에 속한다고 할 수 있다. 방향 그래프에서만 정의된다. 1. 타잔 알고리즘 1) 기본 원리 깊이 우선 탐색 방향 그래프의 정점들을 방문한 후 방문한 정점의 간선을 통해 상위에서 방문된 정점을 방문한다면 SCC가 존재한다고 판단한다. 2) 문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,00..

최소 신장 트리(Minimum Spanning Tree) 모든 정점을 연결하는 트리를 신장 트리라고 하는데 가중치를 갖는 신장 트리 중 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다. 대표적으로 크루스칼 알고리즘이 있으며, 그 외에도 프림 알고리즘과 솔린 알고리즘이 있다. 프림 알고리즘: 임의의 정점을 루트 노드로 삽입한 후 인접한 정점의 간선 중 가장 작은 정점을 트리에 삽입하며 최소 신장 트리를 만든다. 솔린 알고리즘 1. 크루스칼 알고리즘(Kruskal's algorithm) 1) 기본 원리 모든 간선의 가중치를 오름차순으로 정렬한 후 그 목록을 차례대로 순회하며 사이클이 생기지 않도록 최소 신장 트리에 삽입하며 최소 신장 트리를 만든다. 2) 문제 www.acmicpc.net/pr..

세그먼트 트리(Segment Tree) 배열 내 범위 값을 구하거나 특정 범위의 값들을 변경할 때 빠르게 접근하기 위해 사용한다. 이름 그대로 구간들을 보존하고 있는 트리이다. 리프 노드는 배열의 그 수 자체를 의미하고 리프 노드 외 노드들은 자식 노드를 대표하는 값이다. 리프 노드를 제외한 노드는 비워져있는데, 세그먼트 트리의 목적에 따라 채워야한다. 기본 원리 : 합 https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 ..

비트마스크(BitMask)집합 요소들의 구성 여부를 표현할 때 유용한 테크닉이다. 기본 원리{1, 2, 3, 4, 5}라는 집합이 있고 이 집합의 부분집합을 구해야 한다.{1}, {2}, ..., {1, 2}, ..., {1, 2, 5}, ..., {1, 2, 3, 4, 5} 물론 간단히 반복문을 통해 경우의 수를 구할 수 있다.하지만 비트 마스킹을 하면 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.{1, 2, 3, 4, 5} → 11111{2, 3, 4, 5} → 11110{1, 2, 5} → 10011{2} → 00010 1) 삽입i번 째 비트 값을 1로 변경하려고 한다. 이때 OR 연산을 활용한다.i = 3일 때, 10101 | (1 → 10101 | 01000 → 11101 2) 삭제i..