본문 바로가기

전체 글

 (171)
[최단 경로 트리] 플로이드-워셜 알고리즘[Floyd-Warshall] 플로이드-워셜 알고리즘에 대해 알아보자. 플로이드-워셜 알고리즘은 '거쳐 가는 기점'를 기준으로 최단 거리를 구한다. 예를 들어보자. 아래와 같은 그래프가 있다. 이차원 배열의 형태로 출력하면 다음과 같다. 위 상태의 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이제 이 배열을 '거쳐 가는 기점'을 기준으로 반복적으로 갱신할 것이다. 그렇게 한다면 결국엔 모든 A에서 B의 최소 비용을 구해진다. 거쳐 가는 기점이 1인 경우 이렇게 거쳐 가는 기점이 1, 2, ... N인 경우를 모두 확인한다. 다익스트라 알고리즘 vs 플로이드-워셜 알고리즘 공통점 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 차이점 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구한다. 플로이드-워..
[그래프] 인접 행렬과 인접 리스트 전체 정점 개수: N 젠체 간선 개수: E 1. 인접 행렬 그래프의 연결 관계를 이차원 배열로 표현하는 방법이다. graph라는 이차원 배열이 있다고 하자. 이에 인접 행렬을 다음과 같이 정의할 수 있다. 1) 가중치가 없을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 1, 없다면 0. 1) 가중치가 있을 때 graph[i][j]: 노드 i에서 노드 j로 가는 간선이 있다면 가중치, 없다면 INF. 장점 두 정점을 연결하는 간선을 조회할 때 시간복잡도가 O(1)이다. 단점 1. 간선 수에 상관없이 N^2크기의 이차원 배열이 필요하다. 메모리 낭비이다. 2. 모든 간선 수를 알아내기 위한 시간복잡도가 O(N^2)이다. 2. 인접 리스트 그래프의 각 정점에 인접한 정점들을 연결리스트..
[이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점 DFS와 Backtracking의 차이점을 알아보자. DFS 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 탐색한다. 불필요한 경로를 사전에 차단하는 행동이 없다. 따라서 자원 소모가 심하다. Backtracking 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로가 갔다면 더 가지 않고 되돌아온다. 이는 가지치기라고 불린다. 불필요한 경로를 조기 차단하기 때문에 확인해야 하는 경로 수를 줄일 수 있다. 위와 같은 트리가 있다. ALT라는 단어를 찾아보자. DFS는 ALT라는 단어를 찾기 전까지 모든 노드를 방문한다. Backtracking은 ALT라는 단어를 찾는 과정에서 ALT라는 단어가 될 수 없을 것 같은 경로에 갔다면 더 가지 않고 돌아온다.

티스토리툴바