Computer Security

너비 우선 탐색 너비 우선 탐색(Breadth First Search)은 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다. DFS 와 마찬가지로 맹목적으로 전체 노드를 탐생하고자 할 때 자주 사용되며, 큐(Queue) 자료구조에 기초한다. ※큐는 차례로 넣고 , 뺄때는 가장 먼저 들어간놈이 빠져 나오는 구조이다. ex) 1->2->3->4->5 순서대로 넣었다면, 1이 가장 먼저 들어간놈이고, 빠져나올땐 1이 먼저 빠져나간다. 위와 같이 전체적으로 크게, 넓게 탐색하는것이 특징이다. 장점 1. 출발 노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 1.경로가 매우 길 경우에는 탐색가지가 매우 넓어지면서, 그에따라 메모리 할당량이 많아진다. 2.해가 존재하지 않는다면, 유한그래프의 경우에는 모든 ..

깊이 우선 탐색(Depth First Search)은 DFS 라고도 불리우는데 탐색을 할때 보다 깊은것 부터 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색(DFS)는 전체 노드를 맹목적으로 탐색하고자 할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택 자료구조를 통해 만들 수 있다. 장점 1.단지 현 경로상의 노드들만 기억하면 된다 --> 저장공간의 수요가 비교적 적다. .2목표 노드가 깊은 단계에 있을 경우 , 깊은것 부터 우선적으로 탐색하기 때문에 빠르게 해를 구할 수 있다. 단점 1.깊은 경우일때, 해가 없는 경우에 빠져버리면 수행하기 어려울 수 있다. 2.얻어진 해가 최단경로다! 라고 말하기 어렵다. 목표에 이르는 경로가 여러가지 일때, 깊이우선탐색을 시행했을때, 최적화 된 방법이 아닐 수 있다..