소스코드: https://github.com/orlp/pdqsort 논문: https://arxiv.org/abs/2106.05123 Best Average Worst Memory Stable Deterministic n n log n n log n log n No Yes PDQSort 요약 pdq sort는 Pattern-Defeating Quicksort입니다. 특정한 패턴이 감지되는 경우에 빠르게 소팅할 수 있다는 특징이 있으며, 3가지 기본적인 소팅을 합친 하이브리드 소팅입니다. rust에서는 기본 sorting으로 채택했으며, 대략 45% 정도의 성능 향상이 있다고 합니다(링크). 아이템들이 정렬된 경우에 O(n)의 시간이 걸리고(이 과정에서 insertion sort가 사용될 수 있음) 일반적..
본문에서 언급되는 알고리즘은 문자열 검색과는 다른 알고리즘입니다. 특정 배열이 있을 때, 그 배열에서 과반수를 차지하는 아이템이 어떤 것인지 찾는 알고리즘입니다. Time Complexity: O(n) Space Complexity: O(1) 과반수를 차지하는 아이템은 count > size(nums)/2 의 특성을 가지고 있습니다. def majorityElement(nums: List[int]) -> int: count = 0 candidate = None for num in nums: if count == 0: candidate = num count += (1 if num == candidate else -1) return candidate https://www.youtube.com/watch?v=..
링크드 리스트는 '노드를 연결해서 만드는 리스트'를 의미하고, 노드는 데이터와 다른 노드를 가리키는 포인터로 이루어져 있습니다. C언어에서 링크드 리스트를 표현하면 다음과 같이 표현할 수 있습니다. #include struct Node { int data; struct Node* nextNode; }; int main() { struct Node MyNode; return 0; } typedef로 짧은 이름을 부여할 수도 있습니다. #include typedef struct tagNode{ int data; struct Node* nextNode; } Node; int main() { Node MyNode; return 0; } 링크드 리스트의 주요 연산은 다음과 같습니다. - 노드 생성/소멸(creat..