알고리즘 및 자료구조/탐색 검색 결과

해당 글 3건

(탐색알고리즘) 깊이 우선 탐색(DFS : Depth First Search)

깊이 우선 탐색(DFS : Depth First Search) 탐색 알고리즘에 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있습니다.이번 내용은 DFS를 주제로 포스팅하겠습니다! DFS(깊이 우선 탐색)은 트리와 그래프 같은 자료구조에서 스택을 이용하여 데이터를 탐색할 때 사용되는 알고리즘입니다.DFS 알고리즘 특징은 더이상 나아갈 길이 보이지 않을 만큼 깊이 찾아가면서 탐색합니다. 만약, 나아갈 길이 존재하지 않면 이전의 위치로 돌아와 찾아가지 않은 다른 길로 뻗어 나가면서 탐색해 나갑니다. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의..
알고리즘 및 자료구조/탐색 2017. 8. 2. 09:48

(탐색알고리즘) 이진 탐색(Binary Search)

이진 탐색(Binary Search) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있습니다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 됩니다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있습니다. 이진탐색을 설명하기 위해 한 가지의 예로 아래의 정렬된 데이터에서 22를 검색하는 과정을 설명하겠습니다. 5 11 13 19 22 38 42 첫 번째 과정으로 데이터 집합의 중앙을 선택합니다. low : 0hig..
알고리즘 및 자료구조/탐색 2016. 5. 3. 00:09

(탐색알고리즘) 순차 탐색(Sequential Search)

순차 탐색(Sequential Search) 순차 탐색(Sequential Search)은 탐색할 데이터가 모인 집합이 있으면 집합의 처음부터 끝까지 집합의 원소들을 비교하여 원하는 데이터를 찾는 알고리즘입니다.순차 탐색은 데이터를 조작하지 않아 쉽게 구현할 수 있지만 비효율적인 탐색 방법입니다. 단방향으로 탐색을 진행하기 때문에 선형탐색(Linear Search)라고 부릅니다. -------------> 순서대로 탐색 7 14 2 10 11 16 순차 탐색은 알고리즘이 단순하여 구현하기 정말 쉽고 정렬되어 있지 않은 데이터의 집합에서 평균적으로 (n+1)/2번의 비교를 거치고, 최악의 경우 n번의 거칩니다.복잡도는 O(n)입니다. 아래 예제 코드와 함께 간단한 주석을 첨부하였으니 확인하시면 됩니다.순차..
알고리즘 및 자료구조/탐색 2016. 5. 2. 22:41