반응형 알고리즘91 유니온 파인드(Union - Find) 유니온 파인드(Union - Find) 유니온 파인드란? - 여러 개의 노드 중 선택된 두 노드가 같은 집합에 속하는지 판별하는 알고리즘 - 서로소 집합(Disjoint - Set) 알고리즘이라고도 불린다. - 재귀 함수를 이용하여 부모 노드를 찾고, 합친다. 유니온 파인드 실행 과정 - Find : 선택된 두 노드의 부모를 확인하여 현재 같은 집합에 속하는지 판단하는 과정 - Union : 두 노드를 합치는 과정. 두 노드를 합쳐서 같은 부모를 가지도록 만든다. 유니온 파인드 코드(C++) // 유니온 파인드 클래스 class unionFind { public: void initUnion(int n) { // 부모 노드에 자기 자신이 들어가 있는 경우(아무것도 연결되어 있지 않다.) for (int i.. 2020. 6. 17. 정렬 알고리즘 - 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 퀵 정렬 이란? - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법. - 정렬 대상을 반씩 줄여가며 정렬한다. - 피벗을 기준으로 정렬한다. - 피벗을 어떤 값으로 설정하냐에 따라 속도가 달라진다. (피벗이 중간에 해당하는 값일 경우 정렬 대상을 균등하게 나눈다) - 정렬대상에서 세 개의 데이터를 추출하고, 그 중 중간 값에 해당하는 것을 피벗으로 삼는다. - 퀵 정렬은 O(nlogn)의 시작복잡도를 가진다.(최선의 경우) // 최악의 경우 O($n^2$) 퀵 정렬 예시(오름차순) - left와 right가 교차되는 상황 발생하면 더 이상 정렬할 대상이 없다는 것이다. 퀵 정렬 코드(C++) #include #include .. 2020. 6. 16. 정렬 알고리즘 - 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 병합 정렬이란? - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법. - 데이터가 1개 남을 때까지 분할하고, 분할된 데이터를 정렬한 후 다시 결합한다. - 실제 정렬은 분할하는 과정이 아니라, 병합하는 과정에서 이루어진다. - 병합 정렬은 O(nlogn)의 시간복잡도를 가진다. - 병합 정렬은 임시 메모리가 필요하다는 단점이 존재한다. 병합 정렬 예시(오름차순) 병합 정렬의 정렬&결합 과정 - 결합하는 두 데이터는 모두 정렬되어 있다. - 처음부터 하나씩 비교하여 임의의 데이터 공간에 저장한다. 병합 정렬 코드(C++) #include #include using namespace std; void MergeData(vec.. 2020. 6. 16. 정렬 알고리즘 - 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 삽입 정렬 이란? - 이미 정렬되어 있는 것에 하나씩 추가해 정렬하는 방법 - 대상이 이미 정렬되어 있다면 매우 빠른 속도로 동작한다. - N개의 데이터가 주어졌을 때 O($N^2$)의 시간복잡도를 가진다. 삽입 정렬 예시 삽입 정렬 코드(C++) #include #include using namespace std; void insertionSort(vector &vec) { int i, j, data; for (i = 1; i = 0; j--) { if (vec[j] > data) { vec[j + 1] = vec[j]; } else break; } vec[j + 1.. 2020. 6. 14. 이전 1 ··· 17 18 19 20 21 22 23 다음 반응형
