Computer Science (42) 썸네일형 리스트형 [Algorithm] Counting Sort (계수정렬) 1. Counting Sort 계수 정렬은 배열의 원소의 개수를 세어 정렬하는 방식의 알고리즘이다. 특정 값을 가진 원소가 몇개인지를 세어 개수를 가지고 정렬을 진행하기 때문에 특정한 범위의 값들을 원소로 가질때 적합하다. 범위가 넓은 경우에는 원소들을 계수하기 위해 할당하는 배열의 크기가 커지는 문제가 발생한다. 2. Counting Sort 구현 배열의 원소들을 각각의 값에 따라 계수하기 위해서 원소들의 개수를 저장할 임시 배열을 할당한다. 이때 임시 배열의 크기는 배열에 저장된 값의 범위에서 가장 큰 값으로 한다. 임시 배열을 생성한 후에는 기존 배열을 처음부터 끝까지 탐색하면서 해당 원소의 값을 인덱스로 가지는 임시 배열의 원소의 값을 하나씩 더해준다. 기존 배열의 탐색이 끝난 뒤에는 임시 배열을.. [Algorithm] Quick Sort (퀵정렬) 1. Quick Sort (퀵정렬) 퀵 정렬은 병합 정렬과 같은 divide and conquer 기반의 알고리즘이다. 정렬시에 한 요소를 pivot으로 지정하고 pivot을 기준으로 배열을 두 부분으로 나눈다. 이때 pivot을 선택하는 방법은 여러가지가 있다. 첫번째 요소를 pivot으로 지정한다. 마지막 요소를 pivot으로 지정한다. 랜덤하게 pivot을 지정한다. 중간에 위치한 요소를 pivot으로 지정한다. 퀵 정렬은 정렬 알고리즘 중 가장 빠른 알고리즘으로 알려져 있지만, 배열의 정렬 상태와 pivot 선택 방법에 따라 worst case에 O(N^2)의 시간 복잡도를 가질 수 있다. 퀵 정렬의 핵심은 pivot을 중심으로 partition을 나누는 과정이다. pivot으로 지정된 요소의 값.. [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 를 구현하여 방문 여.. 이전 1 2 3 4 5 6 다음