릿코드의 문제 중에서 Trie(트라이) 또는 Prefix Tree를 구현하는 문제가 나온다. 문제 https://leetcode.com/problems/implement-trie-prefix-tree/description/ Implement Trie (Prefix Tree) - LeetCode Can you solve this real interview question? Implement Trie (Prefix Tree) - A trie [https://en.wikipedia.org/wiki/Trie] (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dat..

[네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 합니다. 일단 해당 알고리즘에서 사용하는 용어부터 설명하겠습니다. (네트워크 유량 알고리즘에서 간선은 두 정점을 잇는 파이프라고 생각하면 이해하기 쉽습니다.) 용량(Capacity) c(u, v)는 정점 u에서 v로 가는 간선의 용량(가중치)라고 합니다. 유량(Flow) f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미합니다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미합니다. r(u, v) = c(u, v) - ..

Boolean 변수들에 대해서 참, 거짓의 결정을 여러 번 해야 하는 문제를 충족 가능성 문제(Satisfiability Problem, SAT)라고 합니다. 특히 그중에 선 괄호 안의 각 절(clause)에 최대 두 가지 변수만이 존재하는 경우를 2-SAT 문제라고 합니다. 예를 들어 다음과 같은 식은 각 절에 두 가지 변수를 가지고 있습니다. (A || B) && (B || C) && (C || D) (이처럼 각 절들이 && 로 연결된 수식을 논리곱 정규형(Conjunctive normal)이라고 합니다.) 이제 2-SAT로 해결해야 하는 문제인 알고스팟 회의실 배정(MEETINGROOM) 문제를 풀면서 2-SAT에 대하여 알아봅시다. 문제 https://algospot.com/judge/proble..

절단점/단절점(Articulation point / Cut vertex) 절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점을 의미한다. 해설 게시글 [백준] No.11266 - 단절점 (C++, Articulation point) 절단선/단절선 (Bridge / Cut edge) 절단선이란 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선을 의미한다. 절단점을 먼저 공부하고 보면 쉽게 풀 수 있다. 해설 게시글 [백준] No.11400 - 단절선 (C++, Bridge)

문제 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 위상 정렬(Topological Sort)을 이용하여 임계 경로(Critical Path)를 구현하는 문제였다. 임계 경로(Critical Path) 임계 경로는 프로젝트 완성에 필요한 시간을 계산하는 스케줄 관리 도구로 자주 사용된다. 프로젝트는 각각의 작업으로 세분화되고 작업들은 특정 작업이 선수되어야만 하는 의..

가장 기본적인 분리 집합(Disjoint Set)을 구현하면 풀 수 있는 문제를 통해 유니온-파인드(Union-Find) 자료구조 살펴보자. 문제 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 가장 기본적인 분리 집합(Disjoint Set)을 구현하면 풀 수 있는 문제. 분리 집합은 유니온-파인드(Union-Find) 자료구조를 사용하여 구현할 수 있다. 유니온-파인드는..

Fenwick Tree 펜윅 트리 기존의 펜윅 트리에 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자. 펜윅 트리 (바이너리 인덱스 트리) - BaekJoon 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!) 백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다. 따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다. 하지만 원소의 업데이트는 한 개씩만 진행할 수 있다. 따라서 백준 - 수열과 쿼리 21(16975) 문제와 같은 구간의 업데이트를 요구하는 문제는 일일..

알고스팟 INSERTION - 삽입 정렬 뒤집기를 해결하기 위해 등장하는 자료구조. 트립(Treap) 대부분의 표준 라이브러리에서 제공하는 이진트리 자료구조들은 균형 잡힌 이진트리(레드- 블랙 트리 등..)으로 구현이 되어있다. 그대로 사용한다면 문제가 없지만 이진 트리에 추가적인 기능을 넣어주고 싶어도 레드 블랙 트리는 너무 구현이 복잡하다 보니 문제를 풀면서 처음부터 끝까지 구현해내긴 무리가 있다. 이럴 때는 비교적 간단히 균형 잡힌 트리를 만들어 주는 트립을 구현해보자. 트립(Treap)은 Tree와 Heap의 합성어로 말 그대로 heap의 특성과 tree의 특성을 합쳤다. heap에서는 부모 노드가 자식 노드보다 크다는 규칙만을 가진다. 트립에서는 이와 같이 부모 노드의 우선순위가 자식 노드의 우..

에라토스테네스의 체 "에라토스테네스의 체(Sieve of Eratosthenes)"는 3세기의 그리스 수학자 에라토스테네스가 정리한 소수를 찾는 방법이다. n이하의 자연수에서 소수의 배수를 차례대로 소거하여 최종적으로 n이 남아있다면 n은 소수임을 알아낼 수 있다. 에라토스테네스의 체 구현에는 해당 수가 소수인지 아닌지만 저장하는 bool형의 자료구조가 필요하며, 아래 두 가지의 최적화를 거친다. 1. n이 인수가 있다면 인수는 √n 이하의 수와 그 이상의 수의 쌍으로 이루어지기 때문에 √n의 수까지만 확인해도 판정이 가능하다. 2. i의 배수를 지울때는 i*i이하의 값들은 이미 i이하의 값의 배수(ex. i*3, i*4, i*5 ... i*(i-1) 는 이미 소거)이므로 i*i이상의 값부터 소거하면 된..