Algorithmic Wisdom 🧠/Search2 [알고리즘][탐색] - 깊이 우선 탐색(DFS) 깊이 우선 탐색(Depth-first Search)이란? "루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법" 넓이 우선 탐색과 (Breadth-first Search) 대비되는 알고리즘으로 말 그대로 넓이 보단 깊이를 우선적으로 탐색하겠다는 뜻 먼저 그림을 통해 이해를 해보자 이제 위에서 본 그림을 인접리스트를 사용한 JAVA 코드로 풀어보자 사용할 LinkedList와 boolean타입의 배열 선언부 /* * 먼저 정점들의 연결 다리가 되어줄 * LinkedList와 * * 방문 여부를 확인할 * boolean 타입의 배열을 선언 */ public class DFS { private LinkedList list[]; // 정점들의 인접 리스트를 저장하는 배열 pri.. 2023. 12. 3. [알고리즘][탐색] - 선형 탐색 & 이진 탐색 & 해시 탐색 탐색 알고리즘이란? 저장된 데이터들 중 원하는 값을 찾는 알고리즘 선형 탐색 알고리즘 보편적으로 정렬되지 않은 배열이나 리스트에 사용되며 단순하게 맨 앞이나 뒤에서 시작하여 순차적으로 탐색하는 알고리즘 첫 번째 원소가 정답인 경우: 1 마지막 원소가 정답인 경우: n ∴ O(n) 의 시간 복잡도를 가진다 이진 탐색 알고리즘 정렬된 배열이나 리스트에 사용되며 리스트의 중간값과 찾으려는 값의 대소를 비교하여 탐색 범위를 반으로 줄여가며 값을 탐색하는 알고리즘 (탐색하려고 하는 값이 정렬된 리스트의 중간값보다 크면 중간값을 포함한 하위값들은 탐색 대상에서 제외되며 중간값보다 작으면 상위값들은 탐색에서 제외된다) 첫 번째 원소가 정답인 경우: 1 마지막 원소가 정답인 경우: log2(n) ∴ O(log2(n)).. 2023. 8. 6. 이전 1 다음 728x90 반응형
