알고리즘 공부 8일차

 오늘은 이론 마지막 단원인 그래프 이론을 마무리해 보았다. 그래프 이론은 앞에서 배웠던 DFS/BFS/최단 경로 알고리즘을 포함하는 큰 의미를 갖는다. 이것들 말고도 그래프 이론에 많이 쓰이는 알고리즘은 많은데 오늘은 크루스칼 알고리즘, 위상정렬 알고리즘에 대해서 공부해보겠다. 

 먼저 크루스칼 알고리즘이다. 이것을 설명하기 앞서 서로소 집합 자료구조에 대해서 알아야한다. 이 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 작동하는 함수로는 대표적으로 union(합집합) , find(속한 집합 찾기) 가 있다. 서로소 집합 자료구조는 트리 자료구조를 이용해서 집합을 표현한다. 즉, 루트노드와 부모노드가 존재하는데 그것을 이용해서 union과 find를 구현할 수 있다. 어떠한 정점 A,B를 union하고자 할 때 과정은 다음과 같다.

1. A와 B의 루트 노드 A',B'를 각각 찾는다
2. A'를 B'의 부모 노드로 설정한다.(우선 순위에 따라 바뀔 수 있다.)
3. 모든 연산을 처리할 때 까지 1,2를 반복한다.

  이렇게 구한 부모노드를 노드 번호와 함께 2차원 행렬 형태로 저장한다. 하지만 이 방법에도 단점이 있다. 바로 루트노드를 바로 파악할 수 없어서 find 함수를 사용할 때 최악의 경우 시간복잡도가 O(V)로 작동한다는 것이다.(V는 노드의 갯수)

그래서 이것을 개선시킨 경로 압축 기법이라는 것이 있다. 이것은 부모노드를 업데이트 할 때 재귀함수를 사용해서 바로 루트노드로 업데이트 시켜주는 것이다. 그러면 find를 사용했을 때 바로 루트 노드를 찾을 수 있고 어디에 속해있는지 바로 확인할 수 있다. 이 서로소 집합 자료구조의 사용은 무방향 그래프에서의 사이클을 판별할 때 유용하게 사용할 수 있다. 이것은 '어떤 간선이 있을 때 두 정점의 루트 노드가 같다면 사이클 발생' 이라는 간단한 아이디어로 구현할 수 있다.

 또 알아야할 내용이 있다. 바로 신장트리 알고리즘이다. 신장트리는 '하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프' 를 의미 한다. 즉 모든 노드가 연결되면서 사이클이 존재하지 않는 트리구조를 찾는 것이다. 

 크루스칼 알고리즘은 방금 설명한 신장트리 중 최소비용 신장트리를 찾는데 쓰이는 알고리즘이다. 아이디어는 간단하다. 가장 비용이 적게드는 간선들을 먼저 추가하고, 만약 사이클이 생긴다면 제외하는 그리디 알고리즘의 방식으로 진행된다. 순서를 작성하자면 이렇게 쓸 수 있다.

1. 간선데이터를 오름차순으로 정리한다.
2. 간선을 하나씩 확인해 사이클이 발생하는지 확인한다. 생기지 않으면 최소 신장 트리에 추가한다. 생긴다면 추가하지 않는다.
3. 모든 간선에 대해 진행한다.

 이 알고리즘은 정렬 후 모든 간선에 대해 진행하므로 O(ElogE)의 시간복잡도를 갖는다.(E는 간선의 수) 

 

다음은 위상정렬 알고리즘이다. 이것은 정렬 알고리즘의 일종으로 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 좀 더 이론적으로 설명하자면, 위상정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이다. 쉬운 예시 중 하나는 우리가 듣는 전공 수업의 커리큘럼을 생각하면 편하다. 각 강의별로 선수 과목이 존재하고 그 방향은 역이 되는 경우가 없다. 이 위상 정렬 알고리즘은 다음과 같이 진행된다.

1. 진입차수(들어오는 간선)가 0인 노드를 큐에 넣는다.
2. 큐가 빌때까지 다음을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0인 노드를 큐에 넣기

 만약 원소가 V번(노드의 갯수) 출력되기 전에 큐가 비게 되면 사이클이 발생했다는 것을 알 수 있다. 왜냐하면 V번 출력되기 전에 큐가 비었다는 것은 진입 차수가 0이 되지 않는 노드가 존재한다는 것으로, 서로가 서로에게 진입하는 사이클이 존재한다는 것이기 때문이다. 

 

  오늘은 책의 예제를 다 풀지 못했다. 생각보다 구현에 시간을 많이 잡아먹었기 때문이다. 확실히 앞에 단원들 보다 시간이 많이 드는게 느껴진다. 아직 지식과 구현 실력이 부족함을 느끼고 더 열심히 해야겠다는 생각이 든다. 아 그리고 최근에 내가 빠진게 있다. 바로 Chat-GPT이다. 이것은 언어모델로 GPT는 Generative Pretrained Transformer의 약자이다. 여기에 질문을 하면 생각보다 괜찮은 대답이 나오는데 요즘은 구글이 아닌 여기에 질문을 해보곤 한다. 엄청 구체적인 것도 있고 내가 한 질문에 대한 방향성도 괜찮게 나오기 때문이다. 그래서 오늘은 다른 사람들의 사용도 궁금해서 오픈카톡에 들어가 보았다. 거기서는 벌써 이것을 이용해 앱을 개발한 사람, 논문 참고자료를 찾을 때 사용하는 사람 등 굉장히 많은 분야에서 사용하는 것을 볼 수 있었다. 그것을 보고 이 Chat-GPT는 어디까지 쓰일까 궁금해지기도 했고, 이런 AI는 어떤 방식으로 개발이 되었을까? 를 계속 생각해 보았다. 나도 2학기 딥러닝 수업에서 LSTM을 이용한 언어모델을 보긴 했지만 그것과는 차원이 다른 모델이어서 내가 아직 자세히 알지는 못하는 Transformer를 사용했나라는 생각이 들었다. 내일부터는 코딩테스트의 이론공부는 끝났으니 딥러닝 공부를 다시 시작해야 할 것 같다.