코린이

트라이 (31강) 문자열을 효율적으로 처리하기 위한 트리 자료구조 + 단어 S를 삽입/탐색/삭제할 때 O(|S|) - 문자열을 그냥 배열에 저장하는 것 보다 최대 '4*글자의 종류'배 만큼 더 사용 (예를 들어 각 단어가 알파벳 대문자로만 구성되어 있을 경우 104배) 이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리에 비해 훨씬 느림. 일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제가 여럿 존재 대표적인 활용 사례 : 자동완성기능 (접두사, 접미사 관련) 부록A - 문자열 기초 (32강) 문자열을 가지고 복잡한 연산을 해야한다면 그냥 파이썬을 쓰자 C++에는 split과 같이 구분자를 기준으로 문자열을 나눠주는 함수가 없음 주의사항..

30강 (KMP) 드물게 나옴 S[a:b] = "S[a]S[a+1]...S[b-1]" lSl는 S의 길이 접두사 = 문자열의 첫 문자를 포함하는 연속한 문자열 접미사 = 문자열의 끝 문자를 포함하는 연속한 문자열 패턴 매칭 문제 실패함수 KMP : 패턴 매칭 문제를 O(|A| + |B|)에 해결할 수 있는 기적의 알고리즘 굉장히 헷갈림 먼저 KMP에서 쓰이는 실패 함수를 알면 KMP를 이해하는데 도움이 됨 실패함수 F(x) : 문자열 S[0:x+1]에서 접두사와 접미사가 일치하는 최대 길이 KMP

플로이드 (28강) 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘 시간복잡도 O(V^3) 음수의 가중치를 가져도 상관은 없지만, 음수의 사이클을 가지면 사용 불가 대입이 빈번하게 발생할 경우 min(a,b) 사용보다 if문으로 직접 비교를 통해 필요한 경우에만 대입이 일어나도록 하는 것이 시간복잡도 측면에서 더 효율적임. (DP, 플로이드 등) 경로복원 → nxt테이블 이용 (최단 거리 갱신이 일어날 때 갱신) nxt테이블을 이용해 한 단계씩 앞으로 전진하면서 경로를 복원할 수 있음 다익스트라 (29강) 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 음수인 가중치를 가지면 사용할 수 없음 (→ 벨만포드 알고리즘 이용) 우선순위 큐를 이용한 구현 시 시간복잡도 O(ElogE) ..

DSU Disjoint Set (서로소 집합)이란 서로 공통된 원소가 없는 집합을 말한다. = 유니온 파인드 (합집합 찾기) 공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구 2가지 union, find 연산을 지원한다. 1. union은 2개의 set을 하나의 set으로 합쳐주는 것 2. find는 어떤 element가 주어질 때, 이 element가 속해져 있는 대표 원소를 반환 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 Union : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침 (root를 찾아서, 높이가 작은 쪽을 큰 쪽으로 합침) → 유니온 바이 랭크 (..

최소 신장 트리(MST) (27강) 부분그래프 → 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프를 의미 신장트리 → 주어진 방향성이 없는 그래프의 부분 그래프들 에서 모든 정점을 포함하는 트리를 의미 최소신장트리 → 신장 트리중에서 간선의 합이 최소인 트리를 의미 크루스칼 알고리즘 (유니온 파인드 알고리즘 이용) 1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택 2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가 3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 ..

24강 (그래프) 그래프 = 정점과 간선으로 이루어진 자료구조 단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프 표현법 1 - 인접 행렬 방향그래프 int adj_matrix[10][10] = {}; int v, e; cin >> v >> e; for (int i = 0; i > u >> v; adj_matrix[u][v] = 1; } 무방향그래프 int adj_matrix[10][10] = {}; int v, e; cin >> v >> e; for (int i = 0; i > u >> v; adj_matrix[u][v] = 1; adj_matrix[v][u] = 1; } 표현..

이진검색트리 (22강) insert, erase, find, update → O(log N) 내부적으로 원소가 크기 순으로 정렬되어 있음 (★장점) 자가 균형 트리를 사용해야 O(log N)이 보장 됨 (편향된 트리 때문) STL - set, multiset, map set에서는 원소가 정렬되어있기 때문에 unordered_set과 달리 대소비교해서 값 찾는 연산이 O(log N)에 가능 iterator를 활용하여 prev, next, advance, lower_bound, upper_bound, find등의 연산이 O(log N)에 제공 O(log N)이지만 다른 O(log N) 연산에 비해 느린편임. 우선순위 큐 (23강) pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원..

해시 (21강) 해시함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 충돌문제 발생 (해시에 성능에 큰 영향) 충돌 회피 1 - Chaining 충돌 회피 2 - Open addressing - Linear Probing 충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식 장점 - Cache hit rate가 높다. 단점 - Clustering이 생겨 성능에 영향을 줄 수 있다. - Quadratic probing 충돌 발생 시 오른쪽으로 1,3,5,... 칸씩 이동하는 방식 장점 - Cache hit rate가 나쁘지 않다, Clustering을 어느 정도 회피할 수 있다. 단점 - 해시 값이 같을 경우 여전히 Clustering이 발생한다. - Double Hashing 충돌 발생 시 ..