선택 정렬 (Selection Sort) Unstable Sort 시간복잡도 - O(n2) 장점 - 알고리즘이 단순하다 - 실제로 교환하는 횟수가 적기 때문에 많은 교환이 일어나는 자료상태에서 Bubble Sort보다는 효율적이다 - 추가 메모리가 필요없다 단점 - 불안정 정렬(Unstable Sort)이다 - 시간복잡도가 최선/평균/최악 전부 O(n²)으로, 굉장히 비효율적이다 과정 주어진 배열 중 최솟값 찾기 해당 값을 맨앞으로 옮기기 나머지 요소들도 똑같이 반복 ▶ Selection Sort Code static void selection_sort(int [] A){ for(int i=0; i

버블 정렬 (Bubble Sort) Stable Sort 인접한 두 정수를 비교해서 정렬 시간복잡도 - O(n²) 장점 - 구현이 매우 간단하다 - 추가 메모리가 필요없다 단점 - 시간복잡도가 최선/평균/최악 전부 O(n²)으로, 굉장히 비효율적이다 ▶ Bubble Sort Code static void bubble_sort(int [] A){ Calendar before = Calendar.getInstance(); for(int i=0; i

삽입 정렬 (Insertion Sort) Stable Sort 시간복잡도 - 최선 : O(n) - 평균/최악 : O(n²) 장점 - 레코드 수가 적을 경우, 알고리즘이 매우 간단하다 - 정렬이 대부분 되어있는 리스트의 경우 매우 효율적 단점 - 많은 레코드들이 이동행한다 - 레코드 수가 많고 레코드 크기가 크면 적합하지 않다 과정 리스트의 2번째 요소부터 인덱스를 내려가면서 비교해서 정렬 ▶ Insertion Sort Code static void insertion_sort(int [] list){ Calendar before = Calendar.getInstance(); for(int i=1; i=0 && list[index] > key) { // 밑에 있는 요소들이 key보다 크면 list[index..

퀵 정렬 (Quick Sort) Unstable Sort 분할 정복(Divide and Conquer) 알고리즘 다른 원소들과의 비교만으로 정렬 수행 Merge Sort와 다르게, Quick Sort는 비균등하게 분할 평균적으로 매우 빠른 수행 속도 > C에서는 라이브러리 함수로 qsort가 주어진다 > Java의 Arrays.sort는 quick sort로 구현되어있다 시간복잡도 - 최선/평균 : O(n log n) - 최악 : O(n²) 장점 - 속도가 빠르다 - O(n log n)을 가지는 다른 정렬 알고리즘과 비교해도 가장 빠르다 - 추가 메모리 공간이 필요없다 단점 - 정렬된 리스트에 대해 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다 pivot을 선택할 때 리스트를..

쉘 정렬 (Shell Sort) Unstable Sort 정렬할 리스트의 간격에 따라서 각 부분 리스트를 정렬하는 정렬 알고리즘 간격(gap) = 리스트/2/2/2,...... → 계속해서 2로 나눠준다 (1이 될 때 까지) 만약 gap이 짝수이면 1을 더해준다 (간격이 홀수이면 더 성능이 좋다) 부분 리스트의 개수는 gap과 동일하다 보통 전체에서 h/2를 하지만 이보다 h/3 + 1 이 더 빠르다 시간복잡도 - 최선 : O(n) - 평균/최악 : O(n1.5) 장점 - Insertion Sort의 단점을 보완하고 개념을 확대해서 만든 정렬 - Insertion Sort보다 성능이 우수하다 - 데이터가 본인의 index에서 멀리 떨어져 있을 경우, 교환을 여러번하는 Bubble Sort의 단점을 해결 ..

히프 정렬 (Heap Sort) Unstable Sort 완전이진트리 구조 배열을 이용해서 구현 or 컬렉션을 통해서 구현 시간복잡도 - O(n log n) 장점 - 추가 메모리가 필요없고 항상 O(n log n)의 시간복잡도를 가진다 단점 - 보통의 경우, 퀵정렬보다 느리다 데이터의 상태에 따라서 다른 정렬들에 비해 조금 느리다 - 안정성을 보장받지 못한다 과정 - 최대힙 : 힙에서 pop시킨 요소를 배열의 뒤에서부터 채운다 - 최소힙 : 힙에서 pop시킨 요소를 배열의 앞에서부터 채운다 C : 직접 구현 Java : PriorityQueue / 직접 구현 Python : heapq / PriorityQueue / 직접 구현 ▶ PriorityQueue 이용 PriorityQueue pq1 = new ..

합병 정렬 (Merge Sort) Stable Sort 분할 정복(Divide and Conquer) 기법 (순환 호출로 구현) 1. 하나의 리스트를 2개의 균등한 크기로 분할 2. 분할된 부분 리스트들을 각각 정렬 3. 최종 정렬된 2개의 부분 리스트를 합해서 하나의 정렬된 리스트로 생성 추가적인 리스트가 필요하다 각 부분 리스트를 정렬할 때, 합병 정렬을 순환 호출해서 정렬 실제로 정렬이 이루어지는 시점은 최종적으로 정렬된 2개의 부분 리스트를 합병하는 단계(3)이다 Java의 Collections.sort는 합병정렬로 구현 시간복잡도 - O(n log n) 장점 - 항상 O(n log n)이라는 시간복잡도를 가진다 단점 - 추가적인 메모리가 필요하다 - 추가 메모리를 할당할 수 없으면 Quick S..

기수 정렬 (Radix Sort) Stable Sort 비교하지 않는 정렬 알고리즘 기수(radix) = 숫자의 자리수 → ex) 42 = 4와 2의 2개의 자리수 보유 십진수에서 각 자리수는 0~9까지의 값만 가지기 때문에 10개의 버킷을 생성해서 (0, 1, 2,....9) 숫자의 기수에 맞게 버킷에 집어넣는다 낮은 숫자의 버킷부터 차례대로 해당 버킷의 값을 꺼내면서 정렬 큐(Queue)로 구현하면 편리하게 구현 가능 숫자가 10 이상일 경우 1. 자릿수가 2개가 존재하기 때문에, 먼저 1의 자리수를 기준으로 버킷에 집어넣는다 2. 1의 자리수를 기준으로 insert된 버킷에서 각 숫자를 꺼낸다음에 십의 자리수를 기준으로 버킷에 집어넣고, 버킷에서 꺼내면 정렬이 완료된다 정렬할 배열 A, 10개의 B..

계수 정렬 (Counting Sort) Stable sort 비교하지 않는 정렬 알고리즘 좁은 범위의 Data를 정렬할 때 효과적 입력받는 수의 범위가 한정되어 있을 때 사용 총 배열 3개가 필요 (정렬할 배열 A, 누적 합 배열 C, 최종 정렬된 배열 result) - 추가 배열 C 배열 A에 존재하는 각 요소들의 등장횟수를 오름차순으로 저장하고, 배열 C의 맨 앞 인덱스부터 차례대로 값들을 누적해서 저장 배열 C는 결국 배열 A의 각 요소들의 인덱스를 저장 시간복잡도 - O(n + k) → k = 배열의 최댓값 장점 - O(n)의 매우 빠른 속도로 정렬 가능 단점 - 음수/실수는 정렬 못함 - 추가적인 메모리 공간이 필요하고 값의 분포에 따라 메모리 낭비가 심해질 수 있다 과정 정렬할 배열 A, 배열..

정렬 별 시간복잡도 정렬 시간복잡도 공간복잡도 정렬상태 최선 평균 최악 계수 정렬 Counting Sort O(n+k) O(n+k) O(n+k) O(k) Stable 기수 정렬 Radix Sort O(nk) O(nk) O(nk) O(n+k) Stable 팀 정렬 Tim Sort O(n) O(n log n) O(n log n) O(n) 히프 정렬 Heap Sort O(n log n) O(n log n) O(n log n) O(1) Unstable 합병 정렬 Merge Sort O(n log n) O(n log n) O(n log n) O(n) Stable 쉘 정렬 Shell Sort O(n) O(n1.5) O(n1.5) O(1) Unstable 퀵 정렬 Quick Sort O(n log n) O(n log..

자료구조 시간복잡도 평균 최악 접근 탐색 삽입 삭제 접근 탐색 삽입 삭제 Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) Stack O(n) O(n) O(1) O(1) - pop O(n) - remove O(n) O(n) O(1) O(1) - pop O(n) - remove Queue O(n) O(n) O(1) O(1) - dequeue O(n) - remove O(n) O(n) O(1) O(1) - dequeue O(n) - remove Deque O(n) O(n) O(1) O(1) - pop O(n) - remove O(n) O(n) O(1) O(1) - pop O(n) - remove Singly Linked List O(n) O(n) O(1) O(1) O(n) O..

HashTable - (key, value)로 데이터를 저장하는 자료구조 - 빠른 검색 속도 내부적으로 bucket을 사용해서 데이터를 저장 bucket : 실제 값이 저장되는 장소 - 각각의 key값에 해시함수를 적용해서 bucket의 고유한 index를 생성해서 index를 활용해서 값을 저장/검색 index = key.hashCode()%capacity - O(1) - capacity : bucket의 크기 (16) - load_factor = 저장된 데이터 개수 / capacity ※ Example ("John Smith", "521-1234") 데이터를 capacity(16)인 HashTable에 저장하면 index = hash_function("John Smith")%16 bucket[inde..