Algorithm/Algorithm Study 썸네일형 리스트형 사이클 찾기: DFS 유향 그래프에서 사이클이 있는지 판단하고, 사이클에 포함되는 노드의 개수가 몇 개인지 세는 알고리즘으로 백준 알고리즘 저지의 9466번: 텀 프로젝트 문제가 이에 해당한다. 9466번: 텀 프로젝트 - Baekjoon Online Judge https://www.acmicpc.net/problem/9466 구글링만 해봐도 해당 문제에 대한 많은 풀이가 존재하지만, 아무래도 이런 로직은 내 코드로 정리하는게 제일 이해도 잘가고 나중에 봐도 이해하기 쉬울 것 같아서 풀이 위주로 정리해봤다. 문제에서는 프로젝트를 함께하고 싶은 학생을 선택하는 것이 나오는데 선택은 한명씩 하게 되있으므로, 각 노드에서 나가는 간선은 하나씩이라는 것을 알 수 있다. 주의해야할 것은 자기 자신도 선택할 수 있으므로 나가는 간선이 .. 강한 연결 요소 (SCC: Strongly Connected Component) 강한 연결 요소는 그래프 내의 노드간 연결구조 중 한가지이다. 간단히 설명하자면 그래프 내에서 노드간 상호이동이 가능한 상황이면 그 노드들은 강한 연결 요소 관계에 놓여있다고 말할 수 있고, 만일 일방으로만 이동이 가능한 경우나 이동이 불가능한 경우는 강한 연결 요소가 아니라고 할 수 있다. 예를 들어 방향성 있는 간선과 노드가 주어졌을 때, 이들이 연결되어 하나의 그래프를 이루고 있고, A라는 노드에서 B라는 노드로 이동이 가능하고 B라는 노드에서 A 노드로 이동이 가능하다면, 두 노드는 SCC를 이룬다고 할 수 있다. 좀 더 확장하여 세 개나 그 이상의 노드들의 연결관계로도 설명할 수 있다. 만일 A, B, C 세 개의 노드가 있을 때, A 노드는 B 노드로, B 노드는 C 노드로, C 노드는 A 노.. 1854번: K번째 최단경로 찾기 - Baekjoon Online Judge K번째 최단경로 찾기는 최단경로 알고리즘 중에서 가장 기본적이고, 가장 널리 알려진 다익스트라(Dijkstra) 알고리즘의 응용 문제이다. 다익스트라 알고리즘에 대해 간단히 알아보자면 다익스트라 알고리즘은 노드와 간선으로 이루어진 그래프가 있을 때, 하나의 노드를 출발점으로 하여 목표 노드까지 도달하는데 드는 비용을 최소화시키는 알고리즘이다. 알고리즘이 갖는 의미가 비교적 단순명료하여 이해하기는 쉬운데 처음 소스로 구현하자면 어떻게 해야할지 방향 잡기가 힘들다. 간단히 다익스트라 알고리즘 푸는 법을 설명하자면, 처음 시작점에서부터 갈 수 있는 노드들을 탐색하여, 해당 노드까지 가는데 드는 비용이 최소가 되도록 업데이트 해준다. 그리고 비용을 줄여서 이동 가능한 노드들이 우리가 도착 목표로 하고 있는 노드.. 11400번: 단절선 - Baekjoon Online Judge 단절선 알고리즘은 완전 그래프에서 어떤 간선을 제거하였을 때, 그래프가 두 개 이상의 영역으로 나누어지는지 알아내기 위한 알고리즘이다. 문제를 단절선 알고리즘으로 규정짓기 위해서는 몇 가지 조건이 주어져야 한다. 첫째 완전 그래프여야 한다. 완전 그래프는 모든 노드가 간선으로 연결되어 어느 한 노드도 빼놓지 않고 연결이 되어 있는 경우를 의미한다. 완전 그래프의 정의 https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84_%EA%B7%B8%EB%9E%98%ED%94%84 둘째 한번에 하나의 간선만 끊을 수 있다. 동시에 여러 간선을 끊는다던가 한번 끊어진 간선은 계속 끊어진 상태로 있다던가 하는게 아니라 연결되어 있는 상태에서 한번에 하나씩 끊어져야 한다. 단절선 알고리즘.. 이전 1 2 다음