Study Log

정의상호 배타적 집합(서로소 집합)(Disjoint-Set)을 표현할 때 사용하는 그래프 알고리즘Disjoint-set은 공통 원소가 없는 상호 배타적인 부분집합들로 나눠진 원소들에 대한 정보를 표현하는 자료구조집합을 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어짐Union(합치기): 두 원소가 속한 집합을 하나로 합친다.Find(찾기): 해당 원소가 속한 집합을 반환한다.핵심은 각각의 집합을 하나의 트리로 나타내는 것Union-Find를 사용하면 특정 노드가 어느 집단에 속해 있는지 알 수 있다.트리의 구조를 사용해서 시간복잡도가 평균적으로 O(log N)이지만, 편향될 경우 O(N)이 될 수 있다.경로 압축(Path Compression), Rank기반 연산을 통해 최적화..

정의트리는 list, queue 등과 달리 한 노드가 여러 노드를 가리킬 수 있는 비선형적 자료구조최상위 노드가 존재하는 계층적인 형태단방향 그래프시작 노드에서 출발해서 다시 돌아올 수 없는 사이클이 없는 연결 그래프 용어노드(Node): 트리를 구성하는 데이터 원소간선(Edge): 노드와 노드를 연결하는 선 (노드의 개수 n, 간선의 수 n-1)루트 노드(Root Node): 부모 노드가 없는 트리의 가장 최상단에 있는 노드. 트리에 1개 존재부모 노드(Parent Node): 연결된 두 노드 중 위에 있는 노드자식 노드(Child Node): 부모 노드의 하위 노드형제 노드(Sibling Node): 같은 부모를 갖는 노드조상 노드(Ancestor Node) / 자손 노드(Descedent Node)..

Associative Containers데이터를 특정 기준에 따라 정렬된 상태로 유지하는 자료구조삽입되는 데이터가 항상 자동으로 정렬된 상태를 유지하며, 이를 통해 효율적인 검색, 삽입, 삭제 연산을 제공key - value 구조를 통해 요소에 빠른 접근은 가능하지만 삽입되는 요소의 위치를 지정할 수 없음Red-Black Tree를 기반으로 하고 데이터의 추가/삭제/접근의 시간복잡도가 O(log n) std::set#include #include int main() { std::set mySet = {3, 1, 4, 1, 5, 9}; // 요소 삽입 mySet.insert(2); // 요소 삭제 mySet.erase(4); // 요소 검색 if (mySet.f..

Sequence Container데이터를 순차적으로 저장하는 구조구현이 단순하고 가볍고 빠르기에 저장할 데이터가 정렬 상태를 계속 유지할 필요가 없을 때 선택 std::array#include using namespace std;int main() { int arr[5] = {1, 2, 3, 4, 5} int searchValue = 3; int changeValue = 6; for (int i = 0; i   특징크기 고정 (컴파일 타임에 크기가 고정 필요)요소는 연속된 메모리 공간에 저장인덱스를 사용하여 O(1) 시간 복잡도로 접근 가능크기 변경이 불가능사용 시기요소의 수가 고정되어 있고 변경될 가능성이 없는 경우.메모리 효율이 중요한 경우빠른 인덱스 접근이 필요한 경우 std..

#include 헤더파일에 존재한다. double linked list vector, deque와 다르게 멤버 함수에서 정렬(sort, merge), 이어붙이기(splice)가 있다. 임의접근 반복자 at(), [] 등으로 접근 불가. Iterator를 통해 하나씩 접근해야 한다.(양뱡향 반복자 ++, -- 사용하여 탐색) 연산자( ==, != , , =) 사용가능 using namespace std; 선언했다고 가정 생성자 list 변수이름 비어있는 list 컨테이너 생성 ex) list li; ex) list li; list li(10); default값(0)으로 초기화된 원소 10개를 가지는 list 생성 list li(3, 2); 2로 초기화된 원소 3개를 가지는 list 생성 list li2(l..