오늘은 병합 정렬에 대하여 알아보고자 합니다. 개요 여라개의 정렬된 자료의 집합을 병합하며 한개의 정렬된 집합을 만드는 방식을 병합 정렬이라고 합니다. 전체 원소들에 대하여 정렬을 수행하는게 아니고, 부분적으로 집합을 분할하며 각 집합에 대해 정렬 작업을 완성하고 정렬된 집합들을 다시 병합하면서 하는 분할 정복(divde and conquer)기...

오늘은 셀 정렬에 대하여 알아보고자 합니다. 개요 일정한 간격으로 떨어져 있는 자료들을 집합을 구성하고, 각 집합에 있는 원소들에 대해 삽입 정렬를 수행하는 것을 반복하면서 전체 원소를 정렬하는 방식을 셀 정렬이라고 합니다. 전체 원소에 대하여 삽입 정렬를 시도하는 것보다 부분 집합으로 나누어 정렬하게 되면 비교와 교환 연산의 횟수가 감소합니다....

오늘은 삽입 정렬에 대하여 알아보려고 합니다. 개요 정렬되어 있는 집합에 정렬할 새로운 원소들을 알맞은 위치를 찾아 삽입하는 방식을 삽입 정렬이라고 합니다. 기본적으로 정렬할 자료가 두개의 정렬된 집합과 정렬되지 않은 집합이 있다고 가정합니다. 앞부분 원소부터 정렬을 수행하면서 정렬된 앞부분의 원소가 정렬된 집합으로 되고, 아직 정렬되지 않은 ...

오늘은 퀵 정렬에 대하여 알아보도록 하겠습니다. 개요 퀵 정렬은 정렬할 전체 원소에 대하여 정렬을 수행하는 방식이 아니고, 기준값을 먼저 잡고전체 원소에서 왼쪽 집합과 오른쪽 집합을 분할합니다. 왼쪽 집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 집합에는 기준값보다 큰 원소들을 이동시킵니다. 이때 일반적으로 전체 원소중에 가운데 원소를 피...

오늘은 버블 정렬에 대하여 알아보도록 하겠습니다. 개요 인접한 두개의 원소를 비교하여 자리를 교환하는 방식을 버블 정렬이라고 하며, 첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막 자리로 정렬되게 됩니다. 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하게되면서 물 속에서 물 위로 올라오는 물방울 ...

오늘은 정렬 방법중 하나인 선택 정렬에 대하여 알아보려고 합니다. 개요 전체 원소에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로서 선택 정렬이라고 합니다. 전체 원소중에서 가장 작은 원소를 찾아 선택한 뒤, 첫번째 원소와 자리를 교환하게 됩니다. 그리고 두번째로 작은 원소를 선택하고 두번째 자리 원소와 교환하게 되는 과정을 반복...

순서없이 배열되어 있는 자료를 작은 것부터 큰 것까지 오름차순으로 정렬하거나, 큰 것부터 작은 것까지 내림차순으로 재배열하는 것을 정렬이라고 합니다. 분류 정렬이 실행하는 방식과 정렬이 수행되는 장소에 따라서 정렬 방식을 분류할 수 있습니다. 실행 방식 정렬이 실행되는 방식에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있습니다. 비교식 정렬...

오늘은 최소 비용 신장 트리 Kruskal 알고리즘에 대하여 알아보겠습니다. 개요 Kruskal 알고리즘은 가중치가 높은 간선을 제거하며 최소 비용 신장 트리, 즉 minimum cost spanning tree를 만들거나, 가중치가 낮은 간선을 삽입하면서 minimum cost spanning tree를 만듭니다. 첫번째 알고리즘 우선 높은 ...

오늘은 신장 트리에 대하여 알아보겠습니다. 개요 신장 트리는 n개의 정점으로 이루어진 무방향 그래프 g에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리입니다. 링크드 리스트 링크드 리스트에서 순회를 하게 되면, n-1개의 간선을 이동하며 모든 정점을 방문하면서 신장 트리를 만들게 됩니다. 종류 깊이 우선 탐색을 이용하여 생성된 ...

오늘은 너비우선탐색에 대하여 알아보고자 합니다. 개요 너비우선탐색,즉 BFS는 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 뒤에 다시 방문했던 정점을 시점으로 하여 인접한 정점들을 차례대로 방문하는 방식입니다. 간단히 말하자면, 가까운 정점들을 먼저 방문하고 멀리있는 정점은 나중에 방문하는 순회 방식입니다. 근처에 있는 정점들을 차례대...