공부하는 블로그

위상 정렬(Topological Sort) ? 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프는 여러 위상 정렬이 가능하다. 위상 정렬 구현(in JAVA) import java.util.ArrayDeque; import java.util.ArrayList; public clas..

힙 정렬(Heap Sort) ? 힙 정렬은 말 그대로 자료구조 중 하나인 힙을 이용하여 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대힙을, 오름차순 정렬을 위해서는 최소힙을 구성하면 된다. 힙에 대한 설명은 아래의 포스팅을 참고하자. Algorithm | 자료구조 : 힙(Heap) Heap ? 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 gongbu-ing.tistory.com 힙의 삭제 연산은 최상위 노드를 삭제한 후 최하위 노드를 최상위로 끌어와 다시 힙의 구조를 만족시키는 방향으로 재정렬 한다. 그러므로 힙의 삭제연산을 이용하여 최상위에 위치한 루트 노..

퀵 정렬(Quick Sort) ? 퀵 정렬은 분할 정복 알고리즘의 하나로 피벗(pivot)을 정한 뒤 피벗의 위치를 확정해가며 정렬한다. 피벗을 선정하는 기준은 가장 왼쪽, 가장 오른쪽, 가운데, 랜덤 등 다양하며 어떤 피벗이 좋은 피벗인지는 확답할 수 없다. 분할 정복은 대개 재귀호출을 이용하여 구현한다. * 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략 퀵 정렬은 O(nlog2n)의 시간복잡도를 가지는 매우 효과적인 정렬 알고리즘으로, 자바 스크립트의 배열 객체의 내장 함수인 sort의 내부 구조도 퀵 정렬을 따른다. 퀵 정렬의 과정은 다음과 같다. 각 반복 과정에서는 재귀호출이 사용된다. 1. 배열의 안에 있는 요소 하나를 ..

선택 정렬 (Selection Sort) ? 선택 정렬은 제자리 정렬 알고리즘 중 하나로 배열의 첫번째 원소를 두번째 원소부터 마지막 원소까지, 그 다음은 두번째 원소를 세번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 수를 배열의 앞에 순서대로 가져다 놓는 정렬이다. 1회전마다 N개의 모든 원소를 전부 검사하며 이를 원소의 갯수(N개)만큼 반복하게 되므로 O(n^2)의 시간복잡도를 가지게 된다. 선택 정렬은 O(N^2)의 시간 복잡도를 가지고 있어 성능이 다른 정렬에 비해 좋지 못하다. 하지만 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용하면 좋다. 성능이 좋은 정렬들은 오히려 30 이하의 작은 수에서는 성능이 안좋은 경우가 있다. 선택정렬 구현 (in JAVA) publ..