우선순위 큐(Priority Queue), 트라이(Trie)

우선순위 큐(Priority Queue) 우선순위 큐는(Priority Queue)는 데이터를 우선순위에 따라 저장하고 관리하는 자료구조이다. 보통 힙(Heap) 자료구조를 이용하여 구현한다. 우선순위 큐는 힙(Heap) 자료구조를 이용하여 구현할 수 있으며, 힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분된다. 최대힙은 부모 노드가 자식 노드보다 항상 큰 값을 가지고, 최소힙은 부모 노드가 자식보다 항삭 작은 값을 가진다. 이러한 특성 덕분에 우선순위 큐는 최대값(최소값)을 빠르게 찾을 수 있다. 힙은 부모노드와 자식노드 간의 우선순위를 비교하여 부모노드가 항상 자식노드보다 우선 순위가 높은 완전이진트리 형태의 자료구조이다. 이를 이용하여 우선순위 큐를 구현할 경우, 최상위 우선순위를..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 29.
• textsms

그래프(Graph)

그래프 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조를 의미한다. 연결된 정점간의 관계를 표현할 수 있는 자료구조로 지하철 노선도나 통신 네트워크, 길 추천 등에 사용된다. 그래프의 구조 정점(Vertex) : 각 노드를 의미한다. 간선(Edge) : 노드와 노드를 연결하는 선(Link, Branch) 인접 정점(Adjacent Vertex) : 간선 하나를 두고 바로 연결 된 정점을 의미함. 정점의 차수 (Degree) 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 * 2 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 나가는 간선의 수..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 28.
• textsms

AVL, Red-Black Tree

균형 이진 탐색 트리(Balanced Binary Search Tree) 균형 이진 검색 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리를 말한다. 노드의 삽입과 삭제가 일어 날 때 균형을 유지하도록 하는 트리이다. AVL 트리 AVL트리는 균형 이진 검색 트리의 일종으로, 균형 이진 탐색 트리와 같이 서브간의 높이가 최대 1인 트리를 말한다. AVL 트리는 Adelson-Velsky와 Landis에 의해 개발 되었으며, 이들의 이니셜을 따서 AVL 트리라는 이름이 붙여졌다. AVL 트리의 높이는 O(log N) 이므로, 검색, 삽입, 삭제의 시간 복잡도는 모두 O(log N)이다. AVL트리는 이진 검색 트리의 특성을 그대로 가지며, 높이 균형을 유지하면서 데이터를 추..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 28.
• textsms

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree) 이진트리는 아래의 규칙을 가지고 있는 자료구조이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리를 유지한다. 중복된 키를 허용하지 않는다. 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬된다. 이진 트리에 비해 탐색이 빠르다 (균형 유지) 균형상태 복잡도 O(logN) 불균형상태 복잡도 O(N) 이진 탐색 트리 - 삽입 Root 부터 비교를 시작 한다(중복 키 발견 시 노드 추가하지 않고 종료 된다.) 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동한다. 삽입할 키다 현재 노드의 키보다 크면 오른쪽으로 이동한다. Leaf 노드에 도달 후 데이터를 입력한다...

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 27.
• textsms

트리(Tree)

트리(Tree) 트리 자료구조는 계층 구조를 가지는 비선형 자료구조이다. 컴퓨터과학 분야에서 다양하게 활용이 되고 있다. 예를 들면, 파일 시스템, 디렉토리 구조, 데이터베이스 인덱스, 그래프 알고리즘등에 사용이 되고 있다. 트리는 하나의 루트(Root) 노드와 루트 노드를 중심으로 여러 개의 자식 노드들이 있는 노드들로 이루어져 있다. 각 노드는 다수의 자식 노드를 가질 수 있지만, 하나의 부모 노드만 가질 수 있다. 용어 노드(Node) : 트리 구조의 자료값을 담고 있는 단위 엣지(Edge) : 노드 간의 연결선(= link, branch) 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드 잎새 노드(Leaf) : 자식이 없는 노드 (= 단말) 내부 노드(Internal) : 잎새 노드를..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 25.
• textsms

해시 맵 - 문제

보호되어 있는 글입니다.

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 20.