CS 공부/자료구조23 자료구조의 큰 그림 최종 수정 : 2025.04.18자료구조데이터를 효율적으로 저장하고 관리하는 방법을 학습하는 과목이다. 어떠한 구조로 데이터를 다룰지에 대해 학습한다.■ 자료구조와 알고리즘자료구조와 더불어 알고리즘을 함께 학습하는 것이 좋다. 둘 사이에는 깊은 연관성이 있다. 어떤 자료구조가 사용되었느냐에 따라 사용 가능한 알고리즘이 달라질 수 있기 때문이다.자료구조(data structure) : 데이터를 효율적으로 저장하고 관리하기 위한 방법알고리즘(algorithm) : 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차 ■ 시간 복잡도와 공간 복잡도자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 품질 좋은 코드가 될 가능성이 높다. 자료구조와 알고리즘의 고려 여부에 따른 성능의 차이는 '시간 복잡도'와 '공.. 2025. 4. 18. m원 탐색 트리(m-way search tree) 최종 수정 : 25.1.2m원 탐색 트리1. 정의와 특성최대 차수가 m인 트리로 인덱스를 만들기에 적합한 트리이다. 이진 탐색 트리의 확정된 형태로 높이를 줄이기 위해 사용한다. 루트와 단노드를 제외한 노드는 최소한 두 개의 서브 트리를 가지고, 최소 m/2 개, 최대 m 개의 서브 트리를 가진다. 각 노드의 키의 개수는 서브 트리의 개수보다 1 작다.2. B 트리의 정의와 특성B - 트리(Balanced tree)는 이진 트리에서 탐색 성능의 향상을 위해 단노드의 높이를 같게 한 균형 트리이다. 최대 m개의 서브 트리를 가질 수 있어 이를 m차 균형 트리(m-balanced tree)라 하여 m - 원 탐색 트리라고 한다. B 트리의 특징은 다음과 같다.모든 노드의 킷값은 정렬되어 있어야 한다.각 노드.. 2025. 1. 2. 이진 탐색 트리 최종 수정 : 25.1.2이진 탐색 트리1. 소개이진 탐색 트리는 임의의 키를 가진 원소를 삽입 * 삭제 * 검색하는 데 효율적인 자료구조로 모든 연산은 키값을 기초로 실행한다. 이진 탐색 트리는 이진 트리이며, 공백이 아니면 모든 원소는 다른 키를 갖는다. 왼쪽 서브 틀 원소들의 키가 루트의 키보다 작고, 오른쪽 서브 트리 원소들의 키는 루트의 키보다 큰 값을 가진다.2. 이진 탐색 트리의 탐색이진 탐색 트리에서 키값이 X인 원소를 탐색하는 방법은 루트를 시작으로 탐색한다. 이진 탐색 트리가 공백이면 탐색은 종료한다. 탐색하는 노드가 탐색 키와 같으면 탐색이 성공하고 해당 포인터를 반환한다. 반면에 키값이 같지 않으면 현재 노드의 키값과 탐색 키값을 비교하여 탐색 키가 크면 오른쪽 서브 트리를 탐색하고.. 2025. 1. 2. 힙(heap) 트리 최종 수정 : 25.1.2힙(heap) 트리1. 정의와 종류힙(heap)는 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조이다. 최대 힙(max heap)☞ 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리이며, 부노드의 키값은 자노드의 키값보다 항상 이상( ≥ )이다. 따라서 루트는 키값 중 가장 큰 노드가 된다. 최소 힙(min heap)☞ 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리로 부노드의 키값이 자노드의 킷값보다 항상 이하( ≤ )이다. 즉, 루트는 키값 중 가장 작은 값을 가진다. 이러한 힙은 최댓값이나 최솟값을 루트로 올려 빠르게 검색할 수 있는 트리로, 이는 정렬에서 사용된다. 이를 힙 정렬이라 한다.2. 우선순위 큐일반적인 큐는 선입 .. 2025. 1. 2. 이진 트리 순회 최종 수정 : 25.1.2이진 트리 순회이진 트리에서 각 노드를 차례로 방문하는 것을 순회라고 한다. 트리의 노드가 n개일 때 각 노드를 배열로 표현한 후 순회하면 nPn의 가지수를 가진다. 그러나 트리의 특성상 이진 트리의 형태를 유지하여야 하므로 트리의 순회는 구별된다. 임의의 한 노드에서 순회하는 방법은 왼쪽 서브 트리로의 이동(L)과 현재의 노드를 방문(D)하거나 오른쪽 서브 트리로의 이동(R)이 있다. 노드를 순회할 때 방문하는 순서에 따라 중위(inorder) 순회, 후위 (postorder) 순회, 전위(preorder) 순회가 있다.1. 종위 순회종위 순회(inorder) 순회는 왼쪽 서브 트리, 루트와 오른쪽 서브 트리를 반복적으로 순회한다. 즉, 루트부터 출발하여 가운데를 지나가는 순서.. 2025. 1. 2. 이전 1 2 3 4 5 다음
