독서/C언어로 쉽게 풀어쓴 자료구조12 [CDS] chapter 11 : 그래프 ② 1. 최소 신장 트리그래프내의 모든 정점을 포함하는 트리를 신장 트리(spanning tree)라고 한다. 트리는 '사이클이 없는 연결 그래프'라는 점에서 신장 트리 또한 트리와 마찬가지로 정점이 n개이면 정확히 n - 1개의 간선을 갖게 된다. 잘 생각해보면 신장 트리는 그래프에서 간선의 수가 가장 적은 '최소 연결 부분 그래프'이고, 하나의 그래프에는 여러 신장 트리가 존재할 수 있음을 알 수 있다. 어떤 그래프에서 DFS 또는 BFS 도중에 사용된 간선만 모으면 신장 트리가 된다. 최소 신장 트리(MST, Minimum Spanning Tree)는 간선에 가중치가 부여되어 있는 가중치 그래프에서, 가중치 합이 최소인 신장트리를 말한다. MST를 구하는 대표적인 두 알고리즘이 이하에서 살펴 볼 크루.. 2025. 5. 6. [CDS] chapter 10 : 그래프 ① 1. 그래프 개념그래프(graph)는 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 이전에 공부했던 트리는 계층적인 자료를 표현하는데 적합한 자료구조인데, 결국 이 트리는 그래프의 특수한 한 형태라고 볼 수 있다. 좀 더 엄밀하게 정의하면 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이고, 트리는 사이클이 없는 연결 그래프이다.그래프에서는 많은 용어들이 나오는데, 이하에서 정리하고 넘어가자.부분 그래프 : 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 말한다.완전 그래프 : 그래프의 모든 정점이 서로 연결되어 있는 그래프이다. 정점의 차수 : 어떤 정점과 간선에 의해 직접 연결된 정점을 인접 정점이라 하고, 이 인접 정점의 수를 차수라 한다.경로와 사이클 : 간선이 존재.. 2025. 4. 17. [CDS] chapter 9 : 우선순위 큐 1. 개념이전에 정리한 자료구조 큐는 선입선출 원칙에 의해 먼저 들어온 데이터가 먼저 나가게 된다. 이는 먼저 들어온 데이터가 높은 우선순위를 갖는 것이다. 어떤 우선순위가 존재하고 데이터가 출력되는 순서가 이 우선순위에 의하는 자료구조를 자연스럽게 생각해 볼 수 있다. 이처럼 각 요소에 우선순위가 부여되어, 이중 가장 높은 우선순위의 요소가 먼저 나가는 자료구조를 우선순위 큐라고 한다. 잘 생각해보면 큐나 스택 모두 우선순위 큐의 특수한 태양으로 이해할 수 있다. 적절한 우선순위를 부여하면 우선순위 큐는 큐나 스택과 같이 동작할 것이다. 구현 파트에 서술해놓은 우선순위 큐의 추상자료형을 보면 알 수 있듯이 우선순위 큐에도 당연히 여러 연산이 존재한다. 다만 이들 중에서 가장 중요한 두 연산은 삽입 연.. 2025. 3. 10. [CDS] chapter 8 : 트리 1. 트리 기본트리는 한 개 이상의 노드로 이루어진 유한 집합으로, 계층적인 자료를 표현하는데 적합한 자료구조이다. 항목들이 순차적으로 저장되는 선형 자료구조는 각 항목간의 관계를 표현하기 어려워 더이상 적합하지 않게 된다.트리 자료구조와 관련된 용어는 위 그림으로 정리하면 된다. 위 그림에 더하여, 노드의 차수는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다는 것만 추가적으로 정리하자.(더하여, 책에서는 루트의 레벨을 1로 놓고 트리의 높이 등을 계산하고 있다는 점이 위 그림의 표현과 차이점이다)2. 이진트리(1) 정의 이진 트리는 모든 노드가 2개의 서브 트리를 가지고 있는 트리로, 가장 많이 쓰이는 트리라고 한다. 여기서 서브 트리는 공집합일 수 있기 때문에 모든 노드의 차수는 2 이하가 된.. 2025. 3. 5. [CDS] chapter 7 : 연결리스트 ② 1. 특수한 연결 리스트(1) 원형 연결 리스트원형 연결 리스트(Circular Linked List)는 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드의 주소가 되는 리스트이다. 따라서 원형 연결 리스트에서는 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 연결 리스트에서 노드의 삭제 또는 삽입을 수행하려면 항상 선행 노드를 가리키는 포인터가 필요하기 때문에, 단순 연결 리스트에 비해 노드의 삽입, 삭제가 용이할 것이다.이러한 원형 리스트의 한 변형된 형태로, head 포인터가 리스트의 마지막 노드를 가리키도록 구성할 수 있다. 이 경우 리스트 끝의 노드를 삽입, 삭제할 때 유용할 것이다. 단순 연결 리스트에서는 이 끝 노드에 찾아가는 데에 길이에 비례한 시간이 소요될 것이지만 원형 연결.. 2025. 2. 12. 이전 1 2 3 다음
