본문 바로가기
반응형

알고리즘91

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) 다익스트라(Dijkstra) 다익스트라 알고리즘이란? - 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다. - 가중치가 양수인 경우에만 사용할 수 있다. - 가중치 중 음수가 존재하지 않기 때문에 그래프에 있는 모든 간선을 단 한 번만 처리한다. - 우선순위큐를 이용하여 효율적으로 구현할 수 있다. 다익스트라 실행 과정 - 1. 모든 정점의 거리값을 무한으로 설정한다.(시작점의 거리값은 0) - 2. 시작 노드와 인접한 노드들의 거리값을 설정한다. 시작 노드의 거리값 + 인접한 노드까지의 가중치 < 인접한 노드의 거리값 인 경우 인접한 노드의 거리값을 갱신한다. 인접한 노드의 거리값이 갱신된 경우 해당 노드를 우선순위큐에 넣는다. - 3. 우선순위 큐의 루트 노드를 선택하고, 해당 노드가.. 2020. 7. 16.
탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색이란? - 임의의 노드에서 인접한 노드를 먼저 모두 탐색하고 다음 단계로 넘어간다. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 두 노드 사이의 최단 경로, 임의의 경로를 탐색할 때 사용한다. - DFS보다 빠른 탐색 속도를 보인다. - 큐를 이용하여 구현한다. 너비 우선 탐색 방법 - 1. A노드를 먼저 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 노드를 큐에 넣고, 해당 노드들을 차례로 방문한다. - 3. A노드와 인접한 노드를 방문하며 해당 노드와 인접한 노드를 다시 큐에 넣는다. - 4. 위 과정을 반복하며 모든 노드를 방문한다. 너비 우선 탐색 코드(C++) #i.. 2020. 6. 22.
탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색이란? - 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 것. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 스택 또는 재귀를 이용하여 구현한다. 깊이 우선 탐색 방법 - 1. A노드를 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 B노드를 방문하고, 방문한 노드를 표시한다. - 3. B노드와 인접한 C노드를 방문하고, 방문한 노드를 표시한다. - 4. C노드와 인접한 노드가 없는 경우, 다시 B노드로 돌아가서 다른 인접한 노드가 있는지 탐색한다. - 5. 위 과정을 반복하여 모든 노드를 탐색한다. 깊이 우선 탐색 코드(C++) - 1. 재귀 이용 #incl.. 2020. 6. 22.
탐색 알고리즘 - 이분 탐색(Binary Search) 이분 탐색(Binary Search) 이분 탐색이란? - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다. - 순차 탐색 보다 훨씬 좋은 성능을 보인다. - n개의 데이터가 주어지면 O(logn)의 시간복잡도를 가진다. - 데이터를 절반씩 나누어 가며 탐색한다. 이분 탐색 과정 - 1. 데이터의 중앙 값과 찾는 값을 비교한다. - 2-1. 찾는 값 > 중앙 값인 경우 중앙 값의 오른쪽 부분을 탐색한다. 2-2. 찾는 값 Right위치가.. 2020. 6. 22.
반응형

티스토리툴바