Merge Sort 배열을 두 부분으로 쪼갠 뒤, 각 배열의 첫번째 요소를 비교해 작은 원소부터 새로운 배열에 넣으며 정렬한다. 배열의 길이가 길 경우, 한번에 정렬하기 어렵기 때문에 재귀적으로 배열을 잘게 자르고 정렬하는 것을 반복한다. 문제를 작은 2개의 문제로 분리한 후, 해결하고 다시 합치는 분할 정복 방법을 사용한다. 시간복잡도는 O(nlog(n)) 구현한 코드 function mergeSort (array) { // array에 원소 1개만 들어있을때 if (array.length < 2) { return array; } let mid = Math.floor(array.length / 2); // 쪼개질 기준점 let front = array.slice(0, mid); // 쪼개진 앞부분 le..

Quick Sort pivot이라는 기준점을 잡은 뒤, 요소가 이 pivot보다 작다면 왼쪽, 크다면 오른쪽으로 자리를 이동시킨다. 문제를 작은 2개의 문제로 분리한 후, 해결하고 다시 합치는 분할 정복 방법을 사용한다. 시간복잡도는 O(nlog(n)) 구현한 코드 function quick(array) { // 임의로 배열의 맨 끝 요소를 pivot으로 설정하고 // pivot을 기준으로 왼쪽 / 오른쪽으로 나누기 // pivot보다 작다면 왼쪽 배열에 / 크다면 오른쪽 배열에 넣기 // 정렬된 배열을 왼쪽, pivot, 오른쪽 순서대로 합쳐서 리턴 if(array.length < 2) { return array; } const pivot = array[array.length-1]; let left =..

Selection Sort 배열에서 최소값을 찾아 가장 앞쪽 인덱스로 보내며 정렬한다. 최소값과 맨 앞쪽 요소의 위치를 교환한다, 시간복잡도는 O(n^2) 구현한 코드 function selection(array) { // array를 돌며 i ~ array.length-1 까지의 요소 중 최소값을 찾기 // 찾았다면 현재 순회중인 array의 가장 앞(i) 에 넣기 // 이미 가장 앞에 있다면 다음 반복으로 넘어간다 // 모두 정렬될 때까지 쭉 반복 for(let i = 0; i < array.length; i++) { let min = Math.min(...array.slice(i)); if(min === array[i]) { continue; } else { let index = array.inde..

Bubble Sort 서로 인접한 요소들의 크기를 비교해서 순서대로 되어 있지 않으면 서로 자리를 바꾼다. 더 큰 쪽의 요소를 계속해서 뒤로 밀어내는 모양이 된다. 시간복잡도는 O(n^2) 가 된다. 구현한 코드 function bubbleSort(array) { // 맨 앞에 있는 요소부터 시작 // 한칸씩 증가해가면서 바로 오른쪽에 있는 요소와 자신을 비교 // 자신이 크다면 자리를 바꾸고 아니라면 그대로 for(let i = 0; i array[j+1]) { let temp = array[j+1]; array[j+1] = array[j]; array[j] ..

## 유클리드 호제법 - 두 수의 최대공약수를 구하는 알고리즘으로, 두 수가 상대방 수를 나누어서 원하는 수를 얻게 된다. - n1 > n2 인 경우에 n1을 n2로 나눈 나머지를 r이라고 한다면 n1, n2의 최대공약수는 n2, r의 최대공약수와 같다. - n2와 r을 다시 원래의 n1, n2의 자리에 넣어 n1을 n2로 나눈 나머지를 r이라고 하면, n1, n2의 최대공약수는 n2, r의 최대공약수와 같게 된다. - 위의 과정을 n1을 n2로 나눈 나머지(아래 코드의 n2자리에 들어오는 수)가 0일 때까지(두 수가 나누어 떨어질 때까지) 반복했을 때, n1자리에는 처음 n1, n2의 최대공약수가 있게 된다. // n1 > n2 const gcd = (n1, n2) => { return n2 === 0..

보호되어 있는 글입니다.