Elevation

그래프 이론의 유명한 문제인 최단 경로 문제를 해결하는 알고리즘에 대해 알아보자. 알고리즘에 따라 사용 가능한 조건과 얻을 수 있는 결과가 다르기 때문에 상황에 맞는 알고리즘을 잘 골라서 사용하는 것이 중요하다. 다익스트라다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 꽤 빠른 시간 안에 동작하나 가중치가 양수여야 한다는 제한조건이 있다. 이는 다익스트라가 (전체 최단 경로)=(부분 최단 경로들의 합)이라는 그리디한 접근으로 동작하기 때문이다.* 참고: 다익스트라의 초기 아이디어는 그리디이나, 효율성을 위해 힙을 사용하게 되면서 힙에 방문한 정점을 중복해서 넣는 방식으로 구현하면 일종의 백트래킹처럼 동작한다. 이 경우 음수 가중치의 간선도 ..

서로소 집합서로소 집합(Disjoint set)은 Union-find 알고리즘으로도 많이 불리는데, 서로 겹치는 원소가 없으면서 전체 원소를 포괄하는 집합들의 처리와 관련된 알고리즘이다. 즉 서로소 집합에서 모든 원소는 각각 정확히 1개의 집합에 속하게 된다. 서로소 집합이 지원하는 연산은 2가지이다.​$find(x)$: 원소 x가 속한 집합을 출력한다.$union(a, b)$: 원소 a가 속한 집합과, b가 속한 집합을 합친다.​두 연산을 구현하기에 최적화된 자료구조는 트리이다. 트리를 이용하면 루트 노드를 집합명으로 사용하여 다음과 같이 이해할 수 있다.​$find(x)$: x가 속한 트리의 루트 노드를 출력한다.$union(a, b)$: a와 b가 속한 트리의 루트 노드를 각각 구하여, 둘 중 하나..

DAG방향 비순환 그래프(Directed Acyclic Graph, DAG)란 방향 그래프 중 cycle이 없는 그래프를 뜻한다. cycle이 없기 때문에 linearlization이 가능하다. 이렇게 우선순위에 맞게, 즉 화살표가 오른쪽으로만 향하게끔 정점들을 정렬하는 것을 위상 정렬(Topological sort)이라 한다. 위상 정렬의 해답은 여러 개일 수 있다. DAG는 전체 대상 중 두 대상 간의 관계가 여러 차례 제시된 경우 성립할 수 있다. ex) 두 학생의 키를 비교하거나, 두 과목 간의 위계가 제시된 경우 이때 위상 정렬 알고리즘을 통해 제시된 관계들을 만족시키는 전체 대상들의 순서를 구할 수 있다. DFS를 이용한 위상 정렬위상 정렬의 구현 방법으로는 대표적으로 2가지가 제시되어 있..

그래프의 구현그래프는 인접 리스트나 인접 행렬로 구현한다.인접 리스트: 한 정점과 연결되어 있는 다른 정점들을 연결리스트로 표현인접 행렬: $N \times N$ 행렬을 이용해 정점끼리 연결되어 있으면 1, 없으면 0으로 표현간선 수가 적은(sqarse한) 경우에는 인접리스트가 더 유리하다.​아래는 노드 $N$개와 간선 $M$개가 주어질 때 인접 리스트로 무방향 그래프를 표현하는 코드이다.N, M = map(int, input().split())adj = defaultdict(list)for _ in range(M): u, v = map(int, input().split()) adj[u].append(v) adj[v].append(u) 인접 행렬은 2차원 배열을 이용해서 다음과 같이 표현..