직대딩 블로그

대표적인 정렬 알고리즘의 성능 비교 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 간단하다. 삽입 정렬 O(N^2) O(N) 데이터가 정렬되어 있을 때 가장 빠르다. 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하고, 충분히 빠르다. 계수 정렬 O(N+K) (K는 데이터 중에서 가장 큰 양수) O(N+K) (K는 데이터 중에서 가장 큰 양수) 데이터의 크기가 한정되어 있는 경우에만 사용 가능하고, 매우 빠르게 동작한다. 정렬 알고리즘 핵심 아이디어 선택 정렬 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 삽입 정렬 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는..

#include #include #include const int n_ = 1e6 + 1; int n, m, pnt[n_]; int find(int u) { if (u == pnt[u]) return u; return pnt[u] = find(pnt[u]); } void merge(int u, int v) { u = find(u), v = find(v); if (u > v) std::swap(u, v); pnt[u] = v; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i

n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 n-way 병합 정렬이다. 최선,평균,최악 모두 nlogn #include int SIZE = 10; void merge_sort(int a[], int low, int high); void merge(int a[], int low, int mid, int high); void print(int a[]); void merge_sort(int a[], int low, int high) { int mid; if (low < high) { mid = (low + high) / 2; merge_sort(a, low, mid); merge_sort(a, mid + 1, high); merge(a, low, mid, high); } } void merge..

#include void merge_sort(int sorted[], int array_a[], int array_b[], int m, int n) { int a_ptr = 0, b_ptr = 0, s_ptr = 0, k; while (a_ptr < m && b_ptr < n) { if (array_a[a_ptr]

기수 별로 비교 없이 수행하는 기수 정렬 알고리즘이다. 시간복잡도는 O(nw)이다. #include void rs(int a[], int n) { int i, j, k, base, num, mx = 0, m = 0, bucket[10][20], cnt[10]; for (i = 0; i mx) mx = a[i]; base = 1; while (base

#include //haep = priority_queue void upheap(int); //생성 void insert(int); //삽입 void downheap(); //대치 int del(); //변경 void heapsort(int a[], int); //실행 함수 int a[10]; int n = 10; //전역 배열 a와 전역변수 n void heapsort(int a[], int n) { int i; for (i = 0; i 21번 코드 for (i = 0; i < n - 1; i++) { a[i] = del(); // 삭제 35번 코드로 이동 printf("%d번 데이터 삭제 = %..

#include int count, m; void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } void qs(int a[], int left, int right) { int i, j, k, pivot; if (left left && a[j] > pivot); if (i < j) swap(&a[i], &a[j]); printf("step %d :", m++); for (int k = 0; k < count; k++) printf("%d\t"..

substring - int to string s.substr(a,b) : a~b까지를 string으로 return s.c_str() : string의 시작주소 stoi - string to int stol - string to long s.c_str() : string의 시작주소 abs : 절대값 구해줌 (힙에서 사용) priority_queue pq; reverse iterator sqrt (실수형 제곱근) greater,less 등 계산함수 str[i] == str.size() 올림 : ceil 내림 : floor 반올림 : floor(내림)에 0.5 더해 사용 sort(b, b + n, greater());

1. Suffix Array 란? 해석하면 접미사 배열로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조입니다. 문자열(Array)의 접미사(Suffix)를 사전순으로 정렬한 배열이고 보통 문자열 검색이나 전문 검사 등에 쓰입니다. Suffix Array를 이용한 대표적인 문제론 여러분들의 두뇌를 괴롭힐 LCP Array(Longest Common Prefix Array)가 있습니다. ​ 위의 그림은 banan 라는 문자열을 Suffix Array로 나타낸 경우입니다. Suffix Array는 완전 탐색보다는 조금 나은 수준으로 O(N^2)의 공간복잡도를 가집니다. ​ 그럼에도 왜 힘들게 구현하여 쓰는가. 바로 이런식으로 몇 번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조 형태를..

오늘은 알고리즘 문제를 풀 때 정말 흔히 보이는 에 대하여 알아보겠습니다. DFS, BFS, 다익스트라, 스패닝 트리 등 정말 다양한 문제에서 등장하는 것이 그래프죠. ​ 1. 그래프란 ? 가장 기본적인 정의는 정점(Vertex)와 간선(Edge)의 집합입니다. 여기서 간선은, 두 정점을 이어주는 역할을 합니다. 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있습니다. 위의 그래프는 1,2,3,4,5,6의 총 6개의 정점으로 이루어져 있고, {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} 의 총 7개의 간선으로 이루어져 있다고 불 수 있겠습니다. V(정점의 집합)..