정렬알고리즘12 위상정렬(Topology Sort) 위상 정렬(Topology Sort) 는 순서가 정해져있는 작업을 차례로 수행할 때 순서를 결정해주기 위해 사용되는 알고리즘입니다. 예시를 바로 볼까요. 다음과 같이 할 일 루틴이 있다고 합시다. 청소나 블로그 작성은 어느것을 먼저 수행하든지 상관이 없지만 점심은 강의를 복습하고 나서야 할 수 있습니다. 이처럼 한 단계를 수행하기 전에 해야하는, 즉 화살표의 개수(조건)를 '진입 차수' 라고 합니다. 이러한 조건들에 부합하는 일직선이 순서를 찾는것이 위상정렬입니다. 출근 -> 청소 -> 블로그 작성 -> 강의듣기 -> 강의 복습 -> 점심먹기 위와 같이 정렬을 수행할 수 있습니다. 그리고 다양한 답이 존재합니다. 그렇기 때문에 더욱 매력적인 알고리즘이라고 할 수 있습니다. 또 위상정렬을 DAG(Direc.. 2020. 6. 12. 계수 정렬(Counting Sort) 이때까지 배운 O(N log N)의 시간복잡도인 선택, 버블, 삽입 정렬 그리고 O(N^2)의 시간복잡도인 퀵, 병합, 힙 정렬을 배웠습니다. 가장 빨랐던 정렬은 아무래도 퀵정렬이었는데요. 이거보다 빠르게 정렬을 하는 계수 정렬에 대해 알아보겠습니다. 다음의 5 이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 5 2 3 1 3 4 4 3 4 2 3 4 3 1 1 2 4 3 3 1 2 3 4 5 1 3 2 4 정렬할 데이터 개수가 30개입니다. 특징은 모든 데이터가 1부터 5 사이입니다. 계수 정렬은 이처럼 적절한 '범위 조건'이 있어야한다는 전제에서 굉장히 빠른 알고리즘입니다. 그 속도는 O(N) 입니다. ( 저도 처음보는 시간복잡도의 속도입니다.) 계수 정렬(Counting Sort)는 단순하게 '.. 2020. 6. 1. 힙정렬 저번주에 공부하긴 했지만 이해하는데 좀 시간이 걸리는 바람에 지금 포스팅합니다. 힙정렬은 퀵정렬과 병합정렬과 더불어 시간복잡도 O(nlogn) 을 가진 정렬입니다. 힙정렬을 이해하기 위해서는 완전 이진 트리를 이해해야하는데요. 이진 트리는 자식노드가 두개 이하 트리를 의미합니다.. 여기서 가장 위에 있는 7은 루트노드(root)입니다. 그리고 8과 5의 부모노드입니다. 2와 3은 8의 자식노드입니다. 가장 밑 부분인 2 3 1 2 는 리프노드(leaf)라고 합니다. 트리는 다양하게 생길 수 있습니다. 이런식도 가능합니다. 그 중에서 이진 트리는 자식노드가 두개 이하인 트리이고 완전 이진트리는 자식노드가 두개인 트리를 의미합니다. 간단하죠? 힙은 이런 완전 이진트리를 사용합니다. 한번 트리를 만들어 볼까요.. 2020. 6. 1. C++ Sort() 사용 클래스 객체를 이용해서 정렬하는 건 실무에서 많이 사용되는 방법이고 프로그래밍 대회에선 실행 시간에 안 좋은 측면 때문에 자주 사용되지 않는다고 합니다. 실제로는 C++에 vector 라이브러리에, pair 를 더 많이 이용합니다. 정렬은 이미 만들어진 훌륭한 라이브러리가 많으니깐 원리를 이해하고 바로 라이브러리를 사용하면 좋겠죠! sort 함수는 라이브러리에 포함되어있고 pair는 라이브러리에 포함되어 있습니다. #include #include using namespace std; //sort 기준을 스스로 정할 수 있음 //단순 데이터 정렬 기법은 현실적이지 않음 bool compare(int a,int b){ return a < b; } int main(void){ int a[10] = {9, 3,.. 2020. 5. 30. 이전 1 2 3 다음
