알고리즘 공부[6] 그래프 절단점과 SCC
안녕하세요. 오늘은 그래프의 절단점과 SCC(Strongly Connected Component)에 대해 알아보겠습니다. ContentsCut vertex(절단점 찾기)SCC(Strongly Connected Component)Kosaraju algorithmTarjan algorithm Cut Vertex(절단점)그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다.이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다.느낌상에는 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다.그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니..
안녕하세요. 오늘은 그래프의 간선에 대한 내용과 싸이클 검출 방법에 대해 알아보겠습니다. Contents 간선의 분류 싸이클 존재 여부의 확인 간선의 분류간선 구분에 대한 정확한 정의를 살펴봅시다. DFS를 수행할 때 방문하는 간선들을 모아 만든 tree를 DFS spanning tree라고 합니다. 아래와 같은 그래프가 있고, DFS를 1번 정점으로 부터 정점 번호가 작은 순으로 선택한다고 합시다. 그렇다면 DFS Spanning tree는 아래 그림에서 실선에 해당하는 트리를 말합니다. (Root는 1번 정점이 되겠죠) 여기서 실선으로 이루어진, DFS spanning tree를 이루는 간선을 tree edge(트리 간선)이라고 합니다. forward edge(순방향 간선)이란 트리간선이 아닌데, 트..
알고리즘 공부[4] 한붓그리기(Eulerian circuit)
안녕하세요. 오늘은 한붓그리기, 오일러 서킷이라 부르는 문제들에 대해 다루어 보겠습니다. ContentsEulerian cirtuit(오일러 서킷)Eulerian trail(오일러 트레일) Eulerian Circuit(오일러 서킷)오일러 서킷이라는 것은 우리들에게 한붓그리기 문제로 더 알려져 있습니다. 오일러 서킷그래프가 주어졌을 때 그래프의 한 시작점으로부터 모든 간선을 한번씩만 지나 다시 시작점으로 돌아오는 경로를 말합니다.이러한 경로가 있으려면 어떠한 조건을 만족해야 할까요?가장 많이 사용되고 있는 방법으로는 단순하게 정점의 degree를 사용하는 것입니다.degree라는 것은 위상정렬 할 때 잠시 살펴보았죠? 그 때는 indegree를 이용하였고, 여기서 degree라는 것은 정점에 연결되어 있..
알고리즘 공부[3] Topological sort(위상정렬) (C++)
안녕하세요. 오늘은 그래프를 활용한 문제에서 등장하는 위상정렬에 대해서 알아보겠습니다. ContentsDAG(Directed Acyclic graph)Topological sort란?위상정렬의 구현방식(1)-indegree위상정렬의 구현방식(2)-DFS DAG(Directed Acyclic Graph)우선 위상정렬을 공부하기 전에 DAG에 대해서 알아봅시다. Directed Acyclic graph란 말 그대로 간선에 방향이 있고, 싸이클이 없는 그래프를 말합니다.Directed Graph에서 방향을 가지고 있는 간선들의 sequence에 대해 시작점과 끝점이 같아지는 sequence가 있다면 싸이클이 있다고 합니다. DAG는 이런 싸이클이 없는 유향그래프이죠.이전의 그래프의 정의와 함께 말씀드렸듯 DA..
알고리즘 공부[2] DFS(깊이 우선 탐색) (C++)
안녕하세요. 오늘은 그래프에 대해서 가장 많이 등장하는 DFS에 관하여 알아보겠습니다.DFS는 매년 여러 곳의 입사시험 및 프로그래밍 대회에서 등장합니다. ContentsDFS(Depth-First search)DFS구현(1) RecursiveDFS구현(2) StackDFS의 time complexity DFS(Depth-First Search)DFS란 무엇일까요? 한국말로 해석해보면 깊이 우선 탐색이라는 말이 됩니다. 그래프에서 특정 정점을 찾을 때 그래프의 깊이를 우선적으로 탐색한다는 말이죠. 이렇게 말하면 솔직히 감이 잘 안옵니다.예를 봅시다! https://steemitimages.com/0x0/https://janav.files.wordpress.com/2014/01/dfs-bfs-differe..
알고리즘 공부[1] 그래프 (C++)
안녕하세요. 오늘은 그래프에 관하여 알아보겠습니다.그래프는 여러 알고리즘 문제에서 등장하며, 관련된 알고리즘 또한 많기 때문에 잘 알고 있는 것이 중요하다고 생각합니다. Contents그래프그래프의 종류그래프의 경로그래프의 표현 그래프그래프는 vertex(정점)들의 집합 V와 edge(간선)들의 집합인 E로 구성된 자료구조입니다.그렇다면 우리는 그래프를 간략하게로 표현할 수가 있죠. 이러한 표현에서 눈치를 채신 분들도 있겠지만!그래프를 정의하는데 있어서 간선의 길이 그리고 정점의 위치는 신경쓰지 않습니다.정점이 어디에 있든, 간선이 길이와 상관 없이 각 정점과 정점을 이어주는 간선의 유무로만 그래프를 정의합니다. 그래프의 종류그래프의 종류에는 여러가지가 있습니다. 아래 나타난 것 말고도 여러 기준에 따라..