판교의 메타몽

개요Trie란?LeetCode 208번 문제 - Implement Trie (Prefix Tree)  1.  Trie란?문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조이다.Trie라고 적고 try로 발음되며, 다른 말로는 래딕스 트리(Radix Tree), 접두사 트리(Prefix Tree), 또는 탐색 트리(Retrieval Tree)라고도 한다.  우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화된 자료구조이며,디테일한 설명은 박지훈님이 작성한 [자료구조] 트라이(Trie)를 참고하자. [자료구조] 트라이 (Trie)트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.우리가 검색할 때 볼 수 있는 자동완성 기능,..

map과 unordered_map의 차이 요약 map unordered_map 시간복잡도 O(logN) O(1) 데이터 정렬 레드블랙 트리 (Red-Black Tree) -> 중복허용 X, Key를 기준으로 오름차순 자동정렬 해시테이블 (Hash Table) -> 중복허용 X, 정렬되지 않음 권장하는 사용법 1. 데이터 양이 보다 적을때 권장 2. Key를 이용하여 정렬을 해야할때 권장 대량의 데이터를 저장할때 권장 * 레드블랙트리 : 이진탐색트리의 일종 * 해시테이블 : 키 값을 주소로 사용 map활용 예시 : 사용된 영어 단어들을 1. 빈도순 2. 문자순으로 정렬 예를들어 사용된 단어들이 1. 많이 사용됐을수록, 2. 사전순으로 앞에 올수록 더 앞에 위치하게 정렬을 한다고 가정해보자. map을 사용하..

링크 : https://hongjw1938.tistory.com/22 자료구조 - 우선순위 큐(Heap, Priority Queue) 1. 우선순위 큐(Priority Queue)란? 이 자료구조는 우선순위 큐라는 말에서 볼 수 있다시피 우선순위가 높은 것을 먼저 꺼내기 위하여 만들어진 자료구조이며, 힙(Heap)이라고도 부른다. 예를 들어서, hongjw1938.tistory.com

용어 정리 정점 : Node, Vertex 간선 : Edge G = (V,E) 1. 인접행렬 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용 A[i][j] = w (i->j의 간선이 있을때, 그 가중치), 0(없을때) 알고리즘 테스트에서 거의 사용되지 않는데, 비효율적이어서 그렇다. 예를들어 간선이 정점이 10만개이고 간선이 100만개 이면 행렬은 100억개의 공간을 가지게 되는데, 쓰지 않을 공간까지 자리를 할당해주니 비효율적일 수 밖에 없다. 정 사용할거면 연결이 되어 있느냐 없느냐 정도만 활용하기 위해 bool문으로 선언할 것을 권장한다. 2. 인접 리스트 리스트를 이용해서 구현 A[i] = i와 연결된 정점을 리스트로 포함하고 있음 효율성 : O(V의 차수). 정점 V에 연결된 정..

LCA(Lowest Common Ancestor) 알고리즘 AKA. 최소 공통 조상 알고리즘 요약 : 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다. 구현법 : 일반적으로 DFS를 활용해 구현한다. 다이나믹 프로그래밍(DP), 세그먼트 트리를 활용해 시간 복잡도를 개선할 수 있다. (1) 모든 노드에 대한 깊이(depth)를 계산한다. (2) 최소 공통 조상을 찾을 두 노드를 확인한다. (2)-(1) 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. = 같은 라인에 위치할때까지 올라간다. (2)-(2) 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. (3) 모든 LCA(a,b) 연산에 대하여 2번의 과정을 반복한다. 기본 구현 코드 /..

map Key와 Value를 쌍으로 자료를 보관하는 컨테이너. map은 자료를 저장할 때 내부에서 자동 정렬을 하고, hash_map은 정렬하지 않는다. 레드 블랙 트리 자료구조를 사용하며, 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 저장한다. (오름차순) 따라서 정렬이 필요하지 않은 곳에서 hash_map을 사용하는 것은 메모리 낭비이다. STL로 map과 iterator를 추가해야 한다. map 변수명 (ex : map map1 ) 맵 생성 변수명.size() (ex : map1.size() ) 맵의 사이즈 반환 변수명.empty() (ex : map1.empty() ) 맵이 비어있으면 1(true), 아니면 0(false)를 출력 insert 방법 1 : 변수명[key] = value (..

플로이드 - 워셜(와샬) 알고리즘 (Floyd-Warshall Algorithm) 동적 계획법에 속하는 알고리즘으로, 그래프에서 모든 꼭지점 사이의 최단 경로를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 문제없이 알고리즘이 동작된다. 3중 for문으로 구현되며, 구성은 다음과 같다. 가장 바깥쪽 for문 : 거쳐가는 꼭지점 두 번째 for문 : 출발 꼭지점 세 번째 for문 : 도착하는 꼭지점이다. 시간복잡도는 for문이 3개인 관계로 O(n^3)이다. for(int k = 0; k < n; ++k){ //거쳐가는 꼭지점 for(int i = 0; i < n; ++i){ //출발 꼭지점 for(int j = 0; j d[i][k] + d[k][j]){ d[i][j] = d[i][k] ..

이진 탐색(Binary Serach) 정의 참고 링크 : www.youtube.com/watch?v=W7RGHiN0Mmw&t=96s 1) 저장된 값을 정렬한다. 2) 왼쪽 = 첫번째 값 / 오른쪽 = 맨 마지막에 위치한 값 / 중간값 = 그 중간의 값 3) 중간값과 원하는 값의 차이에 따라 탐색하는 값의 범위를 변경해 나간다. (ex : 원하는 값이 중간값보다 크다 -> 왼쪽 = 중간값 + 1 원하는 값이 중간값보다 작다 -> 오른쪽 = 중간값 -1) 4) 원하는 답이 나올때까지 3번의 과정을 반복한다 이진 탐색(혹은 이분 탐색, 이분 검색)은 탐색 기법 중 하나이며, 원하는 값을 탐색 범위를 두 부분으로 분할하여 찾는 방식이다. 단, 이미 오름차순 혹은 내림차순으로 정렬된 구조에서 사용 가능하다는 조건..

동적계획법 (Dynamic Programmign) = Memoization(메모이제이션) 한줄 요약을 하자면, 기존에 구했던 답을 재활용해서 불필요한 연산은 배제하는 계산법이다. 연산의 효율성을 위해 여러 문제를 나눠서 풀고, 이 과정에서 이미 구한 답을 활용해 불필요한 계산식은 배제한다. 피보나치수열 - (일반 재귀풀이) #include using namespace std; int Fibo(int x){ int total = 0; if(x=2){ total+=Fibo(x-2)+Fibo(x-1); } return total; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; cout ..

백 트래킹 (Back Tracking) 말 그대로 왔던 길을 다시 추적하는 알고리즘. 즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면 모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. Brute Force와는 차별화된 Back Tracking의 특징은 필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다. 이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다. 백 트레킹에는 크게 3가지 종류가 있다. 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search), 큐를 이용하는 BFS(너비우선탐색, Breadth First Search) BFS/HS(최선우선탐색,..