최단 경로 알고리즘?: 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘.
- 다익스트라 알고리즘:
- 그래프 상에서 특정 한 노드에서 다른 모든 노드가지의 최단 거리를 구하는 알고리즘
- 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘
- 그리디+동적 계획법(dp)가 합쳐진 형태 -> 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으면서도 계산해둔 경로를 활용해 중복된 하위 문제를 풀기 때문
- 만약 그래프에 음의 가중치가 있으면 -> 사용 불가
- 이유: 그리디를 통해 최단 경로라고 여겨진 경로 비용을 DP 테이블에 저장한 뒤 재방문하지 않으므로 음의 가중치가 있다면 어긋날 수 있음
- 음의 가중치가 있을 경우 플로이드 워셜 OR 벨만 포드 알고리즘을 사용해야함 -> 하지만 시간 복잡도가 늘어날 수도 있음
- 벨만 포드 알고리즘: 가중 방향 그래프 상에서 특정 한 노드로부터 다른 노드까지의 최단 경로를 구하는 알고리즘
- 다익스트라의 한계점 보완을 위해 나옴(음의 가중치,사이클)
- 그러나 시간 복잡도가 늘어남. (그리하게 최소 비용 경로를 찾는 다익스트라와 달리 모든 경우의 수를 고려하는 DP가 사용됨)
- 매 단계마다 모든 간선을 전부 확인하여 모든 경우의 수를 고려함
- 플로이드 워셜 알고리즘: 모든 노드 간의 최단거리 구할 수 있음 <-> 다익스트라, 벨만 포드
- 음의 가중치가 있어도 최단 경로 구하기 가능
- but 음의 사이클이 존재한다면 -> 벨만 포드 사용해야함!
- 모든 노드 간의 최단거리 구함
- 점화식이 사용됨 -> DP(동적 계획법)
- 최단 거리를 업데이트할 테이블이 필요 -> 모든 노드간의 최단거리 이므로 2차원 배열 사용
- 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
- 일반적으로 힙(Heap)을 이용하여 구현함
부모 노드의 키 값이 자식노드보다 크거나 같은 완전 이진 트리
key(부모노드) >= key(자식노드)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진 트리
key(부모노드) <= key(자식노드)
- 힙뿐만 아니라 배열 or 연결리스트 이용하여 구현 가능
- 시간복잡도 차이
- 배열, 연결리스트는 선형 구조의 자료구조 이므로 삽입 또는 삭제 연산을 위한 시간 복잡도
O(n) - 힙은 완전 이진 트리 구조이므로 힙트리의 높이는 log₂(n+1), 힙의 시간복잡도는
O(log₂n)
- 배열, 연결리스트는 선형 구조의 자료구조 이므로 삽입 또는 삭제 연산을 위한 시간 복잡도
- 배열로 힙 표현: 힙은 일반적으로 배열을 이용하여 구현 (이유: 완전 이진트리이므로 중간에 비어있는 요소x)
- 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
- 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
- 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
- 장점
- 시간복잡도가 좋다
- 힙 정렬이 가장 유용한 경우: 전체 자료 정렬x, 가장 큰 값 몇개만 필요할 때 유용함
- 시간복잡도가 좋다
- 시간복잡도
- 트리의 높이: log₂(n)
- 하나의 요소를 삽입, 삭제 연산 소요 시간: log₂(n)
- 요소의 개수가 n개 -> T(n)=
O(nlog₂n)
- 힙은 1차원 배열로 쉽게 구현 가능
- 정렬해야할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입
- 최대 힙으로 구성된 배열에서 최댓값부터 삭제
- 삽입
- 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
- 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족
- 삭제
- 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨
- 삭제된 루트 노드에 힙의 마지막 노드를 가져옴
- 힙을 재구성
