DS & Algorithm/theory

병합 정렬(Merge Sort) 이란

분할 정복 병합 정렬을 학습하기 전에 분할정복에 대해 먼저 알아보자. 분할 정복(Devide and Conquer)이란, 문제를 나눠서 각각을 풀고 다시 합병해서 답을 도출하는 알고리즘이다. 총 Devide, Conquer, Combine의 스텝으로 이루어지며 Devide는 현재 문제가 분할이 가능할 때, 2개 이상의 문제로 나누고 Conquer는 Devide를 통해 나눈 문제가 여전히 분할이 가능하면, 분할된 문제에 재차 Devide를 수행함을 의미한다. Combine은 devide and conquer를 수행하고 더이상 나눠지지 않는 문제를 합병해 답을 도출하는 과정을 말한다. 분할 정복을 채택한 알고리즘에는 대표적으로 병합 정렬, 퀵 정렬 등이 있으며 이미 퀵 정렬은 다루었으니 병합 정렬을 살펴보자..

계수 정렬(Counting Sort) 이란

계수 정렬 특정한 조건이 부합할 때, 배열 원소 간 비교하지 않고 정렬하는 알고리즘이다. 특정한 조건이란, 원소들이 정수이며 0~K(K=정수)의 범위 안에 포함될 때를 가정한다. 즉, 데이터 개수가 N개이며, 모두 0이상의 정수이며 데이터 중 최댓값이 K일 때 사용할 수 있다. 계수 정렬은, 각각 데이터가 몇 번 씩 등장했는지를 세는 방식이다. 그래서 가장 큰 데이터의 크기로 배열을 선언해서 0부터 K까지 모든 범위를 포함할 수 있어야 하며, 배열 인덱스를 이용하기 때문에 0이상의 정수를 데이터로 갖는 배열을 가정해준다. 계수 정렬을 수행하는 순서를 살펴보자. 1. 인덱스 K를 참조할 수 있는 K+1 크기의 배열 countArr을 선언하고 모든 인덱스의 값을 0으로 초기화한다. 2. 원본 배열의 첫번째 ..

퀵 정렬(Quick Sort) 이란

퀵 정렬 기준 데이터를 설정하고, 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 알고리즘이다. 퀵 정렬에서 선택한 기준 데이터를 피봇 데이터라고 한다. 다양한 상황에서 이용되는 표준 정렬 알고리즘이며, Merge Sort(병합 정렬)과 마찬가지로 정렬 라이브러리의 근간이 되곤 하는 알고리즘이다. 퀵 정렬의 과정은 다음과 같다. 1. 기준(피봇) 데이터를 설정한다.(기본적인 형태에서는 첫번째 데이터를 피봇으로 삼는다.) 2.1. 배열 처음부터 오른쪽으로 순회하며 피봇보다 큰 데이터의 인덱스를 찾는다. 2.2. 배열 마지막부터 왼쪽으로 역순회하며 피봇보다 작은 데이터의 인덱스를 찾는다. 2.3. 작은 데이터와 큰 데이터를 기준으로, 두 인덱스에 위치한 데이터를 swap 할 때 두 데이터가 오름차순으..

삽입 정렬(Insertion Sort) 이란

삽입 정렬 처리되지 않은 데이터를 적절한 위치에 삽입하는 알고리즘이다. 삽입 정렬에서는 배열 첫번째 원소는 정렬되었다고 판단하며, 두번째 원소부터 어떤 위치로 들어가야 할 지 판단한다. 즉, 두번째 원소부터 시작해서 앞에 있는 원소들과 비교하며 삽입할 위치에 데이터를 삽입하며 정렬하는 알고리즘이다. 삽입 정렬의 과정은 다음과 같다. 1. N번째 인덱스의 값을 저장한다. 2. 1 ~ N-1번째 인덱스에 있는 원소들과 비교하며 적절한 위치를 찾아 삽입한다. 3. 1번 과정과 2번 과정을 반복한다. gif를 통해 이해해보자. 삽입 정렬을 JS 코드를 통해 구현하였다. const arr = [5, 6, 3, 1, 8, 7, 2, 4]; function insertionSort(arr){ const len = a..

선택정렬(Selection Sort) 이란

정렬? 정렬은 데이터를 특정 기준에 따라 순서대로 나열하는 방법이다. 문제 상황에 따라 적절한 정렬 알고리즘을 선정하여 사용해야 한다. 이번 포스팅에서는 정렬 중 알고리즘이 단순한 선택 정렬에 대해서 알아본다. 선택 정렬(Selection Sort) 정해진 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다. 처리되지 않은 데이터 중, 가장 작은 데이터를 선택해 앞의 데이터와 순서를 바꾼다고 이해할 수 있다. 선택 정렬의 과정은 다음과 같다. 1. 처리되지 않은 데이터 중 최소값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 처음 위치를 뺀 나머지 배열을 같은 방식으로 교체한다. gif를 통해 바로 이해해보자. 알고리즘을 JS코드로 구현해봤다. const arr = [4, 6, 3, 2, 0..