Data Structure & Algorithm
-
병합정렬(Merge Sort)Data Structure & Algorithm 2021. 2. 4. 09:04
[아이디어] 정렬하고자 하는 데이터를 분할하되 원소가 하나만 남을 때까지 분할합니다. 정렬할 데이터의 원소가 n개 있다고 할 때 n/2, n/2/2, n/2/2/2 ... 씩 분할해 가다가 원소가 하나만 남게 되는 경우 멈춥니다. 1/2씩 데이터를 분할하였으므로 분할 된 두 데이터를 정렬하여 병합합니다. 두 분할 데이터 각각의 가장 왼쪽 데이터 부터 비교해가며 작은 것이 앞에 오도록 정렬된 데이터로 병합합니다. 2의 과정을 데이터 길이가 n이 될 때까지 반복하면 정렬이 완료됩니다. [특징] 평균 시간복잡도는 O(nlogn)입니다. 최악의 경우에도 O(nlogn)을 보장합니다. 안정적인 시간복잡도를 보장하는 만큼 공간복잡도가 올라가는데, 병합정렬의 공간복잡도는 O(n)입니다. 병합정렬은 안정정렬이므로 동일..
-
계수정렬 (Counting Sort)Data Structure & Algorithm 2021. 1. 30. 08:55
계수는 수를 계산하다는 의미입니다. 계수 정렬에서는 정렬하고자 하는 데이터 안에 동일한 원소가 몇 번 들어 있는지를 계산하여 그 결과를 별도의 배열 또는 리스트에 저장하여 정렬에 사용합니다. hash table과 비슷한 아이디어라고 생각됩니다. [아이디어] 정렬할 데이터를 M이라고 할 때, M에서 가장 큰 값을 V라 합니다. 0 ~ V(총 V+1 개) 사이의 데이터 개수를 저장할 수 있는 배열 또는 리스트 N을 생성하고 N의 각 원소들을 0으로 초기화합니다. 예를 들어 M = [7, 5, 2, 3, 7, 1]이라 할 때 N = [0, 0, 0, 0, 0, 0, 0]이 됩니다. M을 선형으로 탐색하면서 M의 값에 해당하는 N의 인덱스 원소의 값에 1씩 더해갑니다. M의 모든 원소들의 값을 살펴보면 1, 2..
-
퀵정렬(Quick Sort)Data Structure & Algorithm 2021. 1. 28. 18:06
[아이디어] 정렬할 데이터의 가장 좌측 인덱스를 left, 가장 우측 인덱스를 right라고하고 정렬기준이 될 데이터를 pivot이라 합시다. left를 1씩 증가하고 right를 1씩 감소시켜가며 pivot을 기준으로 pivot이하인 경우는 pivot보다 왼편으로 pivot을 초과하는 경우 pivot보다 오른쪽으로 데이터를 이동하여 일부 정렬된 형태의 데이터로 만들어줍니다. 이렇게 만들어진 일부 정렬 형태의 데이터를 pivot 기준으로 분할하여 다시 퀵정렬 함수의 재귀 호출을 통해 정렬해 갑니다. 정렬과정에서 정렬에 필요한 데이터를 반씩 줄여가는 형태가 됩니다. left >= right이 되면 더이상 정렬할 요소가 없다는 것이니 별도의 로직 실행없이 return 합니다. 정렬할 데이터 가운데 pivot..
-
삽입정렬(Insertion Sort)Data Structure & Algorithm 2021. 1. 24. 19:20
[아이디어] 데이터의 가장 앞에 위치한 원소는 정렬 된 것으로 간주합니다. 아직 정렬되지 않은 데이터 중 첫번째 데이터를 시작으로 정렬된 데이터와 비교해서 정렬되지 않은데이터가 작으면 정렬되지 않은 데이터와 비교된 데이터를 교환(swaping)합니다. 만약 두 데이터가 같거나 정렬되지 않은 데이터가 정렬된 데이터보다 크다면 비교를 중지합니다. 인덱스 1 ~ n-1 까지의 모든 요소들에 대해 2번 로직을 실행합니다. [특징] 평균시간복잡도는 O(n²)입니다. 버블, 선택 정렬에 비해 비교적 뛰어난 성능을 보여줍니다. [구현] data = [3, 4, 1, 0, 2, 0] print('not-sorted:', ' '.join(map(str, data))) for i in range(1, len(data)):..
-
선택정렬(Selection Sort)Data Structure & Algorithm 2021. 1. 22. 20:54
[아이디어] 데이터의 정렬되지 않은 첫번째 원소부터 선형탐색으로 가장 작은 값을 찾아 인덱스를 기록합니다. 1에서 찾은 인덱스를 사용하여 가장 작은 값과 정렬되지 않은 첫번째 원소를 서로 교환합니다. 1 ~ 2를 모든 원소 개수 - 1 만큼 반복합니다. [특징] 평균 시간 복잡도는 O(n²)입니다. 동일한 값이 두개 이상일 때 정렬 후 데이터 간 순서가 보장되지 않습니다. 제자리 정렬 알고리즘으로 swapping을 위한 임시 저장 메모리 외에 추가적인 메모리를 필요로 하지 않아 공간 복잡도는 O(1)입니다. [구현] 1. python def selection_sort(data, reverse_order): for i in range(len(data) - 1): index = i for j in range..
-
DFS, BFS with pythonData Structure & Algorithm 2021. 1. 11. 10:07
Depth Frist Search(DFS)와 Breadth First Search(BFS)는 그래프 탐색 알고리즘이다. 각각 특정 순서에 따라 그래프의 노드를 탐색하게 된다. DFS는 stack 또는 재귀호출을 이용하여 구현하고 BFS는 queue를 이용하여 구현한다. 1. DFS 구현방법 stack에 시작 노드를 넣고 해당 노드를 방문했음을 기록한다. stack의 최상단 노드와 인접한 노드 중 아직 방문하지 않은 노드의 존재 여부에 따라 인접한 노드 A가 있으면 stack에 넣고 노드 A를 방문했음을 기록한다. 인접한 노드가 없으면 stack에 대해 pop연산을 진행한다. stack이 empty 상태가 되면 알고리즘을 종료한다. ★ 노드가 stack에 push될 때마다 push되는 노드를 순서대로 리스..
-
그래프의 탐색 DFS, BFSData Structure & Algorithm 2020. 10. 6. 08:20
그래프의 모든 노드를 탐색하는 방법으로 DFS(Depth First Search:깊이 우선 탐색)와 BFS(Breadth First Search:너비 우선 탐색)가 있다. DFS는 stack을 BFS는 queue를 사용하여 각각 구현한다. (stack과 queue에 대해서는 다른 글을 참고) 그래프의 노드를 탐색하기 위해서는 노드간 간선에 의해 연결된 인접한 노드 정보가 필요하며 이 정보들을 행렬(2차원 리스트) 또는 리스트 형태로 저장하여 사용한다. 행렬 형태의 인접 노드 정보를 adjacency matrix라 하고 리스트 형태의 인접 노드 정보를 adjacency list라고 한다. adjacency matrix는 불필요한 정보까지 저장하게 되어 메모리를 낭비하게 되지만 원하는 관계 정보를 빠르게 조..
-
Stack과 QueueData Structure & Algorithm 2020. 9. 28. 19:31
stack과 queue를 java와 python으로 구현해보자. [Stack] stack은 LIFO(Last In First Out)로 동작하는 자료구조다. 일반적으로 함수 호출 시 스택구조를 사용한다. 따라서 스택을 사용해야 하는 알고리즘은 함수의 재귀호출로 대체할 수도 있다. stack with java import java.util.EmptyStackException; public class Stack_New { public static class Node { private final T data; private Node next; public Node(T data) { this.data = data; } public T getData() { return this.data; } public Node..