탐색알고리즘 (2) 썸네일형 리스트형 [알고리즘] Binary Search Binary Search 이진 탐색 알고리즘을 말 그대로 탐색 알고리즘이다. 하지만 단순하게 처음부터 마지막까지 순서대로 비교하면서 탐색하는 방법이 아닌, 탐색 범위를 좁혀가며 데이터를 찾아내는 방식이다. 이진 탐색 알고리즘을 적용하기 위한 조건으로 배열 혹은 리스트에 있는 데이터들은 정렬이 되어있어야 한다. 그리고 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하면서 원하는 데이터를 찾게 된다. 이진 탐색 알고리즘은 재귀호출을 이용하여 구현할 수도 있고, 반복문을 이용해서 구현할 수도 있다. Example Code def binary_search(source, target, start, end): if start > end: return None mid = (start + end) // 2 .. [알고리즘] DFS (Depth First Search) DFS (Depth First Search) 그래프를 전체 탐색하는 깊이 우선 탐색 DFS는 탐색을 시작한 시작점부터 해당 부분을 완벽하게 탐색하고 다음으로 넘어가는 방식이다. 아래 그림을 보면 좀더 빠르게 이해할 수 있다. 위 그림처럼 한개의 분기에 대해 모든 탐색이 완료되면 다음 분기로 넘어가고, 완벽하게 탐색한 후에 다음 분기로 넘어가는 흐름을 띄고 있다. 이는 스택, 재귀호출 방식으로 구현할 수 있다. 일반적으로 재귀호출을 사용하였을때 구현하기 편해 자주 사용하지만, 스택오버플로우가 발생할 수 있기 때문에 잘 구현해야 한다 (노드 방문시 방문여부를 검사하면서 진행해야 무한반복에 빠지지 않을 수 있다). 장점 한 분기의 깊이가 깊더라도 완벽하게 탐색하고 다음 분기로 넘어가기 때문에 목표노드가 깊은 .. 이전 1 다음
