Computer Security

이진 탐색 트리 1.이진 탐색이 항상 동작하도록 구현하여 탐색속도를 극대화 시킨 자료구조를 이진 탐색 트리라 한다. 특징: 1.이진 탐색트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다. 이로인해 훨씬 더 빠르게 탐색이 가능하다. 예) 부모노드가 50이고 , 내가 찾을 숫자가 55라면, 왼쪽노드는 항상 부모노드보다 작으니, 오른쪽 노드만 탐색하면 된다. 2.이진 탐색 트리에서는 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 '완전 이진 트리' 인 경우 탐색시간에 O(logN)의 시간 복잡도를 가진다. 이진 탐색 트리 알고리즘 찾고자하는 값이 부모노드 보다 작을경우 왼쪽 자식으로 , 찾고자하는 값이 부모노드보다 클 경우 오른쪽자식으로 뻗어 나가며, 탐색한..

너비 우선 탐색 너비 우선 탐색(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.얻어진 해가 최단경로다! 라고 말하기 어렵다. 목표에 이르는 경로가 여러가지 일때, 깊이우선탐색을 시행했을때, 최적화 된 방법이 아닐 수 있다..