개발자 블로그

파이썬의 경우 가장 빠른 퀵솔트로 sort()함수가 구현이 되어있다. 퀵 솔트란? 기준 데이터를 설정하고 그 기준 보다 작은 데이터들을 왼쪽으로 큰 데이터들은 오른쪽으로 위치를 바꾸어 주며, 바뀐 데이터들 이와 같은 방법으로 재귀적으로 실행되며 정렬되는 방식. 평균적인 시간 복잡도는 O(nlogn)이고 최악의 경우, O(n**2)이 된다. 정렬 알고리즘 중 가장 빠른 시간을 자랑하지만, 기준 데이터에 따라 최악의 시간 복잡도를 가질 수 있다. 따라서, 적절한 pivot(기준)을 정해주는 것이 중요하겠다. python 또한, 내부적으로 항상 nlogn으로 pivot을 설정하여 작동하게 끔 구현이 되어있다. def quick_sort(array: list) -> list: if len(array)

흔히 우리가 탐색을 할 때, 모든 배열을 확인하는 방법을 지양한다. 예를 들어 100까지 수 중에서 하나를 골라 up/down 게임을 한다고 하자. 우리는 보통 중간부터 수를 불러 좁혀나가는 식으로 하는 것이 빠르다는 것을 알고 있다. 따라서 모든 배열을 탐색하는 배열의 길이만큼의 시간 복잡도 대신 log2n의 시간복잡도를 갖을 수 있다. 이를 코드로 구현해보자! # 이진 탐색 - 정렬이 되어있는 배열에서 가능 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(target, array): current_min_idx = 0..