컴공생의 다이어리

깊이 우선 탐색(DFS, Depth First Search) DFS는 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해..

선형 탐색(Linear Search) 선형 탐색은 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 알고리즘이다. 순차 탐색(Sequential Search)이라고도 한다. 파이썬 코드 def linear_search(arr, search): # for문 사용 for i in range(len(arr)): if arr[i] == search: return True return False linear_search([3, 110, 8, 13, 2], 5) # False 반환 linear_search([3, 110, 8, 13, 2], 13) # True 반환 혹은 def linear_search(arr, search): # while문 사용 i = 0 while i < len(arr): if arr[i..

이진 탐색(Binary Search) 이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며 이분 탐색이라고도 불린다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 사람들이 숫자를 맞춰가는 업다운 게임과 같은 방식이다. 참고 : 업다운 게임 - 무한도전 니가 가라 하와이편 탐색 과정 이진 탐색은 데이터가 정렬되어있는 상태에서 진행된다. 시작점과 끝점 사이에 중간점을 정함 (만일, 중간점이 실수라면 소수점 이하를 버림) 중간점에 해당하는 값과 찾고자 하는 값을 비교 찾고자 하는 값이 중간점에 해당하는 값보다 작다면 중간점을 기준으로 왼쪽 부분을, 찾고자 하는 값이 중간점에 해당하는 값보다 크다면 중간점을 기준으로 오른쪽 부분에 해당하는 데이터 범위를 가..