CS 기초/Data structure & Algorithm2 퀵 정렬(Quick Sort) 동작 - 까먹지 않도록 하기 위한 방법.. 퀵 정렬 동작을 까먹지 않도록 하기 위해 퀵정렬의 느낌과 동작을 정리를 해보았다. (오름 차순 기준) 퀵 정렬의 전체적인 그림은 배열에서 pivot이라는 기준을 정하고, 그 기준으로 왼쪽 영역은 pivot보다 더 작은(같거나) 원소들이 놓이도록, 오른쪽 영역은 더 큰(같거나) 원소들이 놓이도록 하는 것이다. 왼쪽 오른쪽 영역이 정렬되어 있을 필요는 없다. 그냥 pivot을 기준으로 크기가 작거나 크면된다. 이후엔 나뉜 왼쪽과 오른쪽 영역에 대해 다시 재귀적으로 quicksort를 진행한다. 그러면 왼쪽 영역에서 또 pivot을 정하고 영역을 나눌 것이고, 오른쪽 영역에 대해서도 마찬가지일 것이다. 이는 왼쪽 영역과 오른쪽 영역이 더 이상 나뉘지 않을 때, 즉 나누려는 영역이 1개이면 리턴한다. 이를 코드.. 2021. 5. 13. [C++] 벡터(Vector)와 리스트(List) 벡터(Vector) 벡터(vector)는 기본적으로 동적 배열이다. 즉 매번 size를 확인하며 배열이 꽉 차게되면 자동으로 capacity를 늘린다. 물론 이 과정엔 메모리를 해제했다가 다시 할당하고 값을 복사하는 오버헤드가 포함되어 있다. 또한 메모리의 잦은 할당은 fragmentation을 초래한다. 따라서 사용 전 reserve를 통해 어느정도 capacity를 정하는 것이 좋다. 배열이기 때문에 인덱스를 지원하며 임의의 요소에 상수 시간으로 접근이 가능하다.(물론 인덱스를 알고 있다고 가정할 때) 하지만 임의의 요소가 삭제되거나 추가될 때 요소의 순서를 유지하기 위해 백터는 재정렬을 해야하는 오버헤드가 있다. 따라서 맨뒤에 요소를 삽입하거나 삭제하는 연산이 아닌 중간에 삽입 삭제가 빈번하게 발생.. 2019. 11. 8. 이전 1 다음
