본문 바로가기

전체 글

 (31)
NeetCode 12번 알고리즘: Quick Sort 니트코드 링크: https://neetcode.io/courses/dsa-for-beginners/11 AlgorithmPivot을 정하는 법을 바꾸면 더 효율적인 알고리즘도 가능하다. (worst case 완화)Code # Implementation of QuickSortdef quickSort(arr: list[int], s: int, e: int) -> list[int]: if e - s + 1  ComplexityTime ComplexityAverage : O(nlogn)Worst Case: O(n^2)   #예시 :  [1,2,3,4,5] 또는 [5,4,3,2,1] 일 때. 즉 sorted 되어 있어도 worst case Memory Complexity새로운 배열을 생성하지 않고 기존 배열..
6/29 코테 일지 (Quick Select, 배열 한 줄 출력, 딕셔너리 자료형) Quick Select (배열이 주어졌을 때, k번째로 큰 값을 select 하는 알고리즘)Neetcode 150 (https://neetcode.io/problems/kth-largest-element-in-an-array) 먼저 sorting을 하는 방식이다. 단순히 k번째로 큰 element를 select하는게 아니라 배열 전체를 sorting 하는 것이니 비효율적이다. sorting 방식에 따라 다르겠지만, 평균적으로 O(nlogn)이 될 것이다. class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return sorted(nums)[-k] 다음은 내가 생각해낸 알고리즘이다. len(nums)-k 번..
6/27,28 코테 일지 (sorting, 중복 제거, 문자열 길이로 sorting) #2751python에서 insertion, merge sort 등을 직접 구현하지 않고 sort()와, sorted를 써도 된다. (time complexity 괜찮아보임)array= [1,2,5,1,3]print(sorted(array))array.sort()print(array) #1181리스트 내 중복 원소 제거 시 나는 다음과 같은 코드를 짰는데 (제거도 아니고 출력만 안하는 코드)stack= []print(new_array[0])for i in range(len(new_array)): if stack and stack[-1] != new_array[i]: stack.pop print(new_array[i]) stack.append(new_array[i]) i=i+1다음 과 같이..

티스토리툴바