Study (16) 썸네일형 리스트형 트라이(Trie) 트라이 구조는 문자열을 처리하는 알고리즘으로, 여러 문자열을 트리 구조를 활용하여 빠르게 처리하는 자료 구조이다. 맵을 사용한 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct Node { map nxt; bool end; Node() { nxt.clear(); end = false; } void insert(char *val) { if(*val == '\0') end = true; else { if(!nxt[*val]) nxt[*val] = new Node(); nxt[*val]->insert(val+1); } } }; Colored by Color Scripter cs 포인터를 사용한 구현 기준 문제 : https://www.acmicpc.net/proble.. 가우스 소거법 가우스 소거법은 연립 방정식의 해를 구하는 방법 중 하나로, O(N3) 알고리즘으로 쉽게 구현할 수 있다. 구현 기준 문제 : https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4.. 느리게 갱신되는 세그먼트 트리 세그먼트 트리의 구간 갱신을 빠르게 처리하기 위한 방법으로, 별도의 배열을 사용하여 필요한 만큼만 부분적으로 세그먼트 트리의 값을 갱신하여 시간복잡도를 줄일 수 있습니다. 구현 기준 문제 : https://www.acmicpc.net/problem/2934 2934번: LRH 식물 상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3.. FFT 문제 : https://www.acmicpc.net/problem/10531 10531번: Golf Bot Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across www.acmicpc.net 개요 FFT는 고속 푸리에 변환을 의미하며, PS에서는 보통 다항식의 계산을 빠르게 계산할 때에 사용합니다. 알고리즘의.. 이분 매칭(소스코드) https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include #define NMAX 205 using namespace std; int n, m, s, si; int i.. KMP 알고리즘 개요 KMP 알고리즘은 3명의 학자(Knuth-Morris-Pratt)가 만든 문자열 탐색 알고리즘입니다. 문자열(S)에서 문자(W)를 찾을 때 사용하는 알고리즘으로, O(|S| + |W|)의 시간복잡도를 가지는 어마어마한 알고리즘입니다. |S|와 |W|는 각각 문자열의 길이를 의미하며, 전체 시간 복잡도가 문자열과 문자 길이의 합이라는 건 단 1번의 탐색으로 문자열 속 문자를 모두 찾을 수 있다는 의미로, 매우 효율적인 탐색 알고리즘 중 하나입니다. 그럼 도대체 어떤 방식으로 탐색해서 이렇게 효율적인지 한번 알아봅시다. 알고리즘 영문 위키피디아의 예시를 통해 기본적인 알고리즘 구조를 살펴보겠습니다. 우선 문자열 S = "ABC ABCDAB ABCDABCDABDE"에서 문자 T = "ABCDABD" 를 .. 단절점과 단절선 개요 단절점과 단절선은 무방향 그래프에서 각각의 정점 또는 간선을 제거했을 때, 그래프가 나눠지게 만드는 정점(단절점) 및 간선(단절선)을 의미합니다. 단절점과 단절선은 모든 정점에서 DFS를 진행하면 구할 수 있지만, 단 1번의 DFS 탐색으로 모든 단절점과 단절선을 구할 수 있습니다. 그리고 이 개념은 방향 그래프에서 SCC를 나눌 때에도 사용할 수 있습니다. 단절점 구하기 단절점을 구하기 위해서는 DFS 탐색 트리를 만들어야 합니다. DFS 탐색 트리를 만들어서 정점에 방문한 순서대로 번호를 매기고, 각각의 정점에서 갈 수 있는 가장 낮은 위치를 찾는 알고리즘을 사용합니다. 여기서 말하는 가장 낮은 위치란 트리에서 높이가 낮은 정점을 의미하며, 우리는 방문 순서에 따라 트리를 만들고 있기에 방문 순.. 2-SAT 구하기 개요 2-SAT는 N개의 논리값을 가지는 변수를 사용하여 논리곱 정규형으로 표현했을 때, 각각의 절에 변수가 2개씩 존재하는 논리식을 의미합니다. 2-SAT는 기본적으로 아래와 같은 형식을 가지고 있습니다. f = (~X1 ∨ X2) ∧ (~X2 ∨ X3) ∧ (X1 ∨ X3) ∧ (X3 ∨ X2) 이렇게 논리식 f를 참(true)로 만족하게 만드는 X1 ~ X3까지의 값을 구하는 것이 2-SAT 문제의 핵심입니다. 그럼 2-SAT의 값은 어떻게 구할 수 있을까요? 물론 X1 ~ X3까지 참(true)과 거짓(false)을 하나씩 넣어보는 브루트포스 방식으로 풀 수 있습니다. 그리고 2-SAT를 제외한 대부분의 CNF 문제(Ex. 3-SAT, 5-SAT)들은 NP-Hard문제로 브루트포스 방식으로 해결해.. 이전 1 2 다음