프로그래머스 정렬 문제 풀이 def solution(array, commands): # array는 0~100수 # commands는 100 x 3 answer = [] for i in range(len(commands)): start = commands[i][0] end = commands[i][1] k = commands[i][2] cut = array[start-1:end] cut.sort() answer.append(cut[k-1]) return answer 문제는 간단히 해결할 수 있었지만 다른 풀이들을 보며 배울 점이 많았습니다. 특히 map()과 lambda와 sorted()함수를 사용해 단 두 줄만에 작성한 코드도 있었습니다. lambda와 map, sorted관련해서 간단히 정리해보고 활..

퀵 정렬 Quick Sort 퀵 정렬 시간복잡도는 Worst 경우 O(n^2), Average : O(nlogn), Best - O(nlogn) pivot을 어떻게 설정하느냐에 따라 성능이 달라질 수 있음 값들이 이미 정렬되어 있는 경우 Worst Case : Random하게 섞어주는 방식 사용 가능 퀵정렬 과정 리스트 개수가 1개일 때 재귀 종료 0번째 값을 pivot으로 설정 pivot보다 작거나 큰 값을 low, high 리스트에 저장 저장한 low, high에 각각 재귀적으로 quick을 적용 최종 low, high, pivot을 병합 def quick(data): # 재귀 함수 종료 조건 if len(data) < 2: return data result = [] # pivot값 설정 pivot ..

병합 정렬 Merge Sort Merge Sort 시간복잡도는 Worst - O(NlogN), Average - O(NlogN), Best - O(NlogN) Merge Sort의 경우 원래 리스트의 크기만큼의 추가공간이 필요하다. 입력 Data의 크기가 클 경우 Overhead가 증가할 수 있다. Divide & Conquer 단계를 수행하므로 시간 복잡도는 LogN이다. Merge Sort는 3단계로 구성된다. 각 리스트를 절반으로 나누는 Divide 단계 나눠진 리스트를 정렬하는 Conquer 단계 정렬된 리스트를 하나로 합치는 Combine 단계 def merge_sort(data): result = [] # 중간 index 구하기 mid = (len(data))//2 # 재귀 종료 조건 if l..

선택, 삽입 정렬 특정값 index를 찾는 알고리즘 find_index() : List 안에 있는 값을 찾아서 해당 위치를 반환해주는 함수 def find_index(list_, var): res_index = -1 for i in range(len(list_)): if list_[i] == var: res_index = i break return res_index data = [24, 10, 3, 8, 33, 27, 46] print(find_index(data, 8)) Selection Sort 시간복잡도는 Worst - O(N^2), Avgerage - O(N^2), Best - O(N^2) for문을 돌며 가장 작은 값을 찾아 0번째부터 바꿔나간다. for문을 2번 돌아야 한다. i==0부터 li..