컴공생 일상 블로그 컴공생 일상 블로그

어떤 문자열이 어떤 문자열들의 집합에 속하는지 알아내기 위해 단순히 모두 비교할 경우O(문자열의 길이 x 문자열의 개수) 의 시간 복잡도를 가진다. 이 때 문자열을 효율적으로 저장하고 탐색하는 자료 구조가 Trie이다. 대충 O(N) 그냥 그림을 보면 이해가 쉽다. 아래와 같이 4개의 단어가 있다고 해보자. Trie 자료 구조에 각 단어를 담아보면 아래와 같다.    트라이 자료구조는 주어진 문자열에 대해 앞 문자부터 하나씩 노드를 생성하면서 만들어진다. Insert1. 문자열에서 현재 문자를 확인2. 현재 문자로 이루어진 노드가 존재한다면 → 그 노드를 탐색존재하지 않는다면 → 새 노드를 생성 Find1. 문자열에서 현재 문자를 확인2. 자식 노드가 현재 문자인 노드가 있는지 확인, 없다면 return..

체비쇼프 거리 Chebyshev Distance 유클리드 거리와, 맨허튼 거리 외에도 체비쇼프 거리라는 것이 있다. 솔직히 특별한 거리는 아니고, 맨허튼 거리가 8 방향에 대해 적용되는 것이라고 보면된다. 노랑색 칸 부터 다른 칸들에 대해 체비쇼프 거리를 나타내면 다음과 같다. Flood Fill(BFS) 를 8 방향으로 돌려 얻거나, 격자의 좌표의 차이의 최대 값이 거리가 된다. strcut yx{ int y, x }; yx a, b; int distance = max(abs(a.x - b.x), abs(a.y - b.y)); https://www.acmicpc.net/problem/28452(체비쇼프 거리를 활용한 시뮬레이션 문제) 28452번: 탄막 게임 두 점 $A(x_1, y_1)$과 $B(x_..

- Hash(string to int) https://blog.joonas.io/143 문자열을 정수로 해싱하기 + 사전순 비교까지 (String to unique integer hashing) 문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 blog.joonas.io - RabinKarp https://junstar92.tistory.com/125 Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾..

- 일반적인 구간 합 계산 int arr[5] = {3, 2, 1, 5, 4}; arr에서의 2번째에서 4번째까지의 합 : 2 + 1 + 5 = 8 배열의 길이가 N 일 때, 일반적인 구간 합 계산으로는 O(N)의 시간 복잡도를 가진다. 만약 N의 길이가 조금만 커져도 해당 연산을 반복하게 되면, 매우 오랜 시간을 필요로 하게 된다.. 해당 경우, 세그먼트 트리를 사용하여, O(logN)의 시간 복잡도로 구간 합을 구할 수 있다. - 세그먼트 트리 해당 배열을 세그먼트 트리로 나타내면 아래와 같다. 트리는 노드는 9 개, 높이는 3인 이진트리 형태를 가진다. 루트 노드 : 총 합(전체 배열의 합) 리프 노드 : 배열의 각 원소 값 트리의 높이 : math.ceil(log2(N)) //ceil은 올림 함수..

단순 탐색 : O(N) 이진 탐색 : O(logN), 단 사전에 정렬이 되어 있어야 함. - STL의 binary_search #include #include using namespace std; int main() { int arr[] = { 3, 5, 1, 2, 7, 4, 7, 3, 3, 9 }; sort(arr, arr + 10); cout

- MST : 그래프의 모든 정점을 연결하는 최소 비용 트리 1) Kruskal 크루스칼 - 간선들을 가중치를 기준으로 오름차순 정렬 - 사이클이 생기지 않는 간선을 (정점의 개수 - 1) 개 만큼 뽑아냄 2) Prim 프림 - 최소 힙을 사용하여, 각 정점으로 부터 최소 간선을 선택해나감 - 크루스칼 알고리즘 - 크루스칼 구현 #include #include #include using namespace std; int N = 5; struct Node { int a, b; int price; }; vector line; int arr[10]; bool compare(Node t, Node v) { return t.price < v.price; } void Init() { for (int i = 0; i..

- Disjoint-Sets (서로소 집합들) 교집합이 존재하지 않는 집합 - UnionFind 로 해결 가능한 문제 - 특정 집합에 몇 개의 원소가 속해있는지 - 특정 원소가 같은 집합에 속해있는지 https://www.acmicpc.net/problem/10775 https://www.acmicpc.net/problem/1717 - Union 연산과 Find 연산 1. union(A, B) : B가 A의 밑으로 들어감, A와 B가 같은 조직이됨. find(B) : B의 최상위 부모를 찾음 = A 2. union(C, D) : D가 C의 밑으로 들어감, C와 D가 같은 조직이됨. 3. union(D, B) : B가 D의 밑으로 들어감, - UnionFind의 저장 각 - 코드 구현 #include us..

Subset Sum(부분 합 문제) : 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다. Ex) X = {8, 6, 7, 5, 3, 10, 9} T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE - Base Cases T = 0 이면, 선택하지않으면 항상 TRUE 이다. T < 0 이면, 항상 FALSE이다. - General Case(점화식) 총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다. 1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다. 2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이..