알고리즘 정복하기!/알고리즘 정리 3 [알고리즘] 이진 탐색(Binary Search)이란? 이진 탐색(Binary Search) - 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 - 처음 중간의 값을 임의의 값으로 선택하고 찾고자 하는 값의 크고 작음을 비교하는 방식 - 처음 선택한 중앙값이 찾는 값보다 크면 그 값은 최댓값이 되며, 작으면 최솟값이 됩니다. 장점 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠릅니다. 단점 검색 원리상 정렬된 리스트에만 사용할 수 있습니다. 구현 예시(Python) def binarySearch(array, value, low, high): if low > high: return False mid = (low+high) // 2 if array[mid] > value: return binarySearch(array, va.. 알고리즘 정복하기!/알고리즘 정리 2022. 3. 7. [알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이란? 너비 우선 탐색 (BFS, Breadth-First Search) - 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 - 큐 자료구조를 이용함 장점 - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 - 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. - 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다. - 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다. 구현 예시(Python) from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐(Q.. 알고리즘 정복하기!/알고리즘 정리 2022. 1. 25. [알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란? 깊이 우선 탐색(DFS, Depth-First Search) - 그래프 탐색에서 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 재귀 혹은 스택 자료구조를 이용함 장점 - 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다. - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. - 얻어진 해가 최단 경로가 된다는 보장이 없다. 구현 예시(Python) # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리.. 알고리즘 정복하기!/알고리즘 정리 2022. 1. 25. 이전 1 다음
