DAMPER's blog

무향 그래프에서 단절점(Cut vertex) 찾기 단절점이란 해당 정점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점을 말합니다. 아래 그림을 예시로 들었을 때, 1번 정점과 인접한 간선을 모두 지웠을 때, 0번 정점이 떨어져나가 하나의 컴포넌트가 됩니다. 그러므로 1번 정점은 단절점입니다. 마찬가지 이유로 3번, 5번 정점도 단절점입니다. 단절점을 찾는 방법으로 여러가지가 있지만 DFS 탐색 1회만으로 그래프의 모든 단절점을 찾을 수 있습니다. 먼저 아무 정점으로부터 DFS 트리를 만듭니다. 이 때 임의의 정점 u와 연결된 정점들은 모두 u의 조상이거나 자손입니다. 만약 u와 인접한 간선들을 모두 지웠을 때 그래프가 나눠지지 않는 경우는 u의 자손들이 u의 선조와 역..

한 시작점에서 다른 모든 정점까지의 최단 거리(간선 가중치의 합이 최소)를 구하는 알고리즘 중 가장 유용한 알고리즘으로 다익스트라 알고리즘이 있다. 하지만 다익스트라 알고리즘은 음수 간선이 있는 그래프의 경우, 그 정당성이 보장되지 않아 벨만-포드 알고리즘을 사용해야한다. 벨만-포드 알고리즘은 음수 간선이 있는 최단 경로를 찾을 뿐만 아니라, 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우 알려주기도 한다. 벨만-포드 알고리즘 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히(?) 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 수행 과정에서 각 정점까지 최단 거리의 상한을 담은 배열 upper[]을 유지한다. 이 값은 알고리즘이 진..

모든 정점이 짝수점(정점의 차수가 짝수인 점)이고, 모든 간선이 하나의 컴포넌트에 포함되어 있다고 가정하자. 함수 findRandomCircuit(u) : 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 재귀적으로 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료. 함수를 실행하면 여러 부분 서킷이 생성될텐데, 전체를 포함하는 하나의 서킷을 원하므로 모든 부분 서킷들을 합쳐야한다. 부분 서킷이 생긴다는 말은 무슨 말일까? 어떤 정점에서부터 출발하는 간선이 하나가 아닌 여러개일 수 있는데, 이때 서킷의 정의에 따라 출발하는 간선만큼 해당 정점으로 오는 간선이 존재해야한다. -> 그만큼 부분서킷이 생긴다. 해당 정점에서 나가는 간선이 2개 존재한다면, 2개의 부분 서킷이 생긴다. 이..

출처 : algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 algospot.com 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서..

오일러 서킷(Eulerian circuit) : 그래프의 모든 간선을 정확히 한번씩 지나서 시작점으로 돌아오는 경로. 오일러 경로(Eulerian path) : 그래프의 모든 간선을 정확히 한번씩 지나는 경로. 시작점과 도착점이 다르다. 무향 그래프에서 오일러 서킷을 찾으려면? 먼저 오일러 서킷의 존재 여부를 확인한다. 1. 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우는 오일러 서킷이 존재할 수 없다. 그래프의 정점이 둘 이상의 컴포넌트로 쪼개져 있어도, 간선들이 한 컴포넌트에 있다면 오일러 서킷은 존재한다. 그래프의 모든 '간선'을 지나 시작점으로 되돌아오기만 하면 되기 때문. 2. 도착점에 인접한 모든 간선은 이미 지나온 상황이어야한다. 3. 도착점에 인접한 간선의 수는 항상 짝수이다..

algospot.com/judge/problem/read/DICTIONARY algospot.com :: DICTIONARY 고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 algospot.com 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른..