알고리즘/기법 (6) 썸네일형 리스트형 위상 정렬(topological sorting) 유향그래프에서 각 정점들이 한 방향으로 나열된 형태 정점 u와 v가 u -> v 순서일 때, 어떠한 경우에도 u -> v 순서가 유지된다. 이러한 특성 때문에 사이클이 존재하지 않는다. 주로 다음과 같은 곳에 사용된다. 1. 소프트웨어 공학에서 일정 계획 방법론인 PERT나 CPM 2. 스킬트리, 선수과목 같은 사전 작업같은 것이 필요한 작업들 물론, BFS/DFS만으로 풀 수 있지만 위상 정렬을 알면 더 쉽게 풀 수 있다. 위상 정렬의 수행 과정 2개 배열이 필요하다. 해당 정점에 연결된 간선의 수를 담는 배열 A 정점별로 간선 자료구조를 담는 배열 먼저, 자신을 가리키는 간선이 없는 정점들을 찾는다. 해당 정점에서 출발하는 간선이 있으면 지움 (배열 A의 카운트를 1 줄인다.) 만약, 해당 간선의 도.. 최소 스패닝 트리(MST, Minimum spanning tree) 최소 신장 트리라고도 한다. 그래프에서 최소 스패닝 트리를 만들기 위해선 다음 조건을 만족해야 한다. 1. 모든 정점은 연결돼있다. 2. 사이클이 없어야 한다.(트리 형태이기 때문) 3. 최소 가중치를 가진 무방향 간선들로만 연결돼야 한다. (간선의 개수는 정점의 개수 - 1 개) 즉, 모든 정점을 사이클 없이 최소한의 비용으로 연결해야 한다. 그림으로 올바른 형태와 잘못된 형태를 보면 다음과 같다. 모든 정점을 최소한의 비용으로 연결한단 특성 때문에 통신, 운송 네트워크 등 공급과 관련된 연결망을 구축하는 문제들이 많다. 스패닝 트리를 만드는 알고리즘은 크게 2가지가 있다. 각각 유리한 점이 있고, 특정 풀이를 쓰도록 강요하는 문제는 많이 없기 때문에 편한걸 쓰면 된다. 1. 크루스칼 알고리즘 가중치가.. BFS(breadth first search) 그래프 순회 방법 중 하나 DFS가 깊이(depth)라면, BFS는 너비(breadth) 우선 탐색이기 때문에 정점에서 인접한 정점들을 우선 탐색한다. 주로 큐를 이용해 구현한다. 우선순위 큐로 구현한다면 다익스트라 알고리즘이 된다. BFS 진행은 3단계로 나눌 수 있다. 1. 시작 index를 정한다. 2. 정점의 이동반경을 확인한다. 3. 방문하지 않은 정점이 있다면, 탐색 큐에 넣어준다. BFS 탐색 순서는 다음과 같다. 시작 index는 1이라 가정한다. 인접 리스트에서 BFS 코드 더보기 import java.io.*; import java.util.*; class Main { static ArrayList[] graph = new ArrayList[10]; public static void m.. DFS(depth first search) 그래프 순회 방법 중 한가지 BFS가 너비(breadth)라면, DFS는 깊이(depth) 우선 탐색이기 때문에 정점에서 가장 멀리 떨어진 곳을 먼저 탐색한다. 주로 재귀를 통해 구현하기 때문에 백트래킹과 유사점을 갖는다. DFS 진행은 4단계로 나눌 수 있다. 1. 현재 정점과 인접한 간선들을 본다. 2. 해당 간선으로 통하는 정점을 방문했는지 본다. 3. 방문하지 않았으면 방문한다. 4. 막혔으면 되돌아간다. 다음 그래프를 DFS로 탐색하는 순서다. 왼쪽 간선부터 탐색하는 방법이다. 또한, 방향이 없는 무방향 그래프이다. 진행 순서를 붙이니 좀 지저분해 보이지만, 피보나치 수열을 재귀로 진행했을 때와 같다. 빨간 선은, 방문할 정점이 있는 노드로 호출되는 방향이다. 파란 선은, 갈 곳이 더 없기 때문.. 유니온 파인드(Union Find) 각 개체들의 집합 상태를 트리로 표현한 하나의 자료 구조다. 도식화한 모습이 트리 형태란 거지, 실제로 트리 자료구조를 직접 구현해야 하는 것은 아니다. 정확히는 각 개체들끼리 공통 부분이 없어야 한다는 조건이 있지만, 이 설명은 서로소란 것에 대한 수학적 접근이 필요하므로 위키를 보는 것을 추천한다. + 대부분 블로그 설명을 보면 정점끼리 묶는 예시가 많고 이 블로그도 그렇게 작성했다. 다만, 어떤 경우에는 정점이 아닌 다른 부분들을 합쳐야 한다는 것을 알아두자. ex) 간선의 가중치 등 다음과 같이 1~5 까지의 노드가 있다. 처음 각 노드들의 root 노드는 자기 자신이다. (부모 노드라 하는게 맞는데 편의상 root로 함) Union 서로 다른 두 개체를 합친다. 정확히는 값이 낮은 개체로 uni.. 0-1 BFS 간단한 BFS문제인줄 알았는데, 일반적인 bfs 그래프 풀이로는 메모리초과나 시간초과가 자명한 문제였다. 나름대로 최적화 기준을 세워서 풀어봤지만 한참을 틀린 뒤 태그를 보고 검색을 해보니 바로 이해가 됐다. 왜 0-1가 붙는데? 간선의 가중치가 0과 1밖에 없어서 그렇다. 즉, 비용없이 정점을 지나는 경우와, 비용을 들여 정점을 지나는 경우로 나뉜다. 이게 되게 난해한 부분이, 매 순간마다 비용없이 정점을 지나는 경우를 고려해 큐에 넣어야 하기 때문에 메모리가 초과되거나, 무한루프를 돌아 시간초과가 나버린다. 해결 방법 덱 자료형을 사용하면 편하다. 다른 자료형을 사용해도 풀 수 있지만, 개인적으론 덱이 편했다. 비용을 들이지 않고 지나는 경우엔, 덱의 선두에 넣어야 한다. 비용을 들이고 지나는 경우엔.. 이전 1 다음
