NEMOSTAR5

강한 결합 요소란 그래프 안에서 '강하게 결합된 정점 집합'을 의미한다. 서로 긴밀하게 연결되어 있다고 하여 강한 결합 요소라고 말한다. SCC는 '같은 SCC에 속하는 두 정점은 서로 도달이 가능하다'라는 특징이 있다. 총 4개의 집합이 존재하는데 각 집합에 있는 정점끼리는 서로에게 도달할 수 있는 것을 알 수 있다. 사이클이 발생하는 경우 무조건 SCC에 해당한다는 특징이 있다. 그래서 위와 같이 방향 그래프일 때만 의미가 있다. 무향 그래프라면 그 그래프 전체는 무조건 SCC이기 때문이다. SCC를 추출하는 대표적인 알고리즘은 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다. 일반적으로 코사라주 알고리즘이 더 구현이 쉽지만 타잔 알..

위상 정렬은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 순서가 정해져있는 작업의 대표적인 예시는 다음과 같다. 그래프의 흐름은 사실 '조건'으로 해석할 수 있다. 위와 같이 여러개의 순서가 정해져있을 때 조건에 부합하는 일직선의 순서를 찾아보자. 위상 정렬 : 1 -> 5 -> 2 -> 3-> 4 -> 6-> 7 위와 같이 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '7'까지 갈 수 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 이것은 사이클이 발생하지 않는 방향 그래프라는 의미이다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 ..

'모든 정점에서 '모든정점'으로의 최단 경로르 구하고 싶다면 플로이드 와샬 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거져가는 정점'을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 0 5 무한 8 7 0 9 무한 2 무한 0 4 무한 무한 3 0 위 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. X에서 Y로 가는 최소 비용 VS X에서 1로 가는 비용 + 1에서 Y로 가는 비용 노드 1을 거쳐가는 경우 0 5 무한 8 7 0 9 15 2 7 0 4 무한 무한 3 0 노드 2를 거치는 경우 0 5 14 8 7 0 9 15 2 7 0 4 무한 무한 3 0 위와 같이 노드 3과 노드 4에 반복해주면 된다..

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러개의 최단 거리로 이루어져있기 때문이다' 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다시 말해 다익스트라 알고리즘은 '현재까지 알고 있던 최단 경로를 계속해서 갱신'합니다. 1. 출발 노드를 설정합니다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다. 3. ..