Computer Science/Algorithm (16) 썸네일형 리스트형 [Algorithm] Heap sort (힙정렬) 1. Heap Sort (힙정렬) 힙 정렬은 자료구조 중 하나인 binary heap을 활용하여 정렬하는 방법이다. 데이터를 최대 힙 또는 최소 힙으로 구성하여서 정렬을 진행하는데, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 바이너리 힙을 구성하게 되면 해당 자료구조 내에서 최소값, 또는 최대값을 알 수 있기 때문에 이 값들을 반복해서 찾아 정렬을 진행할 수 있다. 힙정렬을 위해서는 두가지 프로세스를 반복해야한다. 바이너리 힙 구조를 만드는 과정 (heapify) 힙의 root 값을 가져와 정렬된 메모리에 저장하는 과정 위의 두 과정을 트리에 남아있는 데이터가 없을 때까지 반복한다. 2. Heap Sort 구현 맨 처음 max heap 을 구성한다. .. [Algorithm] Merge Sort (병합 정렬) 1. Merge Sort (병합 정렬) 병합 정렬은 divide and conquer를 기반으로 한 정렬 알고리즘이다. 정렬할 배열을 더이상 나누어지지 않을 때까지 반으로 나눈 뒤 다시 병합하면서 비교를 통해 정렬을 진행한다. 병합과정에서 비교하는 두 배열은 각각 이미 정렬되어 있는 배열들이다. 그렇기 때문에 각각 배열의 처음부터 더 작은 값을 선택하는 방식으로 병합하면서 정렬을 진행한다. 병합정렬의 진행 과정은 다음과 같다. divide: 정렬을 진행할 배열의 크기가 1이 될 때까지 대상이 되는 배열을 반으로 나누어 두 개의 부분 배열로 나눈다. conquer: 분할이 완료된 배열들을 재귀적으로 병합을 진행한다. combine: 병합시에 두개로 나누어진 부분 배열들의 값을 비교하여 하나의 정렬된 배열로.. [Algorithm] Insertion Sort (삽입 정렬) 1. Insertion Sort (삽입 정렬) 삽입 정렬은 N개의 원소 배열을 정렬 시에 배열을 정렬이 되어있는 부분과 정렬이 되지 않는 부분 두 부분으로 나누어 비교를 하여 정렬하는 알고리즘이다. 매 정렬 시에 정렬을 하지 않은 부분의 한 원소를 선택해서 정렬이 된 부분과 비교하여 원소의 위치를 찾아서 해당 위치에 삽입하는 방식으로 정렬한다. 삽입 정렬을 통해서 오름차순으로 정렬 시에 다음과 같은 순서를 거친다. 배열의 정렬을 1부터 N까지 반복한다. i-1까지의 값이 정렬되어 있을 때 정렬을 하는 대상이 되는 값이 i번째 값이 된다. 이때 먼저 i-1 번째 값과 비교하여 i-1 번째 값이 더 큰 경우 자리를 바꾼다. 이 과정을 i-1부터 0번까지 비교를 진행하게 되는데, 이때 한칸 앞의 값이 더 작은.. [Algorithm] Bubble Sort (거품 정렬) 1. Bubble Sort (거품 정렬) 거품 정렬은 N개의 원소를 가진 배열을 정렬 시에 인접한 두 원소를 비교하여 정렬하는 방법이다. 시간복잡도는 크지만 구현이 간단하기 때문에 자주 사용된다. 크기 N의 배열을 정렬할 때, 인덱스 0번과 1번, 1번과 2번, ... N-2번과 N-1번의 원소들을 비교하여 자리를 교환해준다. 인접한 원소들의 교환을 한번 수행할 때마다 가장 오른쪽에 배치되는 원소는 올바르게 정렬되어진 값이 된다. 예를 들어 오름차순으로 정렬하는 경우 매 회차마다 가장 큰 수가 오른쪽으로 정렬되어진다. 이를 통해서 매 회차마다 가장 오른쪽으로 정렬된 값은 다음 회차의 정렬의 대상에서 제외된다. 2. Bubble Sort 구현 Bubble Sort는 첫 원소부터 N-i 까지의 원소에 대해서.. [Algorithm] Selection Sort (선택 정렬) 1. Selection Sort (선택 정렬) 선택 정렬은 in-place 비교 정렬 중의 하나로 정렬되지 않은 부분에서 매번 최소값을 가지는 요소를 찾아서 가장 앞으로 자리를 옮기는 방식을 반복하여 정렬을 진행한다. 이 방법을 진행하는 중에는 배열이 최소값들이 순서대로 정렬된 부분과 아직 정렬되지 않은 두 부분으로 나뉘어진다. 정렬되지 않는 리스트에서 최소값을 찾는다. 최소값을 리스트의 가장 앞에 위치한 값과 자리를 바꾼다. 첫번째 값을 제외하고 두번째 값부터 리스트를 지정해서 정렬을 진행한다. 매 정렬마다 정렬되지 않은 리스트의 최소값이 정렬된 리스트 이동하는 방식으로 구현된다. 추가적으로 값을 저장하는 메모리가 필요하지 않기 때문에 공간 복잡도에서 이점을 가지게 된다. 2. Selection Sor.. [Algorithm] BFS 1. BFS (Breadth First Search, 너비 우선 탐색) 그래프 탐색 방법 중의 하나로 하나의 정점으로부터 시작해서 인접한 정점을 먼저 탐색하는 방법이다. 해당 정점과 연결되어있는 정점들 중 하나의 방향으로만 우선 탐색했던 DFS와 달리 BFS는 인접한 정점들을 먼저 탐색하고 이어서 다음으로 인접한 정점들을 탐색하는 방식으로, 깊이가 아닌 너비를 우선으로 탐색하는 방법이다. 주로 특정 정점까지의 최단 경로를 찾고 싶을 때 사용한다. BFS는 인접한 노드들에 대해서 우선적으로 탐색하고 이어서 다음으로 인접한 노드들을 탐색하는 것이 트리 탐색의 level order traversal 과 유사한데, 그래프에서는 사이클이 발생할 수 있기에 방문한 노드를 확인하는 visited 를 구현하여 방문 여.. [Algorithm] DFS 1. DFS (Depth First Search, 깊이 우선 탐색) 그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로 탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다. DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder tr.. [Algorithm] Binary Search Algorithm Binary Search Algorithm (이진 탐색 알고리즘) 이진 탐색 알고리즘은 탐색 알고리즘의 하나로 이미 정렬되어 있는 배열을 대상으로 원하는 값을 찾는 알고리즘이다. 정렬되어 있는 배열의 중간의 값과 타겟이 되는 값을 비교해서 탐색을 진행한다. 중간값과 타겟이 동일하다면 해당 값을 반환한다. 만약 타겟이 되는 값이 중간값보다 큰 경우 중간 값을 기준으로 우측, 작다면 중간 값을 기준으로 좌측의 부분 배열을 대상으로 반복적으로 탐색을 진행한다. 이때 대상이 되는 배열의 왼쪽 인덱스가 오른쪽 인덱스보다 크다면 값이 없는 것으로 판단하여 탐색을 중단한다. 위의 예제 이미지는 정렬되어있는 배열에서 타겟 값인 23을 탐색하려고 한다. 첫번째 과정에서 중간값은 16 이다. 16은 타겟 값인 23 보다 .. 이전 1 2 다음
