C19 그래프 탐색 - 너비 우선 탐색 BFS 이번에는 그래프 탐색의 다른 방식인 BFS에 대해서 소개해드리겠습니다. 1. 너비 우선 탐색 Breadth First Search, BFS 지난번에 본 깊이 우선 탐색(DFS)는 한 정점에서 시작해서 갈 수 있는 정점까지 방문한 후에 방문하지 않은 인접 정점이 있는 정점으로 돌아와서 진행하는 방식이었습니다. 이번에 배울 너비 우선 탐색은 정점에 인접한 정점들을 모두 한 번씩 방문하고 나서 방문했던 정점들의 인접한 정점들을 다시 한 번씩 방문하는 방식입니다. 또한 정점들마다 너비 우선 탐색을 수행하기 위해서 큐를 이용합니다. 이점도 DFS와 차이점을 보이고있습니다. DFS와 마찬가지로 배열과 큐를 이용하는데 배열에는 방문 정보를 담고 큐에는 방문 기록을 남기기 위해 사용합니다. A에서 시작하도록 하겠습니다.. 2021. 10. 9. 그래프 탐색 - 깊이 우선 탐색 DFS 그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 종류가 있는 그중에서 깊이 우선 탐색 부터 알아보겠습니다. 1. 깊이 우선 탐색 Depth First Search, DFS 깊이 우선 탐색은 한 정점에서 시작하여 한 방향으로 진행해 갈 수 있는 정점까지 최대한으로 탐색합니다. 그러다가 더이상 진행할 수 없다면 가장 최근에 만난 갈림길이 있는 정점으로 돌아가서 다른 방향의 간선으로 진행할 수 있는지 탐색하는 방식입니다. 깊이 우선 탐색에서는 탐색한 경로의 정보를 담기 위해서 스택을 이용하고, 정점에 대해 방문한 정보를 기록하기 위해서배열을 이용합니다. 말로했을 때.. 2021. 10. 8. 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다. 1. 인접 리스트 인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스트로 표현해보면 다음과 같습니다. 그림을 보고나면 대충 감이 잡히실겁니다. 각 정점에 대해서 노드는 간선의 갯수만큼 연결되어있습니다. 맨 처음의 A, B, C, D 노드를 헤드 포인터라고 하며, 이 헤드 포인터는 그래프의 정점의 갯수만큼을 필요로합니다. 즉, 무방향 그래프의 노드의 수 만큼의 연결 리스트가 만들어지고 각 연결 리스트는 정점이 가진 간선의 갯수(차수, degree)만큼의 길이를 가지게 됩니다. 만약 방향 그.. 2021. 10. 5. 그래프 구현 1 - 인접 행렬로 그래프 구현하기 모든 자료구조가 그래왔듯이 그래프를 구현하는 방식에는 순차 자료구조를 이용하는 방식과 연결 자료구조를 이용하는 방식 두가지가 있습니다. 그래프에서도 마찬가지이지만 이름을 조금 다르게 부릅니다. 순차 자료구조를 이용해서 구현하는 것을 인접 행렬 기반 그래프, 연결 자료구조를 이용해서 구현하는 것을 인접 리스트 기반 그래프 라고합니다. 오늘은 첫 번째 순차 자료구조를 이용한 방식인 인접 행렬을 이용한 그래프를 구현해보겠습니다. 1. 인접 행렬 Adjacent Matrix 인접 행렬은 그래프에서 정점이 어떤 간선으로 연결되었는지를 나타내는 행렬입니다. 정점 n개의 그래프에 대해서 nXn행렬을 이용합니다. 이때 정점끼리 연결되어 있다면 행렬의 값을 1로, 연결되어있지 않다면 행렬의 값을 0으로 이용합니다. 예시.. 2021. 10. 4. 힙 Heap 힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 히프는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합니다. 1. 힙 Heap 힙은 이진 트리의 노드들 중에서 키값이 가장 큰 값또는 가장 작은 값을 찾기 위한 자료구조입니다. 이때 가장 큰 값을 찾으면 최대 힙, 가장 작은 값을 찾으면 최소 힙이라고 합니다. 또 다른 특징은 힙은 같은 키값을 가진 노드를 가질 수 없다는 점 입니다. 그래서 최대 힙에서는 가장 큰 키값을 가진 노드가 루트 노드가 되고, 최소 힙에서는 가장 작은 키값을 가진 노드가 루트 노드가 됩니다. 힙을 1차원 배열로 구현하기 때문에 배열의 인덱스를 통해 트리간의 부모 자식관계를 쉽게 알 수 있다.. 2021. 10. 2. AVL 트리 이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진 트리는 오른쪽으로 한 번 이동하는 연산만을 수행하면 됩니다. 이처럼 노드가 늘어날수록 그 차이가 커집니다. 이처럼 노드가 늘어나서 불균형해질수록 이진 트리의 연산횟수가 증가하는 단점이 있는데, 이 단점을 보완한 트리를 균형 이진 탐색 트리 혹은 균형 트리라고 합니다. 이 균형 트리에는 B 트리, AVL 트리 2-3-4 트리 등이 있는데 오늘은 이 중에서 AVL 트리에 대해서 알아보려고 합니다. 1. AVL 트리 Adelson-Velskii.. 2021. 10. 1. 이전 1 2 3 4 다음 300x250
