3주 차는 그래프 자료구조에 대해 공부하는 시간이었다. 사실 문제의 난이도 자체는 저번주보다 쉬웠으나, 자료구조에 대한 이해가 없다면 처음부터 공부해야 했기에 시간이 많이 걸렸을 것이다.
BFS / DFS
그래프를 탐색하는 대표적인 방식이다. 너무 전형적인 패턴이라서 풀어봐서 눈 감고도 외워서 칠 수 있을 정도다..
하지만 한 번씩 이 탐색을 꼬아서 내는 문제가 있는데, 처음 보는 패턴의 문제들이 많아서 난이도가 확 뛰는 느낌이었다.
Union-Find / 최소 스패닝 트리
학부 때 배웠던 거지만 기억이 안 나서 다시 공부했다.
유니온 파인드는 현재 노드의 집합의 루트 노드를 구할 수 있다. 이로 인해 최소 스패닝 트리를 만들 때 사이클이 생기는지 아닌지 검사할 수 있다.
최소 스패닝 트리는 그래프의 노드를 모두 연결하면서 그 에지들의 가중치가 최소가 되는 트리이다.
최소 스패닝 트리가 어디서 사용될까 했는데.. 아마 세계를 모두 연결해야 하는 해저 케이블이나 모든 신호국을 이어야 하는 전화선을 설치할 때 쓰이지 않을까?
최소 스패닝 트리를 구현하는 방식도 여러 가지가 있는데, Kruskal, Prim, Sollin의 알고리즘이 있다.
처음에는 Prim의 알고리즘을 사용했다가 시간초과로 낭패를 봤다.
그래서 다시 유니온 파인드를 이용한 Kruskal의 알고리즘을 사용해 문제를 통과했다.
전형적인 유니온 파인드 문제다. 집합이 몇 개인지만 확인하면 끝.
유니온 파인드를 사용할 때 주의할 점은 각 노드의 부모가 누구인지 확인할 수 있는 게 아니라 속한 집합의 루트 노드가 누구인지 알 수 있다는 것을 확실히 구별하는 것이다.
위상 정렬 / 임계 경로
위상 정렬은 어떤 작업을 할 때, 먼저 해야 할 작업이 있는 경우 그 순서를 정하는 방식이라고 한다.
예를 들어 알고리즘을 수강하려면, C언어와 자료구조를 선수과목으로 수강해야 하기 때문에 어느 것을 먼저 수강할지 정하는 것이다. 이 특성상 C언어와 자료구조 사이에 관계가 없다면 두 과목 중 아무것이나 먼저 수강해도 되기 때문에 전체적인 순서는 일정하지 않다.
위상정렬을 사용하려면 사이클이 없는 방향성 그래프여야만 한다.
위상 정렬을 수행하려면 먼저 진입차수와 진출차수에 대해 알고 있어야 한다.
진입차수는 노드로 들어오는 에지의 수, 진출차수는 노드에서 나가는 에지의 수이다,
예를 들어 1 -> 3, 2 -> 3, 3 -> 4, 3 -> 5 라고 한다면, 1과 2의 진입 차수는 0, 진출 차수는 1이고, 3의 진입 차수와 진출 차수는 2이다.
위상 정렬을 수행하는 과정을 대략적으로 적어보면 다음과 같다.
1. 진입차수가 0인 노드들을 큐에 집어넣는다
2. 큐에서 노드를 꺼낸다. 이때 이 노드를 출력하거나 배열에 추가하는 등 순서를 출력할 수 있다
3. 꺼낸 노드의 진출 에지들을 없앤다
4. 이 과정에서 진입차수가 0이 된 노드들을 다시 큐에 집어넣는다
5. 위의 과정을 큐가 빌 때까지 반복한다.
사실 위상 정렬 자체는 별 거 없다.
문제는 이를 이용한 임계 경로 문제가 조금 어렵다는 것이다.
https://verdant-bathtub-bae.notion.site/1c57bb7778c980c6b3c0c0aa873802cd?pvs=4
임계 경로 | Notion
방향 그래프에서 특정 노드부터 어떤 노드까지 도달하는데 가장 오래 걸리는 경로
verdant-bathtub-bae.notion.site
노션에 정리해 두었다.
위 문제들이 위상 정렬 관련 문제들인데... 그래프 수정은 아직 잘 이해가 가진 않는다. 나머지는 다 할만한 듯!
다익스트라 / 플로이드-워셜
위의 임계 경로는 각 노드에 대한 최장경로를 찾았다면 다익스트라는 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
다익스트라 알고리즘의 수행 과정을 대략적으로 적으면 다음과 같다.
1. 시작 노드를 최소 힙에 집어넣는다. 이때의 가중치는 0이다 (당연히 시작 지점이니까)
2. 힙에서 노드와 가중치를 꺼낸다
3. 꺼낸 가중치 + 꺼낸 노드와 연결된 노드와의 가중치가 기존의 거리보다 가깝다면 갱신하고, 연결된 노드와 더해진 가중치를 힙에 넣는다.
4. 힙이 빌 때까지 위 과정을 반복한다.
다익스트라 알고리즘은 음의 가중치가 있을 때 최단경로를 보장하지 못한다는 단점이 있다. 이를 보완하기 위한 것이 벨만-포드 알고리즘이라고 하는데... 현실 세계에서 음의 가중치가 잘 있지 않으니 크게 신경 쓰지 않아도 될 듯하다.
또한, 다익스트라는 하나의 노드에서의 최단 경로를 구하는데, 플로이드-워셜 알고리즘을 사용하면 모든 노드의 다른 모든 노드까지의 최단 경로를 구할 수 있다.
B-Tree
데이터베이스에서 방대한 양의 데이터를 저장하기 위한 자료구조이다.
https://verdant-bathtub-bae.notion.site/B-1c77bb7778c98010b294da2780d1f4e5?pvs=4
B 트리 | Notion
B트리는 하나의 노드에 많은 수의 정보 저장 가능
verdant-bathtub-bae.notion.site
위 페이지에서 B-Tree의 삽입 / 삭제 과정도 영상으로 찍어 올려놨다.
트라이
문자 검색 알고리즘으로, 우리가 IDE나 검색 엔진에서 큰 도움을 받고 있는 자동완성에서 이 알고리즘이 사용된다고 한다.
다만, 다음 자식 노드 배열의 포인터도 모두 갖고 있어야 해서 그 크기가 매우 클 것 같아 이를 어디에 저장해야 할지가 궁금했는데, 트리 전용 데이터베이스나 key-value 저장소에 이를 저장해 두고 자주 쓰이는 정보만 캐싱해서 사용한다고 한다.
퀴즈와 시험
이번 퀴즈는 스택으로 dfs를 구현하라는 문제가 나와서 잠깐 당황했다... 문제 하나가 추상화의 개념을 묻는 문제였는데 외우지 않아서 틀렸다 ㅠ
시험은 주차 시험 중 가장 쉬웠던 것 같다. 과장 안보태고 문제당 10분도 안걸린것 같은데...
사실 정글러들의 실력이 천차만별이라 그 평균을 보고 문제를 내주신것 같긴 하다