Topology, Network Topology
포스트 난이도: HOO_Middle
[Notice] 포스트 난이도에 대한 설명
안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다
whoishoo.tistory.com
# Topology와 Network Topology
알고리즘 공부를 하다 보면 자주 마주치는 것이 바로 Topology, 한국말로는 위상수학이다. (필자는 위상 수학보다는 토폴로지가 더 와닿는다.) CS에서 배우는 알고리즘 자체가 새롭게 나온 학문이나 지식이 아닌 기존에 있는 지식을 기반으로 만들어진다. 수학적 개념에서 토폴로지는 연속성과 수렴성을 다루는 기하학의 학문 중 하나이다. CS(Computer Science)에서의 토폴로지는 연속성과 수렴성을 고려하는 노드 간의 연결성을 나타내는 알고리즘을 의미한다.
따라서 CS에서는 토폴로지(Topology)라고도 하지만 네트워크 토폴로지(Network Topology)라고도 한다. 한마디로 CS 말하는 토폴로지와 수학적 토폴로지는 다른 것을 의미하며, CS에서는 토폴로지 또는 네트워크 토폴로지라고 부른다.
# 네트워크 토폴로지
CS에서 의미하는 네트워크 토폴로지 또한 연속성과 수렴성을 나타내는데, 연결되는 노드끼리 이러한 특징을 나타낸다.
위의 그림에서 보듯이 노드끼리 연속적으로 연결되어 있고 결과적으로 하나의 노드로 수렴되는 걸 알 수 있다. 이와 같은 형태를 CS에서는 토폴로지라고 하며, 위의 예제는 머신러닝(Machine learning)에서 사용되는 기초 딥러닝(Basci deep learning) 토폴로지(Topology) 예시 그림이다. 토폴로지의 형태는 다양하며, 토폴로지 형태의 따라 알고리즘 또한 달라진다. 대표적인 토폴로지 형태로는 일렬로 나타낸 라인 토폴로지(Line topology), 버스 토폴로지(Bus topology), 트리 토폴로지(Tree topology), 링 토폴로지(Ring topology) 등이 있다. 또한 Internet of Things와 같이 사물 인터넷에서 사용되는 Mesh network 방식 또한 Mesh topology를 적용하고 있다. 이처럼 토폴로지는 시각적으로 연속성을 가진 노드들을 의미하며 코드에서는 연속성을 가진 연결된 노드들을 의미한다.
# Topological sort
토폴로지(Topology) 얘기가 나온 김에 토폴로지라는 단어가 포함된 정렬 알고리즘 하나를 간단하게 살펴보자면, Topological sort라는 정렬 알고리즘이 있다. Topological sort라는 단어의 의미를 통해 해당 알고리즘의 성격을 유추해볼 수 있다. 우선 Topological이라는 것은 토폴로지가 연속성을 가진 노드라는 의미를 가지고 있다고 유추할 수 있다. 다음으로 sort라는 단어는 정렬이라는 의미를 가지고 있기에 정렬 알고리즘에 해당한다는 걸 예측할 수 있다. 결과적으로 Topological sort 알고리즘은 연속성을 가진 노드의 정렬 알고리즘이라고 유추할 수 있다.
거두절미하고 Topological sort algorithm은 첫번째 노드와 연결되어 있는 인접한 노드들부터 순서대로 작동하는 특징을 가진다. 위의 예제 그림을 살펴보면 1이라는 노드 다음에 2와 3이 연결되어 있는 인접한 노드이기에 작동하는 4번 노드보다 우선적으로 선택된다. 하지만 여기서 유의할 점이 위와 같이 2개의 노드가 Topological sort에서 같은 조건에 충족된다면, 작업이 수행되는 순서가 1-2-3-4일 수도 있지만 1-3-2-4가 될 수도 있다. 따라서 Topological sort algorithm에서는 이 점을 유의해야 한다.
# CS에서의 Topology
CS에서 알고리즘 자체가 수행되는 작업의 순서를 의미한다. 그렇다보니 사실상 모든 프로그래밍은 알고리즘대로 작동이 되며, 토폴로지로 구성이 되어 있다고 볼 수 있다. 수학에서 사용되는 토폴로지와 컴퓨터에서 사용되는 토폴로지는 다르지만 연속성과 수렴성이라는 특징에서 비슷하다고 볼 수 있다. CS를 공부하는데 있어 토폴로지가 언급된다면 두려워하지 말고 노드가 연결되는 모습과 연속성을 생각하면 된다. 토폴로지는 우리 뇌 안의 시냅스 간의 관계에서도 존재하고 있으니 친하게 지내도록 하자.
'Computer Science > Algorithms' 카테고리의 다른 글
| [Deep Learning Algorithms] Adam Optimization Algorithm(아담 최적화 알고리즘) (0) | 2022.07.31 |
|---|---|
| [Deep Learning Algorithms] SGD(Stochastic Gradient Descent), 확률적 경사 하강법 (0) | 2022.07.29 |
| [알고리즘] Machine Learning Algorithm: Random Forest (0) | 2022.06.09 |
| [알고리즘] Machine Learning Algorithm: Support Vector Machine(SVM) (0) | 2022.06.01 |
| [알고리즘] K-nearest Neighbors Algorithm(K-NN): K-최근접 이웃 알고리즘 (0) | 2022.05.29 |
댓글