algorithm using python (4) 썸네일형 리스트형 이진탐색 배열 내부의 데이터가 sorting이 되어 있어야만 사용가능 찾으려는 데이터와 중간점에 위치하는 데이터를 반복적으로 비교해서 범위 밖의 데이터는 날리면서 진행 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어듬 시간복잡도 : O(logN) 요청사항이 들어오면 그 제품이 있는지 이진탐색으로 찾아보는 코드 graph algorithms - bfs, dfs 그래프구조에서 기초적인 탐색알고리즘으로 이용되는 bfs, dfs를 파이썬으로 구현해보았다. BFS = Breadth-First Search(너비우선탐색) - 루트 노드에서 시작해 인접 노드를 먼저 탐색하는 방법 - 넓게 탐색 - 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이용 - 재귀적으로 동작하지 않음 - 어떤 노드를 방문했었는지 여부를 반드시 검사해야함 - 큐를 이용해서 넓이부터 탐색 DFS = Depth First Search - 루트 노드에서 시작해 다른 branch로 넘어가기 전 해당 branch를 깊게 완벽하게 탐색 - 모든 노드를 방문하고자 할 때 이용 - Stack 이용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 .. Quick Sort divide & conquer algorithm pivot이라고 불리는 임의의 값을 기준으로 분할 정복 쿽 정렬의 성능은 어떠한 pivot 값을 선택하느냐에 영향을 많이 받는다. Best Case에서는 pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 merge sort와 마찬가지로 O(nlogn)의 시간 복잡도를 가지게 된다. 하지만 pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면 성능이 저하된다. Worst Case의 경우 한 편으로만 모든 값이 몰리게 되어 O(n^2)의 시간 복잡도를 가진다. 따라서 상용화를 할 때에는 중앙값(median)에 가까운 pivot 값을 선택하는 것이 좋다. 배열의 처음, 중앙, 마지막에 들어있는 값들 중에 크기가 중간인 .. Merge Sort Sorting algorithm divide & conquer algorithm 시간복잡도 각 층의 계산 시간 : 데이터 개수가 n일 때, 이를 정렬하는 데 cn의 시간이 걸린다고 해보자(c는 컴퓨팅 파워 등과 관계 있는 어떤 상수를 나타냄). 층의 수 : logn Big-O notation : O(nlogn) Python Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 def merge(left, right): result = [] while len(left) > 0 or len(right) > 0: if len(left) > 0 and len(right) > 0: if left[0] 0: result.app.. 이전 1 다음
