javascript-algorithms

JavaScript 알고리즘 및 자료 구조

CI codecov

이 저장소에는 많이 알려진 알고리즘 및 자료 구조의 Javascript 기반 예제를 담고 있습니다.

각 알고리즘과 자료 구조에 대해 연관되어있는 설명이 README에 작성되어 있으며, 링크를 통해 더 자세한 설명을 만날 수 있습니다. (관련된 YouTube 영상도 포함).

Read this in other languages: English, 简体中文, 繁體中文, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana

자료 구조

자료 구조는 데이터를 특정 방식으로 구성하고 저장함으로써 더 효율적으로 접근하고 수정할 수 있게 해줍니다. 간단히 말해, 자료 구조는 데이터 값들, 데이터 간의 관계, 그리고 데이터를 다룰 수 있는 함수와 작업의 모임입니다.

B - 입문자, A - 숙련자

알고리즘

알고리즘은 어떤 종류의 문제를 풀 수 있는 정확한 방법이며, 일련의 작업을 정확하게 정의해 놓은 규칙들입니다.

B - 입문자, A - 숙련자

주제별 알고리즘

패러다임별 알고리즘

알고리즘 패러다임 이란, 알고리즘이 주어진 문제를 해결하기 위해 채택한 기초가 되는 일반적인 방법 혹은 접근법입니다. 알고리즘이 해결하는 문제나 알고리즘의 동작 방식이 완전히 다르더라도,알고리즘의 동작 원칙이 같으면 같은 패러다음을 사용했다고 말할 수 있으며, 주로 알고리즘을 구분하는 기준으로 쓰인다. 알고리즘이 일반적인 컴퓨터의 프로그램에 대한 개념보다 보다 더 추상적인 개념인 것처럼 알고리즘의 패러다임은 명확히 정의된 수학적 실체가 있는 것이 아니기 때문에 그 어떤 알고리즘의 개념보다도 훨씬 추상적인 개념입니다.

이 저장소의 사용법

모든 종속 모듈들 설치

npm install

ESLint 실행

코드의 품질을 확인 할 수 있습니다.

npm run lint

모든 테스트 실행

npm test

이름을 통해 특정 테스트 실행

npm test -- 'LinkedList'

Playground

./src/playground/playground.js 파일을 통해 자료 구조와 알고리즘을 작성하고 ./src/playground/__test__/playground.test.js에 테스트를 작성할 수 있습니다.

그리고 간단하게 아래 명령어를 통해 의도한대로 동작하는지 확인 할 수 있습니다.:

npm test -- 'playground'

유용한 정보

참고

▶ Data Structures and Algorithms on YouTube

Big O 표기

Big O 표기로 표시한 알고리즘의 증가 양상입니다.

Big O graphs

Source: Big O Cheat Sheet.

아래는 가장 많이 사용되는 Big O 표기와 입력 데이터 크기에 따른 성능을 비교한 표입니다.

Big O 표기 10 개 일때 100 개 일때 1000 개 일때
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

자료 구조 작업별 복잡도

자료 구조 접근 검색 삽입 삭제 비고
배열 1 n n n  
스택 n n 1 1  
n n 1 1  
연결 리스트 n n 1 1  
해시 테이블 - n n n 완벽한 해시 함수의 경우 O(1)
이진 탐색 트리 n n n n 균형 트리의 경우 O(log(n))
B-트리 log(n) log(n) log(n) log(n)  
Red-Black 트리 log(n) log(n) log(n) log(n)  
AVL 트리 log(n) log(n) log(n) log(n)  
Bloom Filter - 1 1 - 거짓 양성이 탐색 중 발생 가능

정렬 알고리즘 복잡도

이름 최적 평균 최악 메모리 동일값 순서유지 비고
거품 정렬 n n2 n2 1 Yes  
삽입 정렬 n n2 n2 1 Yes  
선택 정렬 n2 n2 n2 1 No  
힙 정렬 n log(n) n log(n) n log(n) 1 No  
병합 정렬 n log(n) n log(n) n log(n) n Yes  
퀵 정렬 n log(n) n log(n) n2 log(n) No 퀵 정렬은 보통 제자리(in-place)로 O(log(n)) 스택공간으로 수행됩니다.
셸 정렬 n log(n) 간격 순서에 영향을 받습니다. n (log(n))2 1 No  
계수 정렬 n + r n + r n + r n + r Yes r - 배열내 가장 큰 수
기수 정렬 n * k n * k n * k n + k Yes k - 키값의 최대 길이