본문 바로가기

sort3

#04 퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복을 통해 정렬을 수행하는 대표적인 정렬 알고리즘이다. 최선과 평균에서 시간 복잡도가 O(nlogn)으로 다른 정렬 알고리즘과 비교했을 때 가장 빠르다. 공간 복잡도도 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다. - 하단에 pythonic 한 코드에서는 추가로 n의 공간을 사용하므로, O(2n)이다. 이미 오름차순, 내림차순으로 정렬되었을 때 O(n^2)이고, 또한 불안정 정렬이라는 단점이 존재한다. def quick_sort(arr, start, end): if start >= end: # 인덱스가 하나 return pivot = start left = start + 1 right = end while left arr[pivot]: # 피벗보다 작은 값이 나올때까지.. 2022. 1. 6.
[프로그래머스] 무지의 먹방 라이브 (Python) https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 딕셔너리 + 정렬을 활용해서 문제를 풀었다. 효율성에서 아슬아슬하게 통과해서 더 좋은 풀이가 있을 것 같다. 알고리즘 : 1. 먹는 것이 종료되는 시간이 같은 음식을 dict를 통해 세어 준다. (defaultdict 활용) 2. 짧은 시간 순서대로 dict.items를 정렬한다. - food_times의 입력이 [6, 6, 1, 1, 2, 2, 3, 5] 일 경우 아래와 같이 정렬됨. - Tsort => [(1, 2), (2, 2), (3, 1), (5, 1), (6, 2)] (음식 다 먹는 시간, 그 음식의 개수) 3. 정렬된 T.. 2021. 12. 28.
[프로그래머스] 방금 그곡 (Python) https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 내가 짠 알고리즘은 다음과 같다. 1. #들어가 있는 음은 변환 2. 라디오에서의 play_time 계산 3. play_time과 실제 음악 시간과 비교해서 실제 재생된 음악 값으로 변경 4. 네오가 기억하는 멜로디가 실제 재생 된 음악에 있다면 5. 후보군에 이름, 재생된 시간, 입력된 순서 저장 6. 재생된 시간과, 입력된 순서 기준으로 정렬 7.. 2021. 11. 4.

티스토리툴바