[묘공단]코딩 테스트 합격자 되기(7주차) 그래프

Erdos·2024년 2월 20일

코딩테스트

목록 보기

15/20

🗓️TIL (this week I learned)
화 읽기, 정리가 까다로움🤔
수
목 몸풀기문제1
금 몸풀기문제
토 문제

	깊이 우선 탐색 Depth-first search (DFS)	너비 우선 탐색 Breadth-first search (BFS)
참고	wiki(en) wiki(ko)	wikipedia(en) wiki(ko)
그림
특성	가장 깊은 노드까지 방문한 후에 더이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다.	시작 노드부터 인접한 노드를 모두 방문한 후 그다음 단계의 인접 노드를 방문(먼저 발견한 노드)
활용	🔹모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때 🔹그래프의 사이클을 감지해야 하는 경우	🔹미로 찾기에서 최단 경로를 찾을 때 🔹네트워크 분석 문제
장점	- 현 경로상의 노드를 기억하기 때문에 비교적 적은 메모리 - 목표노드가 깊은 단계에 있을 경우 해를 빨리 찾을 수 있음	- 가중치가 없는 그래프에서 최단 경로 보장 - 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리
단점	🔹해가 없는 경우 깊이 빠질 가능성 🔹얻은 해가 최적의 해가 아닐 수도 있음(해에 다다르면 탐색을 끝내므로)	🔹경로가 매우 길 경우 많은 저장 공간이 필요함 🔹해가 존재하지 않는 유한 그래프인 경우, 모든 그래프 탐색 후 실패로 끝남 🔹무한 그래프의 경우 해를 찾지도 못하고, 끝내지도 못함.

🔹음의 가중치가 있는 그래프에서 다익스트라 알고리즘은 제대로 동작하지 않음.
🔹가장 좋은 것을 선택하는 전력을 가진 그리디 알고리즘 원리와 같음
🔹한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다.

🔹매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용 갱신, 음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있음.
🔹왜 정점 개수 -1만큼 반복하는가? 매 연산마다 최단 경로가 1개씩 확정되므로 ✅

🔹왜 한 번 더 연산을 반복하는가? 음의 순환을 찾기 위해!

🤔🤔🤔🤔

🔹모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘