7/2 탐색 알고리즘 - BFS, DFS, 다익스트라
본문 로딩 중...
| 용어 | 뜻 | 예시/활용 |
|---|---|---|
| 노드 | 그래프에서 하나의 위치나 상태 | 맵 칸, 도시, 퀘스트 상태 |
| 간선 | 노드와 노드를 연결하는 관계 | 길, 이동 가능 방향 |
| BFS | 가까운 곳부터 넓게 탐색하는 방식 | 최단 칸 수, 전파 범위 |
| DFS | 한 방향으로 깊게 들어갔다 돌아오는 방식 | 백트래킹, 경로 존재 |
| 다익스트라 | 가중치가 있는 그래프의 최단 비용 탐색 | 지형 비용이 다른 길찾기 |
DFS / BFS
다익스트라
다익스트라 알고리즘은 ++음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드++에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.
다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,
더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다.
다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다.
| 구분 | 그리디 알고리즘 | 다익스트라 알고리즘 |
|---|---|---|
| 의미 | 알고리즘을 설계하는 방식 | 최단 경로를 구하는 구체적인 알고리즘 |
| 핵심 | 현재 가장 좋은 선택을 반복 | 현재 거리가 가장 짧은 정점을 선택 |
| 목적 | 문제에 따라 다름 | 시작점에서 각 정점까지의 최단 거리 계산 |
| 최적해 보장 | 문제의 조건에 따라 다름 | 음수 가중치가 없으면 보장 |
| 관계 | 상위 개념 | 그리디 방식을 사용하는 알고리즘 |
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
게임업계 취업을 준비하다 보면 조금 불편한 현실을 마주하게 됩니다. 게임회사에 들어가고 싶은 사람은 많습니다. 특히 신입 채용은 더 그렇습니다. 공고 하나에 많은 지원자가 몰리고, 회사 입장에서는 비슷한 조건의 지원자 가운데 사람을 선택할 수 있습니다. 그래서 다른 산업에서 흔히 이야기하는 “처음부터 연봉을 낮춰 부르지 마세요.” “적극적으로 협상하세요.”
우리들의 게임 발매 이야기
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
게임업계 취업을 준비하다 보면 조금 불편한 현실을 마주하게 됩니다. 게임회사에 들어가고 싶은 사람은 많습니다. 특히 신입 채용은 더 그렇습니다. 공고 하나에 많은 지원자가 몰리고, 회사 입장에서는 비슷한 조건의 지원자 가운데 사람을 선택할 수 있습니다. 그래서 다른 산업에서 흔히 이야기하는 “처음부터 연봉을 낮춰 부르지 마세요.” “적극적으로 협상하세요.”
