[Algorithm] 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)

순차 탐색 앞에서부터 하나씩 차례대로 탐색하는 방법 array = [3, 1, 7, 5, 9] for i in range(len(array)): if array[i] == 7: print(i) break 리스트를 차례대로 순회하므로 시간 복잡도는 O(N)이다. 이진 탐색 정렬된 리스트에 대하여 찾으려는 데이터와 중간 지점의 데이터를 비교해나가며 탐색하는 방법 순차 탐색과 달리 정렬이 되어 있어야 사용할 수 있다. 중간이 정확히 안 나누어질 때는 소수점 이하를 버린다. 시간 복잡도는 O(logN)이다. 구현 def binary_search(array, target, start, end): while start array[middle]: start = middle + 1 elif target < array[..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 16.
• textsms

[Algorithm] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

사전 지식 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue) 재귀함수 자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다. 그래프 그래프에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph) DFS (깊이 우선 탐색, Depth-First Searc..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms