알고리즘, 그래프
// 공부는 한번 할 때 한번에 끝낼 것. 2-3년 후에 다시 보기 싫다면.
* 내용은 과거 알고리즘 과목 수강 당시 강의 자료로 남은 자료를 다시 참고하여 공부한 내용입니다.
그래프?
정점(vertex)와 간선(edge)으로 표현. 간선으로 이어진 정점들은 인접(adjacent)해 있다고 표현한다.
그래프 종류
- 가중치도 방향성도 없는 기본 그래프
- 가중치가 있는 그래프
- 유향 그래프(directed)
- 가중치가 있는 유향 그래프
그래프의 표현 방식
- 2차원 배열
- Linked List
> 정점을 키 혹은 인덱스로 활용하는 방식으로 구현한다.
BFS(Breadth-First Search), 너비 우선 방식
1. 시점을 기준으로 인접한 정점들을 우선 방문한다.
2. 이전에 방문한 정점들과 인접하지만 방문하지 않은 정점들을 방문한다.
3. 모든 정점들을 방문할 때까지 위의 과정을 반복한다.
-> 자료에 따르면 queue를 활용한 방식으로 구현하였다.
DFS(Depth-First Search), 깊이 우선 방식
1. 시점을 기준으로 연결된 첫번째 정점을 우선 방문한다.
2. 방문한 정점과 인접하지만 방문하지 않은 정점을 하나 방문한다.
3. 방문할 정점이 없을 때 방문한 이전 정점과 인접하지만 방문하지 않은 정점이 있다면 방문한다.
4. 모든 정점들을 방문할 때까지 위의 과정을 반목한다. 아마도..?
-> 자료에 따르면 stack을 활용한 방식으로 구현하였다.
트리? 포레스트?
트리: 그래프를 구성하는 임의의 두 정점 사이 간선이 1개인 그래프.
포레스트: 서로 간선으로 연결되어 있지 않은 트리가 여러 개가 모인 집합.
연결 그래프, connected graph
정점과 간선으로 구성된 그래프들 중에서 임의의 두 정점 간의 경로가 존재하는 그래프. => 모든 정점이 간선들로 연결된 그래프.
사이클: 어떤 정점에서 간선들을 따라 전진하다 보면 다시 그 정점에 도달하는 경우 그래프에 사이클이 있다고 표현.
트리: 연결 그래프 중에 사이클이 없는 것. n개의 정점으로 구성된 트리는 언제나 n-1개의 간선을 가짐.
그래프 G의 신장 트리, Spanning Tree
: 그래프 G의 모든 정점들과 일부 간선으로 구성된 트리. 신장 트리는 사이클이 없어야하고, 모든 정점이 간선으로 연결되어 있어야 한다.
그래프 G의 최소 신장트리, MST, Minimum Spanning Tree
: 신장 트리 중에서도 간선의 합이 최소인 신장 트리.
최소 신장 트리를 만드는 알고리즘
- Prim 알고리즘
1) 시작 정점을 S 집합에 포함 시킨다. S 집합의 정점들과 인접한 정점들과 이어진 최소 간선을 찾는다.
2) 최소 간선과 이어진 정점을 S 집합에 포함시키고 인접한 정점들과 이어진 최소 간선을 찾는다.
3) 위의 과정을 모든 정점을 방문할 때까지 반복한다.
- Kruskal 알고리즘
1) 각 정점을 각각의 집합으로 둔다.
2) 가중치가 가장 적은 간선에 연결된 정점 두 개를 하나의 집합으로 합친다.
3) 다음으로 가장 적은 간선에 연결된 정점들을 하나의 집합으로 합친다.
3-1) 같은 집합 내의 정점끼리의 간선이라면 무시한다.
4) 정점 집합이 1개가 될 때까지 위의 내용을 반복한다.
TMI
최근 필요에 의해 MST를 구현해야 할 일이 생겼다. 접해본 경험이 있었지만 기억에서 희미해진 탓에 갈피조차 잡지 못했다. 그 사실이 너무 분해서 다시 공부해야겠다는 마음이 저절로 들었다.
그 시절 학습자료를 펼쳐보니, 노트 필기까지 열...심히 해가며 배웠더랬다. 하지만 그 당시에 이해하지 못한 것이 더 많았고 머리 속으로 우겨 넣기는 했다. 기억을 못하는 것을 보니 영 허튼 공부를 한 것 같기도 하고.
그래도 이 분한 기억 하나로 위의 내용들은 기억에 꽤 오래 남을 것 같다. 게다가 지난 포스팅에 알고리즘 과목을 듣고 힙정렬과 레드블랙트리 밖에 기억에 남지 않았다고 말한 적이 있는데 위 내용을 공부하며 힙정렬이 있었다는 것도 깨달았다. 이는 따로 포스팅 하지는 않겠지만 추가적인 학습을 통해 활용할 수 있도록 할 것이다.