히프 정렬 (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..

Floyd Algorithm - 모든 정점 사이의 최단 경로 - Dijkstra : 정점의 수 n개 만큼 반복 실행 - Floyd : 한 번에 찾아 준다 - 인접 행렬 weight[][] 2차원 배열에 대한 3중 반복 루프 - O(n³) Ak[i][j]를 0~k까지의 정점만을 이용한 정점 i~j까지의 최단경로 원하는 최종 결론 : An-1[i][j] A-1 → A0 → A1 → ..... → An-1순으로 최단거리 구하기 ▶ Floyd Algorithm Code int A[MAX_VERTEX][MAX_VERTEX]; void floyd(graph* g) { for (int i = 0; i n; i++) { for (int j = 0; j n; j++) { A[i][j] = g->weig..

Prim VS Dijkstra - 전체적인 틀은 BFS와 유사 Prim 각 정점의 distance는 집합 S에 존재하는 정점과 연결하는데 발생하는 weight → 각 정점의 weight는 여러 번 바뀐다 → 시작 정점 v ~ 모든 정점에 도달하는 최소비용 계산 Dijkstra 시작 정점 v ~ 모든 정점까지의 최단 거리 계산 Prim : 집합 S에서 해당 정점까지의 거리 (S ~ v) DIjkstra : 집합 S의 시작정점 r에서 해당 정점까지의 가장 짧은 거리 (S(r) ~ v) 알고리즘 비교 Prim void prim_mst(graph* g, int v) { // v = 시작 정점 init_distance(distance); init_selected(selected); distance[v] = 0; ..

최단경로 - 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로 Dijkstra 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 Floyd 모든 정점 ~ 다른 모든 정점까지의 최단 경로 Dijkstra Algorithm - 탐욕적 방법 (greedy method) 이용 - 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산 - 가중치가 음수가 아닐 때 정상적으로 작동 - Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택 - 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요 - O(n²) 시작 정점(v) 선택 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없..

Prim MST Algorithm - 시작 정점에서부터 신장 트리 집합을 확장해가는 알고리즘 - 인접 정점들 중에서 가중치가 최소인 정점을 선택해가면서 트리를 확장 이전 단계에서 만들어진 신장 트리를 확장 - n개의 정점에 대해서 n-1개의 간선을 선택하면 알고리즘 종료 - 배열로 구현 or 최소히프로 구현 - 어떤 정점에서 시작하던간에 똑같은 트리 생성 - O(n²) ※ 각 정점으로부터 거리 distance 배열, 선택된 정점 selected 배열 (모든 정점 distance = INF로 초기화) v의 인접 정점들 distance 업데이트 인접 정점들 중 distance가 가장 낮은 정점(w) 선택 v와 w를 하나의 그룹으로 간주하고 해당 그룹으로부터 distance 다시 업데이트 n-1개 간선 선택할..

신장 트리 (Spanning Tree) - 그래프의 모든 정점들을 포함하는 트리 - 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리 - 모든 정점들을 가장 적은 수의 간선, 비용으로 연결 - n개의 정점들에 대해 반드시 n-1개의 간선만 사용 + 사이클 포함 X ex) 도로 건설, 전기 회로, 통신, 배관,.... Kruskal Algorithm, Prim Algorithm Kruskal MST Algorithm - 탐욕적 방법 (greedy method) 이용 - 간선을 기반으로 하는 알고리즘 - 간선의 개수 e개 → O(|e|log₂|e|) - 매 선택마다 최선의..