뇌의 외장하드

- 별도의 모든 범위를 담을 수 있는 리스트 선언 후, 한번에 반환받는 방식(비교 기반이 아님) - 특정 조건 부합시에만 사용 가능(데이터가 정수 형태 / 데이터의 범위 ≤ 1,000,000) 시간 복잡도 : O(N + K) 공간 복잡도: O(N + K) 범위의 끝과 끝 두값이 있는 경우, 비효율적 N: 데이터의 개수, K: 데이터의 최대값 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count = [0] * (max(array) + 1) #0 ~ 9 면 10개임 for i in range(len(array)): count[array[i]] += 1 for i in range(len(count)): for j in range(count[i]): prin..

- Pivot(큰 값 작은 값을 교환할 때의 기준)을 사용 - Pivot이 이동된 경우 Pivot을 기준으로 좌 우를 별개로 나눠 교환 반복 - 가장 많이 사용되는 정렬 알고리즘, 대부분의 정렬 라이브러리의 근간 시간 복잡도 : O(NlogN) 최악의 경우 O(N^2) - 이미 정렬된 경우, 인덱스 n(n-1, n-2 ..._)부터 Pivot까지 공간 복잡도: O(N) #파이썬이 지리는 형태 array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array): #리스트가 하나 이하의 원소가 남았을 때, 종료 if len(array) = end: # 원소가 1개인 경우 종료 return pivot = start left = start + 1 right = end w..

- 정렬되어 있는 데이터들을 비교하며 적절한 위치에 삽입 - 데이터가 거의 정렬 되어 있을 때, 효율적 시간 복잡도 : O(N^2) 최선의 경우 O(N) 공간 복잡도: O(N) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): #첫 번째 데이터는 정렬되어 있다고 판단 for j in range(i, 0, -1): if array[j] < array[j-1]: array[j], array[j-1] = array[j-1], array[j] else: break 정렬 전체가긔 이것이 코딩 테스트다 - 나동빈 정리하긔

- 기준에 가장 적합한 데이터를 선택해 (정렬된 데이터 제외) 맨 앞의 데이터와 교환하는 것을 반복 - 원시적인 방법, 비효율적임 시간 복잡도 : O(N^2) ≒ (N^2 + N)/2 ≒ N! ≒ 연산 횟수 공간 복잡도: O(N) 연산 횟수: N + (N-1) + (N-2) + ... + 2 N개 확인, 정렬된 1개의 데이터를 제외하고 확인 ... 마지막 하나 남은 경우는 확인하지 않아도 됨 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[m..

정렬이란? - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 공식처럼 사용 (이진 탐색의 전처리 과정 등) 선택 : O(N^2), 거의 사용 X 삽입 : O(N) ~ O(N^2), 정렬이 거의 된 경우 가장 빠름 퀵 : O(NlogN) ~ O(N^2), 이미 정렬이 된 최악의 경우가 N^2 계수 : O(N+K), N: 개수 K: 최대값 파이썬 기본 정렬 라이브러리: O(NlogN) 보장 1. 단순히 정렬 기법을 아는지 묻는 문제 (정렬 라이브러리 사용 시 가능) 2. 정렬 알고리즘의 원리를 묻는 문제 3. 빠른 알고리즘이 필요한 문제 (기존의 알고리즘에 구조적인 개선을 거쳐야함) tip. 별도의 요구사항이 있는 경우(데이터 한정, 동작 시간 단축), 계수 정렬 사용이 유리 1. ex) 위에서 아..