짹뚜 스튜디오

합병 정렬 분할 정복 알고리즘 중 하나이고 안정 정렬에 속하는 정렬 알고리즘이다. 알고리즘 합병 정렬은 다음과 같이 진행된다. Divide: 입력으로 받은 배열을 같은 크기의 2개의 배열로 길이가 1이 될 때까지 나눈다. (배열의 길이가 1일 때 배열이 정렬이 된 상태라고 본다.) Conquer: 2개의 정렬된 배열을 하나의 배열로 정렬을 하면서 합친다. 입력으로 받은 배열을 배열의 길이가 1개가 될 때까지 절반으로 나눠준다. 2개의 정렬된 배열을 서로 인덱스 0부터 비교하면서 더 작은 값을 또 다른 배열에 넣어준다. 2개의 배열 중 하나의 배열에서 모든 값을 새로운 배열에 넣을 때까지 반복한다. 만약 하나의 배열의 값들을 모두 넣어주면 남은 배열의 값들은 새로운 배열에 push 한다. 나눠진 모든 배열..

소수란 1 보다 큰 정수 중 약수로 1과 자기 자신만을 가지는 정수이다. 그러므로 임의의 정수가 소수인지를 판별하기 위해서는 2부터 n-1까지의 정수로 나누기를 해서 나머지가 0이 나오는지 안 나오는지로 확인할 수 있다. function isPrime(n){ for(let i = 2; i < n; i++){ if(n % 2 === 0){ return false; } } return true; } 하지만 위 방식으로 하면 시간복잡도가 O(n)이 나온다. 다른 접근 방식으로는 약수의 중심을 구하는 공식을 이용하면 된다. 어느 한 정수의 약수들 중에서 두 개의 약수를 곱해서 해당 정수가 나오는 값끼리 한 쌍으로 묶었을 때 하나의 약수는 무조건 해당 정수의 제곱근보다 작은 수이다. 예를 들어 정수 50의 약수는..

퀵 정렬 분할 정복 알고리즘 중 하나로 평균적으로 매우 빠른 속도를 가지고 있다. 퀵 정렬의 특징으로는 비 균등하게 분할을 한다. 알고리즘 퀵 정렬은 다음과 같이 진행된다. 입력된 배열을 pivot을 기준으로 비균등하게 2개의 배열로 나눈다. pivot을 중심으로 왼쪽에는 pivot보다 작은 요소, 오른쪽에는 pivot보다 큰 요소들로 나눈다. 분할된 배열들을 가지고 다시한번 새로운 pivot을 기준으로 비 균등하게 2개의 배열로 나눈다. 더 이상 분할이 안될때까지 반복적으로 진행한다. // javascript 코드 const quickSort = (arr, left, right) => { if (left >= right) return; let low = left + 1; let high = right;..

삽입 정렬 삽입 정렬은 요소를 앞에서부터 순서대로 이미 정렬된 배열과 비교를 해서 자신의 위치를 찾아서 삽입하는 알고리즘이다. 삽입 정렬은 필요할 때만 삽입을 진행하기 때문에 만약 데이터가 거의 정렬이 된 상태라면 다른 알고리즘보다 빠르게 정렬을 할 수 있다. 그러나 평균적으로 삽입 정렬의 시간 복잡도는 O(n²)이다. 알고리즘 오름차순으로 정렬을 할 때는 다음과 같이 진행한다. 두 번째 요소부터 반복문을 진행한다. 현재 확인할 요소의 앞부분은 이미 정렬이 된 상태이다. 앞부분의 마지막 요소부터 비교를 시작한다. 삽입할 요소보다 큰 요소들을 찾는다. 큰 값을 가진 요소들의 위치를 한 칸 뒤로 옮긴다. 지정한 위치에 삽입할 요소를 넣는다. function insertionSort(arr) { for(let..

해당 글은 모든 자바스크립트 개발자가 알아야 하는 33가지 개념에서 열두 번째인 Bitwise Operators, Type Arrays and Array Buffers 항목을 공부하면서 간단하게 작성한 글이다. 비트마스크란? 컴퓨터가 사용하는 데이터의 최소 단위인 비트를 활용해서 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 비트마스크는 알고리즘보다는 비트를 활용한 테크닉으로 본다. 비트는 0 또는 1만 있을 수 있고 0은 off를 1은 on을 의미한다. 장점 비트 연산을 사용하기 때문에 O(1)이라는 빠른 연산속도를 가진다. 하나의 정수만을 이용해서 다양한 경우의 수를 표현할 수 있기 때문에 메모리 사용량이 적다. (DP 문제에 유용) 비트 연산자를 사용해서 한 줄의 간결한 코드로 원하는 값을 찾을 ..

버블 정렬을 이용해서 오름차순으로 정렬한다면 인접한 두 수를 비교하여 작은 수 를 앞으로 보내면 된다. 내림차순으로 정렬한다면 큰 수를 앞으로 보내면 된다. 이렇게 배열을 한 번 순회할 때마다 마지막 원소가 정렬되는 모습이 거품이 수면 위로 올라가는 모습과 같다고 하여 버블 정렬이라고 한다. 알고리즘은 단순하지만 상당히 비효율적이다. 전체 원소의 개수가 n개 일때, 각 순회 때마다 n-1, n-2,..., 2 ,1번 비교 및 자리 교체가 이루어지기 때문에 시간 복잡도는 O(n²)가 된다. 구현 방법 (javascript) function bubbleSort(arr){ for(let i = 0; i < arr.length; i++){ for(let j = 0; j < arr.length - 1 - i; j..

안정 정렬 (Stable Sort) 안정 정렬이란 중복된 값들이 정렬한 후에도 입력된 순서와 동일하게 유지되는 특성을 말한다. 다음과 같은 카드 배치에서 숫자가 오름차순이 되게 정렬하고자 할 때 중복되는 숫자 7 카드들은 정렬되기 전의 순서가 그대로 유지된 채로 정렬이 완료된다. (하트 -> 스페이드 -> 다이아몬드 순서가 유지된다.) 대표적인 안정 정렬 알고리즘에는 버블 정렬, 삽입 정렬, 병합 정렬이 있다. 불안정 정렬 (Unstable Sort) 불안정 정렬이란 중복된 값들이 정렬한 후에 입력된 순서와 상관없이 무작위로 정렬이 되는 특성을 말한다. 다음과 같은 카드 배치에서 숫자가 오름차순이 되게 정렬하고자 할 때 중복되는 숫자 7 카드들은 정렬되기 전의 순서가 유지되지 않고 무작위로 섞이게 된다...

유클리드 호제법은 두 수의 최대공약수를 구할 때 사용하는 알고리즘이다. 일반적으로 두 수의 최대공약수를 구하려면 일단 두 수를 소인수분해한 후 공통된 소수 중 가장 큰 수를 찾으면 된다. 그러나 수가 커질수록 소인수분해하기 어렵기 때문에 유클리드 호제법을 사용하면 쉽고 효율적으로 구할 수 있다. 구현 방법 유클리드 호제법의 개념은 다음과 같다. 두 자연수 a와 b (a > b), 그리고 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b 와 r의 최대공약수와 같다. GCD(a, b) = GCD(b, r) 위와 같은 방법을 반복해서 r이 0이 될 때 b가 최대공약수가 된다. 이 알고리즘의 시간복잡도는 O(log N)이 된다. 재귀 함수를 사용하면 쉽게 구현할 수 있다. //javascript..

이진 탐색이란 정렬된 리스트에서 탐색하는 범위를 절반으로 줄여가면서 원하는 값을 탐색하는 방법이다. 탐색 범위를 절반으로 줄여가기 때문에 시간 복잡도는 O(logN)이다. 아래 리스트에서 3을 탐색한다고 하면, start 값은 1 end 값은 10이 된다. 그리고 mid 값은 5가 된다. 3이 5보다 작기 때문에 mid 값인 5를 기준으로 왼쪽에 있는 값들을 이용해서 이진 탐색을 반복한다. start 값은 1 end 값은 4가 된다. 그리고 mid 값은 2가 된다. 3이 2보다 크기 때문에 mid 값인 2를 기준으로 오른쪽에 있는 값들을 이용해서 이진 탐색을 반복한다. start 값은 3 end 값은 4가 된다. 그리고 mid 값은 3이 되고 찾고하는 값이기 때문에 탐색을 종료한다 이진 탐색을 구현하는 ..

그리디 (탐욕) 알고리즘은 현재 상황에서 최적의 해를 찾는 알고리즘이다. 알고리즘 구현은 단순하지만 단점도 존재한다. A 위치에서 시작해서 해당 그래프의 최고점을 찾는다고 했을 때, A에서 최적의 선택은 C 방향으로 올라가는 것이다. 그러나 그래프 전체를 봤을 때는 B가 최고점이다. 이렇듯 그리디 알고리즘은 항상 최적의 결과를 찾아내지는 못하지만 최적에 근사한 결과를 찾아낼 수 있다. 과목 선택 문제에서 그리디 알고리즘을 사용할 수 있다. 예를 들어 한 강의실에서 최대한 많은 수업을 진행할 수 있는 경우를 찾아야 한다고 하자. 수업 시작 시간과 종료 시간이 주어줬을 때 다음과 같은 순서로 문제를 해결할 수 있다. 수업이 가장 빨리 끝나는 과목을 찾는다. 해당 과목이 끝난 후에 다음으로 가장 빨리 끝나는 ..