* 필요 헤더: 힙 정렬, 퀵 정렬, 병합 정렬 https://hyrule.tistory.com/62 220420_정렬_힙 정렬(Heap Sort) 구현 * 처리 과정을 바탕으로 구현해 보았음 https://hyrule.tistory.com/61 220420_정렬_힙 정렬(Heap Sort) 처리 과정 hyrule.tistory.com //HeapSort.h /* * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으.. hyrule.tistory.com https://hyrule.tistory.com/64 220420_정렬_퀵 정렬(Quick Sort) 구현 * 퀵 정렬 이론과 예시를 토대로 구현 * 여기서 나온 과정과 약간 다르게 구현함 https://hyrule.tistory.com/63 220420_정..
* 필요 헤더: 힙 정렬, 퀵 정렬, 병합 정렬 https://hyrule.tistory.com/62 220420_정렬_힙 정렬(Heap Sort) 구현 * 처리 과정을 바탕으로 구현해 보았음 https://hyrule.tistory.com/61 220420_정렬_힙 정렬(Heap Sort) 처리 과정 hyrule.tistory.com //HeapSort.h /* * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으.. hyrule.tistory.com https://hyrule.tistory.com/64 220420_정렬_퀵 정렬(Quick Sort) 구현 * 퀵 정렬 이론과 예시를 토대로 구현 * 여기서 나온 과정과 약간 다르게 구현함 https://hyrule.tistory.com/63 220420_정..
[정렬 알고리즘] * 배울 내용 - 퀵 정렬, 힙 정렬, 합병(병합) 정렬 - 이외에도 많은 정렬 알고리즘이 있지만 가장 중요하고 어려운 내용들만 배울 예정. - 이외에도 다른 정렬 알고리즘들도 공부해놓으면 좋음. * 정렬의 사용처 - 대표적으로 길 찾기에 가장 많이 사용됨. * 대부분 정렬은 재귀를 통해 구현됨. * 힙정렬은 우리가 지난 시간에 배웠던 이진 트리를 기반으로 정렬하므로 힙정렬부터 할 예정. * 오늘의 목표: 셋 다 만들고 성능 테스트 * 시간복잡도: 알고리즘 성능을 수치화. 빅 오 표기법: 정렬 알고리즘이 최악의 상황에 얼마나 걸리는지를 수치화. * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으로 정렬하면 내림차순, 최소힙으로 정렬하면 오름차순으로 정렬됨. - 최대힙 -> 높은 수를 위로..
* 저번에 그려본 알고리즘 순서를 토대로 구현 https://hyrule.tistory.com/65 220420_정렬_병합정렬(Merge Sort) 알고리즘 hyrule.tistory.com /* [분할 정렬 / 합병 정렬] * 이 정렬방식은 속도가 빠른 대신, 공간이 두 배 필요하다. * 먼저 분할부터 한 후, 다시 병합하면서 정렬하는 과정을 가진다. * 이 때, 정렬된 데이터를 복사본에 저장하기 때문에 새 공간이 필요한 것이다. * 분할-정복 알고리즘 * 오름차순 정렬 예시 8 3 5 9 1 6 7 8 3 5 91 6 7 8 35 91 67 8359167 3 85 91 67 ↑↑ * 3 5 비교 -> 3이 더 작으므로 3을 배열에 등록하고 포인터를 이동 3 3 85 91 67 ↑↑ * 8 5 비교 -..
* 퀵 정렬 이론과 예시를 토대로 구현 * 여기서 나온 과정과 약간 다르게 구현함 https://hyrule.tistory.com/63 220420_정렬_퀵 정렬(Quick Sort) 이론 hyrule.tistory.com //QuickSort.h /* * 비대칭 정렬 * 최선의 경우에는 가장 빠른 성능을 가지지만 * 최악의 경우에는 매우 느리다. * 과정 요약 7 9 5 1 3 6 4 Pivot(중심점)을 하나 정함 -> (일반적으로 맨 앞 자리)7 Pivot보다 작은 건 왼쪽, Pivot보다 큰 건 오른쪽 Pivot: 7 5 1 3 6 4 7 9 * Pivot 7 기준 왼쪽 배열부터 정렬(1, 3, 4, 5, 6만 놓고 정렬) 다시 Pivot 설정 -> 5(맨 앞자리) 1 3 4 5 6 7 9 다시 ..
* 처리 과정을 바탕으로 구현해 보았음 https://hyrule.tistory.com/61 220420_정렬_힙 정렬(Heap Sort) 처리 과정 hyrule.tistory.com //HeapSort.h /* * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으로 정렬하면 내림차순, 최소힙으로 정렬하면 오름차순으로 정렬됨. - 최대힙 -> 높은 수를 위로 - 최소힙 - > 낮은 수를 위로 * 정렬 기준은 이전에 했던 방법인, main에서 선언한 함수를 함수 포인터로 넘겨 대소여부를 비교하는 방식으로 구현함. (main의 비교함수가 true를 반환하면 자리바꿈, 아니면 놔둠) - 이 방식으로 했을 때의 장점: 포인터나 클래스 등 대소판별이 어려운 객체들도 함수에 판별기준을 추가하여 대소판별이 가능해진다. ..
* 필요한 헤더: 링크드 리스트(Linked List) https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하 hyrule.tistory.com //BinaryAVLTree.h /* [자가균형이진트리] * 이진트리의 문제점: 편향트리가 될 가능성이 있다. * 편향트리는 나오는 순간 최악. * 일반 이진트리를 쓸 때 편향트리를 피할 수 있는 방법은 아예 없다.(넣는 데이터에 의존적) * 그렇다고 사용자가 데이터를 직접..
* 이진트리 구현 https://hyrule.tistory.com/57 220415~220418_자료구조_이진트리(Binary Tree) 구현 * 필요 헤더: LinkedList.h https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는.. hyrule.tistory.com //main.cpp #include "BinaryTree.h" #include //순회 출력을 위한 함수(이진 트리 클래스에서 주소를 받아서 사용할 예정) void OutputOrder(const int& Key, const int& Value, co..
* 필요 헤더: LinkedList.h https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하 hyrule.tistory.com //BinaryTree.h /* [이진트리] * 자식노드가 최대 2개 * 구현방식: 배열기반 or 리스트기반 * 배열기반은 복잡하므로 이진트리로 * 이진트리를 쓰는 이유 : '탐색'이 매우 빠르다 - 추가할때, 삭제할때 규칙이 있음 ex) 루트노드보다 큰건 오른쪽, 작은건 왼쪽에 추가..
