[코딩테스트 합격자 되기] 그래프

[인프런] 코딩 테스트 합격자 되기 C++

[그래프의 구현 방법]

인접 행렬 [c++ 코드]
- 행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 됨
- 노드 대비 간선이 적을 경우 메모리 공간 효율이 좋지 않음
인접 리스트 [c++ 코드]
- 특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식
- 실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비 없음
- 특정 노드에 모든노드가 연결된 경우, 탐색시 O(N)이 될 수 있음 (드문 케이스)

[DFS와 BFS]

c++ 코드 : DFS BFS

백트래킹(부모노드로 가는 행위)은 DFS에만 존재
- 백트래킹은 모든 경우의 수를 다 따질 때 유용
- e.g. 스도쿠 문제, 1~5를 사용해서 합이 10이 되는 모든 경우
BFS으로 찾은 해만 최적해를 보장
- DFS는 시작 노드에서 가장 가까운 해라는 것이 보장 안됨
BFS는 모든 인접 노드를 큐에 푸시하므로 DFS보다 메모리 사용량이 높음
물론 둘 다 되는 경우 존재. 애매한데 최적해라는 말 없으면 DFS 먼저 시도 (강사 의견)

[다익스트라 - 최단경로 알고리즘] c++코드

음의 가중치가 없는 경우, 두 노드를 잇는 가중치의 합을 최소로 하는 경로를 찾는 알고리즘

최소 비용과 직전 노드를 저장하면, 시작 노드에서 특정 노드까지의 최소 비용과 그 경로를 알 수 있음

cod