정리/자료구조 (3) 썸네일형 리스트형 [자료구조] 트라이 (Trie) 문자열 [자료구조 소개] 문자열을 char단위로 쪼개서 트리에 저장한 자료구조. 문자열 검색에 용이함. [자료구조 특징] 트리 사용. 재귀, 포인터(C++ 사용 시), 트리에 대한 지식 필요 공간, 시간 복잡도를 효율적으로 개선함 (기존의 방식으로 문자열을 찾으려면 문자열 길이 M, 배열 길이 N으로 복잡도가 $O(NM)$, 트라이는 $O(M)$) [코딩 방법] 클래스(구조체) 생성, 현재 노드가 끝인지(문자열이 끝인지) 확인하는 bool타입 변수와 자식노드를 가리킬 객체포인터배열(C++) 혹은 객체배열(Java) 생성. 객체포인터배열은 nullptr(C++) 혹은 null(Java)로 초기화. C++의 경우 동적할당을 사용하므로 자식노드를 삭제할 소멸자도 생성. (!if (child[i]) delete.. [자료구조] 트리, 이진 트리 그래프 이론 트리 [자료구조 소개] 정점이 V개일 때 모든 정점이 연결되어 있고 간선이 V - 1개인 그래프. [자료구조 특징] 순환하지 않는 그래프. [코딩 방법] 일반 양방향 그래프와 동일 [응용] 트리 동적 계획법 트라이 변형된 트리들 (이진 트리 등) 이진 트리 [자료구조 소개] 트리와 같으나, 하나의 루트 노드가 있고 자식 노드가 최대 두 개인 트리. [자료구조 특징] 일반 트리와 동일. 자식 노드가 최대 두 개. [코딩 방법] 자식 노드가 최대 두 개이므로 일반 그래프처럼 코딩할 이유가 없음. 보통 이진 트리를 사용하는 경우에는 루트 노드가 핵심이고 재귀를 사용하는 경우. 크기가 V이고 원소로 크기가 2인 배열을 갖는 2차원 배열을 생성하여 좌우 자식 노드를 저장하면 됨. [응용] 변형된 이진.. [자료구조] 분리 집합 (Union-Find) 그래프 이론 [자료구조 소개] 그래프의 노드끼리의 합집합에 대한 정보를 저장하는 자료구조. 서로소 집합(Disjoint Set)이라고도 함 [자료구조 특징] 재귀 사용 재귀를 사용하므로 최적화 필요 → 경로 압축 Union by Size, Union by Rank와 같은 최적화 방법도 존재 Union by Size를 사용하여 집합의 크기를 알 수 있음 [코딩 방법 / 일반적인 방법] [초기화] 사이즈가 N인 배열 생성, arr[i] = i로 초기화 [Find] parent[cur] != cur인 경우, parent[cur] = Find(parent[cur]) (경로 압축) 후 return parent[cur] parent[cur] == cur인 경우, return cur [Union] Union하는 두 .. 이전 1 다음