전체 글 (54) 썸네일형 리스트형 강한 연결 요소 (Strongly Connected Component) 안녕하세요. 오늘은 줄여서 SCC 라고도 불리는 강한 연결 요소에 대해 알아보도록 하겠습니다. 사이클 유향 그래프에서 사이클을 찾는 알고리즘을 SCC 알고리즘 이라고 합니다. 하나의 SCC에 속하는 정점들은 서로에게 도달할 수 있는 것이 사이클 입니다. {1, 2, 5} , {3, 4, 8} , {6, 7} 은 각각 서로 다른 SCC를 이루고, 그 안에서 서로 도달가능한 집합입니다. 알고리즘 SCC를 찾는 알고리즘으로 2가지가 있습니다. 둘 다 알아보도록 하겠습니다. 코사라주 알고리즘 타잔 알고리즘 코사라주 알고리즘 시간, 공간적 비용이 타잔 알고리즘보다 크다는 단점 직관적이고 이해하기 쉽다는 장점 타잔 알고리즘보다 상대적으로 구현 난이도가 낮다는 장점 또한 존재합니다. 작동 과정 모든 노드가 방문될 때.. 최소 스패닝 트리 (Minimun Spanning Tree) 안녕하세요. 오늘은 최소 스패닝 트리에 대해 알아보겠습니다. 스패닝 트리 중 가장 가중치가 작은 트리 스패닝 트리가 무엇인지 먼저 알아야합니다. 그래프 그래프는 위 그림과 같이 노드와 간선으로 구성되는 자료구조입니다. 트리 그래프 그림을 보면 사이클이 존재합니다. 사이클이란, 어떤 노드에서 출발해서 간선을 최대 1번만 이용해서 자신 노드로 돌아오는 것을 말합니다. (3 - 4 - 5 - 3, 3 - 2 - 5 - 3 등) 트리는 사이클이 없는 acyclic graph 라고 합니다. 스패닝 트리 관련 유투브 영상을 찾아봤는데 영어로 아래와 같이 설명합니다. hit all vertices of graph G 그래프의 모든 노드에 도달하는 트리라는 뜻입니다. 트리이기 때문에 사이클이 없는 것을 확인할 수 있습.. A* algorithm 안녕하세요. 오늘은 A* algorithm (A star algorithm) 에 대해 알아보겠습니다. 최단 경로 휴리스틱 알고리즘 시작 정점 s에서 끝 정점 e 까지의 최단 경로를 근사화한 값을 구하기 위한 최단 경로 알고리즘 입니다. 휴리스틱 알고리즘 중 하나 입니다. 최단 경로를 찾는데 가장 유명한 알고리즘이 다익스트라 알고리즘 입니다. 다익스트라 알고리즘은 시작 정점에서 현재 정점까지 걸린 비용이 작은 것을 우선으로 탐색합니다. A* algorithm은 f cost가 작은 것을 우선으로 탐색합니다. f cost = g cost + h cost g cost = 시작 정점에서 현재 정점까지 걸린 비용 h cost = 현재 정점에서 끝 정점까지 걸릴 예상 비용 g cost가 다익스트라 알고리즘에서 우선시.. Topological Sort (위상 정렬) 안녕하세요. Topological Sort (위상 정렬)에 대해 알아보도록 하겠습니다. 간선의 방향에 따라 노드를 정렬 위상 정렬은 DAG (Directed Acyclic Graph) 에서 작동하는 알고리즘 입니다. Directed : 간선에 방향성이 있음 Acyclic : 순환 경로가 없는 그래프 => DAG란, 간선에 방향성이 있고 사이클이 존재하지 않는 그래프 노드를 간선의 방향을 거스르지 않고 정렬하는 알고리즘 입니다. 간선 (u -> v)가 있다고 가정하면, 노드를 정렬했을 때 u가 v보다 먼저 나타나야 합니다. 위의 [그림 1]에서 위상 정렬을 하면 아래와 같이 나올 수 있습니다. (위상 정렬은 정답이 여러 개가 나올 수 있습니다.) 1 -> 2 -> 3 -> 4 -> 5 2 -> 1 -> 3.. Disjoint-set 안녕하세요. Disjoint-set에 대해 알아보도록 하겠습니다. 서로소 집합, 분리 집합 Disjoint-set은 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합입니다. 서로 다른 원소들이 같은 집합에 있는지, 혹은 다른 집합에 있는지를 판별할 수 있습니다. 트리 형태로 관리하며, 연산이 union과 find 두 가지가 있기에 union-find 라고도 불립니다. 과정 어떤 알고리즘을 거쳐서 disjoint-set이 같은 집합에 속하는지를 판별할 수 있는지 알아보겠습니다. 1) parent 배열 준비 parent 배열이란, parent(x)의 값은 x의 부모 노드를 의미합니다. 처음에는 모든 노드가 자기 자신이 루트 노드인 트리이므로 아래와 같이 설정해줍니다. 2) union 연산 union .. 네이버 블로그 기존에 작성하던 네이버 블로그에 이어서 티스토리에도 블로그를 작성합니다. 감사합니다. https://blog.naver.com/kdr06006 알고리즘 블로그 : 네이버 블로그 IT 블로그 경북대학교 모바일공학과 blog.naver.com 이전 1 ··· 4 5 6 7 다음
