Let IT Begin

* Python을 기준으로 합니다 유니온 파인드 (Union Find), 서로소 집합 (Disjoint Set) - 개념 집합 : 순서와 중복이 없는 원소들을 가지는 자료구조 유니온 파인드 (=서로소 집합) : 교집합이 없는 두 집합 관계를 의미 해당하는 원소가 그래프에 연결되어 있는지를 판별하기 위한 자료구조로써, 일반적으로 트리를 통해 구현함 노드의 개수가 $V$이고 $V-1$개의 union 연산과 $M$개의 find 연산이 가능할 때, 유니온 파인드의 time complexity는 $O(V+M(1+\log_{2-M/V}V))$ 유니온 파인드의 연산 Find : 특정 노드의 root를 확인하는 연산 (노드가 같은 트리에 연결되어 있는지를 판별) 현재 노드의 parent를 찾는다 Parent가 root..

* Python을 기준으로 합니다 우선순위 큐 (Priority Queue) - 개념 우선순위 큐 : 우선순위가 높은 데이터를 가장 먼저 삭제하는 큐 즉, 우선순위 큐는 데이터를 우선순위에 맞게 정렬하고 순서대로 추출할 수 있어야 함 이때 배열이나 연결 리스트를 사용한 구현은, 우선순위에 따른 삽입과 삭제에 많은 비용이 소모됨 따라서 우선순위 큐는 힙 자료구조를 사용하여 삽입과 삭제를 $O(\log n)$ 내에 처리하도록 함 우선순위 큐에서 최소힙을 적용하면 값이 작을수록 높은 우선순위를 부여하도록 할 수 있음 반대로 최대힙을 적용하면 값이 클수록 우선순위를 부여함 - 힙은 일반적으로 최소힙으로 구현되므로, 삽입 시 음수를 취하고 추출 시 다시 -1을 곱하는 방식으로 처리 - 구현 1. heapq 라이브..

* Python을 기준으로 합니다 힙 (Heap) - 개념 힙 : 특정 조건을 만족하면서 항상 완전 이진 트리 형태를 가지는 자료구조 힙의 조건 최대힙 : parent 노드가 항상 child 노드 보다 크거나 같다는 조건을 만족하는 힙 최소힙 : parent 노드가 항상 child 노드 보다 작거나 같다는 조건을 만족하는 힙 - 해당 힙 구조를 기반으로 최대/최소값 탐색을 $O(1)$ 내에 처리 가능 이때 힙은 단순히 위의 조건들만을 만족할 뿐, 정렬된 상태는 아님 - 구조적으로는 이진 탐색 트리와 유사하기 때문에 대부분의 연산은 $O(\log n)$ 내에 끝남 - BUT, 힙은 상/하 관계를 보장하고 이진 탐색 트리는 좌/우 관계를 보장한다는 차이가 있음 사용 예시 : 우선순위 큐, 힙 정렬, 다익스트..

* Python을 기준으로 합니다 트라이 (Trie) - 개념 트라이 : 문자열 탐색을 위한 트리 형태의 자료구조 어떠한 문자열 내에서 특정 단어를 검색한다고 하자 - 직관적으로 문자별 단순 비교를 사용하는 경우 $O(n^{2})$의 time complexity를 가짐 - 대신 트라이 구조를 적용하면 $O(n)$ 내에 탐색이 가능함 이때 트라이는 일반적으로 사용되는 이진 트리 형식이 아닌 다진 트리($m$-ary Tree) 형태를 가짐 장점 - 트라이를 구성하면 완전히 일치하는 문자열이 아니라 일부를 생략하더라도 탐색이 가능함 - 문자별로 트리가 만들어지기 때문에 자동적으로 정렬되는 효과가 있음 단점 - 문자의 수가 늘어날수록 메모리를 많이 사용함 - 구현 1. 노드 정의 트라이는 이진 트리가 아니라, ..

* Python을 기준으로 합니다 트리 (Tree) - 개념 트리 : 계층형 구조를 가지는 자료구조로써 순환 (Cycle)이 존재하지 않는 그래프 트리는 재귀적인 특성을 가지는 자기 참조 자료구조임 - 즉, 트리의 모든 노드는 자기 자신을 root로 하는 다른 서브 트리로 대표될 수 있음 트리의 한 노드가 가질 수 있는 child의 수에는 제한이 없지만, 일반적으로 최대 2개의 child 만을 가지는 이진 트리를 자주 활용함 이진 트리 (Binary Tree) 모든 노드가 최대 2개의 child만을 가지고, 왼쪽과 오른쪽의 child가 구별 가능한 트리 이진 트리의 종류 정 이진 트리 : 모든 노드가 0 or 2개의 child를 가지는 트리 완전 이진 트리 : 마지막 level을 제외한 트리의 각 lev..

* Python을 기준으로 합니다 그래프 (Graph) - 개념 그래프 : 노드(Node)와 각 노드를 연결하는 간선(Edge)으로 구성된 비선형 자료구조 서로 연결되어 있는 객체를 다루는 경우 유용 일반적으로 그래프는 연결 조건에 제약이 없지만, 특정한 제약 조건을 가지는 경우 가중치를 통해 표현함 주요 용어 인접 (Adjacent) : 간선으로 연결된 두 노드를 adjacent 하다고 함 차수 (Degree) : 노드에 연결된 간선의 수 경로 (Path) : 간선을 따라 이동하는 경로 - 이때 경로를 구성하는 간선의 수를 경로 길이 (path length)라고 함 그래프의 종류 방향성에 따라 방향 그래프 (Directed Graph) : 두 노드를 연결하는 간선에 방향성이 존재하는 그래프 - 하나의 ..