Algorithm
-
BFS와 DFSAlgorithm/이론 2019. 10. 6. 17:58
BFS(Breadth-First Search) 너비 우선 탐색 이란 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 최단 경로를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용한다. - Queue 자료구조를 사용한다. 알고리즘 1. 시작 노드를 큐에 삽입하면서 시작한다. 동시에 시작노드를 방문했다고 알리는 방문 처리 2. 큐에서 하나의 노드를 꺼낸다. 3. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 4. 큐가 빌 때 까지 DFS(Depth-First Search) 깊이 우선 탐색이란 탐색을 함에 있어 보다 깊은 것을 우선적으로 하여 탐색..
-
GreedyAlgorithm/이론 2019. 10. 3. 00:45
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고 불린다. 미래를 생각하지 않고 근시안적으로 각 단계에서 가장 최선의 선택을 하는 기법. 알고리즘 1. 해 선택(Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다. 2. 적절성 검사(Feasibility Check): 새로운 부분해 집합이 적절한지 검사한다. 3. 해 검사(Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번 부터 다시 시작한다. 그리디 알고리즘이 통하는 몇몇 문제들이 있다. 활동선택 문제 활동 선택 문제는 쉽게 말해 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는..