javascript-algorithms - GitLite

KO | EN

gitlite — search

#python #ai #typescript #golang #machine-learning #linux #macos #java #cli #kubernetes #pytorch #security #ios #open-source

javascript-algorithms

(★ 196,529)

📝 JavaScript로 구현한 알고리즘과 자료 구조 모음으로, 상세한 설명과 추가 읽기 자료 링크를 제공합니다.

파일 탐색기

최종 버전 다운로드 (.zip)

# 설치 가이드

1. 코드 내려받기

git clone https://github.com/trekhleb/javascript-algorithms

깃허브에서 프로젝트 코드 전체를 내 컴퓨터로 내려받습니다.

cd javascript-algorithms

방금 내려받은 프로젝트 폴더 안으로 이동합니다.

2. Node.js

쉬움 추천

사전 준비물

Git GitHub에서 프로젝트 코드를 내려받으려면 필요합니다.
Node.js npm 명령어를 쓰려면 Node.js가 설치되어 있어야 합니다. LTS(장기지원) 버전을 추천합니다.

npm install

package.json에 명시된 라이브러리들을 내려받아 설치합니다.

npm run lint

이 명령어를 터미널에 그대로 입력해 실행하세요.

npm test

이 명령어를 터미널에 그대로 입력해 실행하세요.

npm test -- 'LinkedList'

이 명령어를 터미널에 그대로 입력해 실행하세요.

npm i

이 명령어를 터미널에 그대로 입력해 실행하세요.

✅ 명령어 실행 후 터미널에 나타나는 주소(보통 http://localhost:3000 형태)를 브라우저에서 열어보세요.

이 레포의 README에 적힌 실제 명령어를 그대로 가져왔습니다.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# JavaScript Algorithms and Data Structures

> 🇺🇦 우크라이나가 러시아 군대에 의해 [공격받고 있습니다](https://war.ukraine.ua/). 민간인들이 희생되고 주거 지역이 폭격당하고 있습니다.
> - 우크라이나 지원 방법:
>   - [Serhiy Prytula Charity Foundation](https://prytulafoundation.org/en/)
>   - [Come Back Alive Charity Foundation](https://savelife.in.ua/en/donate-en/)
>   - [National Bank of Ukraine](https://bank.gov.ua/en/news/all/natsionalniy-bank-vidkriv-spetsrahunok-dlya-zboru-koshtiv-na-potrebi-armiyi)
> - 더 자세한 정보: [war.ukraine.ua](https://war.ukraine.ua/) 및 [우크라이나 외무부(MFA of Ukraine)](https://twitter.com/MFA_Ukraine)

<hr/>

[![CI](https://github.com/trekhleb/javascript-algorithms/workflows/CI/badge.svg)](https://github.com/trekhleb/javascript-algorithms/actions?query=workflow%3ACI+branch%3Amaster)
[![codecov](https://codecov.io/gh/trekhleb/javascript-algorithms/branch/master/graph/badge.svg)](https://codecov.io/gh/trekhleb/javascript-algorithms)
![repo size](https://img.shields.io/github/repo-size/trekhleb/javascript-algorithms.svg)

이 저장소는 널리 쓰이는 다양한 알고리즘과 자료 구조의 JavaScript 기반 예제 구현을 담고 있습니다.

각 알고리즘과 자료 구조는 관련 설명 및 (YouTube 동영상을 포함한) 추가 학습 자료 링크가 포함된 별도의 README를 가지고 있습니다.

_다른 언어로 읽기:_
[_简体中文_](README.zh-CN.md),
[_繁體中文_](README.zh-TW.md),
[_한국어_](README.ko-KR.md),
[_日本語_](README.ja-JP.md),
[_Polski_](README.pl-PL.md),
[_Français_](README.fr-FR.md),
[_Español_](README.es-ES.md),
[_Português_](README.pt-BR.md),
[_Русский_](README.ru-RU.md),
[_Türkçe_](README.tr-TR.md),
[_Italiano_](README.it-IT.md),
[_Bahasa Indonesia_](README.id-ID.md),
[_Українська_](README.uk-UA.md),
[_Arabic_](README.ar-AR.md),
[_Tiếng Việt_](README.vi-VN.md),
[_Deutsch_](README.de-DE.md),
[_Uzbek_](README.uz-UZ.md),
[_עברית_](README.he-IL.md)

## Data Structures

자료 구조란 데이터에 효율적으로 접근하고 수정할 수 있도록 컴퓨터 내에서 데이터를 조직하고 저장하는 특정한 방식입니다. 더 정확히 말하자면, 자료 구조는 데이터 값들의 모음이며, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 연산들의 집합입니다.

각 자료 구조에는 고유한 트레이드오프(trade-off)가 존재한다는 점을 기억하세요. 따라서 구현 방법 자체보다는 특정 자료 구조를 선택하는 이유에 더 주목해야 합니다.

`B` - 초급 (Beginner), `A` - 고급 (Advanced)

* `B` [Linked List](src/data-structures/linked-list)
* `B` [Doubly Linked List](src/data-structures/doubly-linked-list)
* `B` [Queue](src/data-structures/queue)
* `B` [Stack](src/data-structures/stack)
* `B` [Deque](src/data-structures/deque) - 양방향 큐 (double-ended queue)
* `B` [Hash Table](src/data-structures/hash-table)
* `B` [Heap](src/data-structures/heap) - 최대 힙 및 최소 힙 버전
* `B` [Priority Queue](src/data-structures/priority-queue)
* `A` [Trie](src/data-structures/trie)
* `A` [Tree](src/data-structures/tree)
  * `A` [Binary Search Tree](src/data-structures/tree/binary-search-tree)
  * `A` [AVL Tree](src/data-structures/tree/avl-tree)
  * `A` [Red-Black Tree](src/data-structures/tree/red-black-tree)
  * `A` [Segment Tree](src/data-structures/tree/segment-tree) - 최소/최대/합 구간 쿼리 예제 포함
  * `A` [Fenwick Tree](src/data-structures/tree/fenwick-tree) (Binary Indexed Tree)
* `A` [Graph](src/data-structures/graph) (방향 및 무방향 그래프 모두)
* `A` [Disjoint Set](src/data-structures/disjoint-set) - 상호 배타적 집합(union-find) 자료 구조 또는 merge-find 집합
* `A` [Bloom Filter](src/data-structures/bloom-filter)
* `A` [LRU Cache](src/data-structures/lru-cache/) - 가장 오랫동안 참조되지 않은 항목을 교체하는 (LRU) 캐시

## Algorithms

알고리즘은 일련의 문제를 해결하기 위한 명확한 절차의 명세입니다. 이는 일련의 연산 순서를 정밀하게 정의하는 규칙들의 모음입니다.

`B` - 초급 (Beginner), `A` - 고급 (Advanced)

### 주제별 알고리즘 (Algorithms by Topic)

* **수학 (Math)**
  * `B` [Bit Manipulation](src/algorithms/math/bits) - 비트 설정/조회/업데이트/클리어, 2를 곱하기/나누기, 음수 만들기 등
  * `B` [Binary Floating Point](src/algorithms/math/binary-floating-point) - 부동소수점 숫자의 이진 표현
  * `B` [Factorial](src/algorithms/math/factorial)
  * `B` [Fibonacci Number](src/algorithms/math/fibonacci) - 고전적 방식 및 닫힌 형태(closed-form) 버전
  * `B` [Prime Factors](src/algorithms/math/prime-factors) - 소인수 분해 및 하디-라마누간(Hardy-Ramanujan) 정리를 이용한 개수 계산
  * `B` [Primality Test](src/algorithms/math/primality-test) (시도 나눗셈 방법)
  * `B` [Euclidean Algorithm](src/algorithms/math/euclidean-algorithm) - 최대공약수(GCD) 계산
  * `B` [Least Common Multiple](src/algorithms/math/least-common-multiple) (LCM) - 최소공배수
  * `B` [Sieve of Eratosthenes](src/algorithms/math/sieve-of-eratosthenes) - 주어진 한도까지의 모든 소수 찾기
  * `B` [Is Power of Two](src/algorithms/math/is-power-of-two) - 숫자가 2의 거듭제곱인지 확인 (나이브 및 비트 연산 알고리즘)
  * `B` [Pascal's Triangle](src/algorithms/math/pascal-triangle) - 파스칼의 삼각형
  * `B` [Complex Number](src/algorithms/math/complex-number) - 복소수 및 기본 연산
  * `B` [Radian & Degree](src/algorithms/math/radian) - 라디안과 각도 간의 상호 변환
  * `B` [Fast Powering](src/algorithms/math/fast-powering) - 빠른 거듭제곱
  * `B` [Horner's method](src/algorithms/math/horner-method) - 호너의 방법 (다항식 값 계산)
  * `B` [Matrices](src/algorithms/math/matrix) - 행렬 및 기본 행렬 연산 (곱셈, 전치 등)
  * `B` [Euclidean Distance](src/algorithms/math/euclidean-distance) - 두 점/벡터/행렬 간의 유클리드 거리
  * `A` [Integer Partition](src/algorithms/math/integer-partition) - 정수 분할
  * `A` [Square Root](src/algorithms/math/square-root) - 뉴턴의 방법(Newton's method)을 이용한 제곱근
  * `A` [Liu Hui π Algorithm](src/algorithms/math/liu-hui) - N각형을 이용한 원주율(π) 근사값 계산
  * `A` [Discrete Fourier Transform](src/algorithms/math/fourier-transform) - 이산 푸리에 변환 (시간에 대한 함수를 구성 주파수들로 분해)
* **집합 (Sets)**
  * `B` [Cartesian Product](src/algorithms/sets/cartesian-product) - 데카르트 곱 (여러 집합의 곱집합)
  * `B` [Fisher–Yates Shuffle](src/algorithms/sets/fisher-yates) - 유한 시퀀스의 무작위 순열 생성
  * `A` [Power Set](src/algorithms/sets/power-set) - 멱집합 (집합의 모든 부분집합, 비트 연산, 백트래킹 및 캐스케이딩 솔루션)
  * `A` [Permutations](src/algorithms/sets/permutations) (중복 허용 및 비허용 순열)
  * `A` [Combinations](src/algorithms/sets/combinations) (중복 허용 및 비허용 조합)
  * `A` [Longest Common Subsequence](src/algorithms/sets/longest-common-subsequence) (LCS) - 최장 공통 부분 수열
  * `A` [Longest Increasing Subsequence](src/algorithms/sets/longest-increasing-subsequence) - 최장 증가 부분 수열
  * `A` [Shortest Common Supersequence](src/algorithms/sets/shortest-common-supersequence) (SCS) - 최단 공통 슈퍼수열
  * `A` [Knapsack Problem](src/algorithms/sets/knapsack-problem) - "0/1" 배낭 문제 및 "Unbounded" 배낭 문제
  * `A` [Maximum Subarray](src/algorithms/sets/maximum-subarray) - 최대 부분 배열 (브루트 포스 및 다이나믹 프로그래밍(카단 알고리즘) 버전)
  * `A` [Combination Sum](src/algorithms/sets/combination-sum) - 특정 합을 만드는 모든 조합 찾기
* **문자열 (Strings)**
  * `B` [Hamming Distance](src/algorithms/string/hamming-distance) - 해밍 거리 (기호가 다른 위치의 개수)
  * `B` [Palindrome](src/algorithms/string/palindrome) - 회문 확인 (문자열을 뒤집어도 같은지 확인)
  * `A` [Levenshtein Distance](src/algorithms/string/levenshtein-distance) - 레벤슈타인 거리 (두 시퀀스 간의 최소 편집 거리)
  * `A` [Knuth–Morris–Pratt Algorithm](src/algorithms/string/knuth-morris-pratt) (KMP Algorithm) - 부분 문자열 검색 (패턴 매칭)
  * `A` [Z Algorithm](src/algorithms/string/z-algorithm) - 부분 문자열 검색 (패턴 매칭)
  * `A` [Rabin Karp Algorithm](src/algorithms/string/rabin-karp) - 라빈-카프 부분 문자열 검색
  * `A` [Longest Common Substring](src/algorithms/string/longest-common-substring) - 최장 공통 부분 문자열
  * `A` [Regular Expression Matching](src/algorithms/string/regular-expression-matching) - 정규 표현식 매칭
* **검색 (Searches)**
  * `B` [Linear Search](src/algorithms/search/linear-search) - 선형 검색
  * `B` [Jump Search](src/algorithms/search/jump-search) (또는 블록 검색) - 정렬된 배열에서의 검색
  * `B` [Binary Search](src/algorithms/search/binary-search) - 이진 검색 (정렬된 배열)
  * `B` [Interpolation Search](src/algorithms/search/interpolation-search) - 보간 검색 (균등 분포된 정렬된 배열에서의 검색)
* **정렬 (Sorting)**
  * `B` [Bubble Sort](src/algorithms/sorting/bubble-sort) - 버블 정렬
  * `B` [Selection Sort](src/algorithms/sorting/selection-sort) - 선택 정렬
  * `B` [Insertion Sort](src/algorithms/sorting/insertion-sort) - 삽입 정렬
  * `B` [Heap Sort](src/algorithms/sorting/heap-sort) - 힙 정렬
  * `B` [Merge Sort](src/algorithms/sorting/merge-sort) - 합병 정렬
  * `B` [Quicksort](src/algorithms/sorting/quick-sort) - 퀵 정렬 (in-place 및 non-in-place 구현)
  * `B` [Shellsort](src/algorithms/sorting/shell-sort) - 셸 정렬
  * `B` [Counting Sort](src/algorithms/sorting/counting-sort) - 계수 정렬
  * `B` [Radix Sort](src/algorithms/sorting/radix-sort) - 기수 정렬
  * `B` [Bucket Sort](src/algorithms/sorting/bucket-sort) - 버킷 정렬
* **연결 리스트 (Linked Lists)**
  * `B` [Straight Traversal](src/algorithms/linked-list/traversal) - 순방향 순회
  * `B` [Reverse Traversal](src/algorithms/linked-list/reverse-traversal) - 역방향 순회
* **트리 (Trees)**
  * `B` [Depth-First Search](src/algorithms/tree/depth-first-search) (DFS) - 깊이 우선 탐색
  * `B` [Breadth-First Search](src/algorithms/tree/breadth-first-search) (BFS) - 너비 우선 탐색
* **그래프 (Graphs)**
  * `B` [Depth-First Search](src/algorithms/graph/depth-first-search) (DFS) - 깊이 우선 탐색
  * `B` [Breadth-First Search](src/algorithms/graph/breadth-first-search) (BFS) - 너비 우선 탐색
  * `B` [Kruskal’s Algorithm](src/algorithms/graph/kruskal) - 가중치가 있는 무방향 그래프의 최소 신장 트리(MST) 찾기
  * `A` [Dijkstra Algorithm](src/algorithms/graph/dijkstra) - 단일 정점에서 모든 그래프 정점까지의 최단 경로 찾기
  * `A` [Bellman-Ford Algorithm](src/algorithms/graph/bellman-ford) - 단일 정점에서 모든 그래프 정점까지의 최단 경로 찾기
  * `A` [Floyd-Warshall Algorithm](src/algorithms/graph/floyd-warshall) - 모든 정점 쌍 간의 최단 경로 찾기
  * `A` [Detect Cycle](src/algorithms/graph/detect-cycle) - 사이클 감지 (방향 및 무방향 그래프 모두, DFS 및 상호 배타적 집합 기반 버전)
  * `A` [Prim’s Algorithm](src/algorithms/graph/prim) - 가중치가 있는 무방향 그래프의 최소 신장 트리(MST) 찾기
  * `A` [Topological Sorting](src/algorithms/graph/topological-sorting) - 위상 정렬 (DFS 방식)
  * `A` [Articulation Points](src/algorithms/graph/articulation-points) - 단절점 (타잔(Tarjan) 알고리즘, DFS 기반)
  * `A` [Bridges](src/algorithms/graph/bridges) - 단절선 (DFS 기반 알고리즘)
  * `A` [Eulerian Path and Eulerian Circuit](src/algorithms/graph/eulerian-path) - 오일러 경로 및 오일러 순환 (플루리(Fleury) 알고리즘 - 모든 간선을 정확히 한 번 방문)
  * `A` [Hamiltonian Cycle](src/algorithms/graph/hamiltonian-cycle) - 해밀턴 순환 (모든 정점을 정확히 한 번 방문)
  * `A` [Strongly Connected Components](src/algorithms/graph/strongly-connected-components) - 강한 연결 요소 (코사라주(Kosaraju) 알고리즘)
  * `A` [Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - 외판원 순회 문제 (모든 도시를 방문하고 출발지로 돌아오는 최단 경로)
* **암호학 (Cryptography)**
  * `B` [Polynomial Hash](src/algorithms/cryptography/polynomial-hash) - 다항식 기반 롤링 해시 함수
  * `B` [Rail Fence Cipher](src/algorithms/cryptography/rail-fence-cipher) - 메시지 인코딩을 위한 전치 암호 알고리즘
  * `B` [Caesar Cipher](src/algorithms/cryptography/caesar-cipher) - 시저 암호 (단순 치환 암호)
  * `B` [Hill Cipher](src/algorithms/cryptography/hill-cipher) - 선형대수학에 기반한 치환 암호
* **머신러닝 (Machine Learning)**
  * `B` [NanoNeuron](https://github.com/trekhleb/nano-neuron) - 기계가 실제로 학습하는 방식을 보여주는 7개의 간단한 JS 함수 (순전파/역전파)
  * `B` [k-NN](src/algorithms/ml/knn) - k-최근접 이웃 분류 알고리즘
  * `B` [k-Means](src/algorithms/ml/k-means) - k-평균 클러스터링 알고리즘
* **이미지 처리 (Image Processing)**
  * `B` [Seam Carving](src/algorithms/image-processing/seam-carving) - 내용 기반 이미지 크기 조절 알고리즘
* **통계 (Statistics)**
  * `B` [Weighted Random](src/algorithms/statistics/weighted-random) - 가중치에 기반하여 목록에서 무작위 항목 선택
* **진화 알고리즘 (Evolutionary algorithms)**
  * `A` [Genetic algorithm](https://github.com/trekhleb/self-parking-car-evolution) - 자율 주차 차량 학습에 유전 알고리즘이 적용될 수 있음을 보여주는 예제
* **기타 (Uncategorized)**
  * `B` [Tower of Hanoi](src/algorithms/uncategorized/hanoi-tower) - 하노이의 탑
  * `B` [Square Matrix Rotation](src/algorithms/uncategorized/square-matrix-rotation) - 정사각 행렬 회전 (in-place 알고리즘)
  * `B` [Jump Game](src/algorithms/uncategorized/jump-game) - 점프 게임 (백트래킹, 다이나믹 프로그래밍(하향식 + 상향식) 및 그리디 예제)
  * `B` [Unique Paths](src/algorithms/uncategorized/unique-paths) - 고유한 경로 (백트래킹, 다이나믹 프로그래밍 및 파스칼의 삼각형 기반 예제)
  * `B` [Rain Terraces](src/algorithms/uncategorized/rain-terraces) - 빗물 모으기 문제 (다이나믹 프로그래밍 및 브루트 포스 버전)
  * `B` [Recursive Staircase](src/algorithms/uncategorized/recursive-staircase) - 계단 오르기 (꼭대기에 도달하는 방법의 수 계산, 4가지 솔루션)
  * `B` [Best Time To Buy Sell Stocks](src/algorithms/uncategorized/best-time-to-buy-sell-stocks) - 주식 매수/매도 최적 시기 (분할 정복 및 원패스(one-pass) 예제)
  * `B` [Valid Parentheses](src/algorithms/stack/valid-parentheses) - 유효한 괄호 확인 (스택 사용)
  * `A` [N-Queens Problem](src/algorithms/uncategorized/n-queens) - N-퀸 문제
  * `A` [Knight's Tour](src/algorithms/uncategorized/knight-tour) - 나이트의 순회

### 패러다임별 알고리즘 (Algorithms by Paradigm)

알고리즘 패러다임은 알고리즘 클래스의 설계를 뒷받침하는 일반적인 방법이나 접근 방식입니다. 컴퓨터 프로그램이 알고리즘의 상위 추상화이듯, 패러다임은 알고리즘 개념보다 한 단계 더 높은 추상화입니다.

* **브루트 포스 (Brute Force)** - 모든 가능성을 확인하고 최선의 솔루션을 선택합니다.
  * `B` [Linear Search](src/algorithms/search/linear-search)
  * `B` [Rain Terraces](src/algorithms/uncategorized/rain-terraces) - 빗물 모으기 문제
  * `B` [Recursive Staircase](src/algorithms/uncategorized/recursive-staircase) - 꼭대기에 도달하는 방법의 수 계산
  * `A` [Maximum Subarray](src/algorithms/sets/maximum-subarray)
  * `A` [Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - 모든 도시를 방문하고 출발지로 돌아오는 최단 경로
  * `A` [Discrete Fourier Transform](src/algorithms/math/fourier-transform) - 이산 푸리에 변환
* **그리디 (Greedy)** - 미래를 고려하지 않고 현재 시점에서 가장 좋은 옵션을 선택합니다.
  * `B` [Jump Game](src/algorithms/uncategorized/jump-game)
  * `A` [Unbound Knapsack Problem](src/algorithms/sets/knapsack-problem)
  * `A` [Dijkstra Algorithm](src/algorithms/graph/dijkstra) - 모든 그래프 정점까지의 최단 경로 찾기
  * `A` [Prim’s Algorithm](src/algorithms/graph/prim) - 가중치가 있는 무방향 그래프의 최소 신장 트리(MST) 찾기
  * `A` [Kruskal’s Algorithm](src/algorithms/graph/kruskal) - 가중치가 있는 무방향 그래프의 최소 신장 트리(MST) 찾기
* **분할 정복 (Divide and Conquer)** - 문제를 더 작은 부분으로 나누고 해당 부분들을 해결합니다.
  * `B` [Binary Search](src/algorithms/search/binary-search)
  * `B` [Tower of Hanoi](src/algorithms/uncategorized/hanoi-tower)
  * `B` [Pascal's Triangle](src/algorithms/math/pascal-triangle)
  * `B` [Euclidean Algorithm](src/algorithms/math/euclidean-algorithm) - 최대공약수(GCD) 계산
  * `B` [Merge Sort](src/algorithms/sorting/merge-sort)
  * `B` [Quicksort](src/algorithms/sorting/quick-sort)
  * `B` [Tree Depth-First Search](src/algorithms/tree/depth-first-search) (DFS)
  * `B` [Graph Depth-First Search](src/algorithms/graph/depth-first-search) (DFS)
  * `B` [Matrices](src/algorithms/math/matrix) - 다양한 형태의 행렬 생성 및 순회
  * `B` [Jump Game](src/algorithms/uncategorized/jump-game)
  * `B` [Fast Powering](src/algorithms/math/fast-powering)
  * `B` [Best Time To Buy Sell Stocks](src/algorithms/uncategorized/best-time-to-buy-sell-stocks) - 분할 정복 및 원패스 예제
  * `A` [Permutations](src/algorithms/sets/permutations) (중복 허용 및 비허용 순열)
  * `A` [Combinations](src/algorithms/sets/combinations) (중복 허용 및 비허용 조합)
  * `A` [Maximum Subarray](src/algorithms/sets/maximum-subarray)
* **다이나믹 프로그래밍 (Dynamic Programming)** - 이전에 찾아낸 하위 문제의 솔루션을 사용하여 전체 솔루션을 구축합니다.
  * `B` [Fibonacci Number](src/algorithms/math/fibonacci)
  * `B` [Jump Game](src/algorithms/uncategorized/jump-game)
  * `B` [Unique Paths](src/algorithms/uncategorized/unique-paths)
  * `B` [Rain Terraces](src/algorithms/uncategorized/rain-terraces) - 빗물 모으기 문제
  * `B` [Recursive Staircase](src/algorithms/uncategorized/recursive-staircase) - 꼭대기에 도달하는 방법의 수 계산
  * `B` [Seam Carving](src/algorithms/image-processing/seam-carving) - 내용 기반 이미지 크기 조절 알고리즘
  * `A` [Levenshtein Distance](src/algorithms/string/levenshtein-distance) - 두 시퀀스 간의 최소 편집 거리
  * `A` [Longest Common Subsequence](src/algorithms/sets/longest-common-subsequence) (LCS)
  * `A` [Longest Common Substring](src/algorithms/string/longest-common-substring)
  * `A` [Longest Increasing Subsequence](src/algorithms/sets/longest-increasing-subsequence)
  * `A` [Shortest Common Supersequence](src/algorithms/sets/shortest-common-supersequence)
  * `A` [0/1 Knapsack Problem](src/algorithms/sets/knapsack-problem)
  * `A` [Integer Partition](src/algorithms/math/integer-partition)
  * `A` [Maximum Subarray](src/algorithms/sets/maximum-subarray)
  * `A` [Bellman-Ford Algorithm](src/algorithms/graph/bellman-ford) - 모든 그래프 정점까지의 최단 경로 찾기
  * `A` [Floyd-Warshall Algorithm](src/algorithms/graph/floyd-warshall) - 모든 정점 쌍 간의 최단 경로 찾기
  * `A` [Regular Expression Matching](src/algorithms/string/regular-expression-matching)
* **백트래킹 (Backtracking)** - 브루트 포스와 유사하게 가능한 모든 솔루션을 생성하려고 시도합니다. 단, 다음 솔루션을 생성할 때마다 모든 조건을 만족하는지 테스트한 후에만 후속 솔루션을 계속 생성합니다. 조건을 만족하지 않으면 역추적(backtrack)하여 솔루션을 찾기 위한 다른 경로로 진행합니다. 일반적으로 상태 공간의 DFS 순회가 사용됩니다.
  * `B` [Jump Game](src/algorithms/uncategorized/jump-game)
  * `B` [Unique Paths](src/algorithms/uncategorized/unique-paths)
  * `B` [Power Set](src/algorithms/sets/power-set) - 집합의 모든 부분집합
  * `A` [Hamiltonian Cycle](src/algorithms/graph/hamiltonian-cycle) - 모든 정점을 정확히 한 번 방문
  * `A` [N-Queens Problem](src/algorithms/uncategorized/n-queens)
  * `A` [Knight's Tour](src/algorithms/uncategorized/knight-tour)
  * `A` [CombinationSum](src/algorithms/sets/combination-sum) - 특정 합을 만드는 모든 조합 찾기
* **분기 한정 (Branch & Bound)** - 백트래킹 검색의 각 단계에서 발견된 최소 비용 솔루션을 기억하고, 지금까지 찾은 최소 비용 솔루션의 비용을 하한선으로 사용하여 이보다 비용이 큰 부분 솔루션을 폐기합니다. 일반적으로 상태-공간 트리의 DFS 순회와 BFS 순회가 결합되어 사용됩니다.

## How to use this repository

**모든 의존성 설치하기**

```
npm install
```

**ESLint 실행하기**

코드 품질을 확인하기 위해 실행할 수 있습니다.

```
npm run lint
```

**모든 테스트 실행하기**

```
npm test
```

**이름으로 테스트 실행하기**

```
npm test -- 'LinkedList'
```

**문제 해결 (Troubleshooting)**

린트나 테스트가 실패하는 경우, `node_modules` 폴더를 삭제하고 npm 패키지를 다시 설치해 보세요:

```
rm -rf ./node_modules
npm i
```

또한, 올바른 Node 버전을 사용하고 있는지 확인하세요 (`>=16`). Node 버전 관리를 위해 [nvm](https://github.com/nvm-sh/nvm)을 사용하는 경우, 프로젝트의 루트 폴더에서 `nvm use`를 실행하면 올바른 버전이 자동으로 선택됩니다.

**플레이그라운드 (Playground)**

`./src/playground/playground.js` 파일에서 자료 구조와 알고리즘을 자유롭게 테스트해 볼 수 있으며, `./src/playground/__test__/playground.test.js`에 테스트 코드를 작성할 수 있습니다.

그런 다음, 다음 명령어를 실행하여 플레이그라운드 코드가 예상대로 작동하는지 확인할 수 있습니다:

```
npm test -- 'playground'
```

## Useful Information

### 참고 자료 (References)

- [▶ YouTube의 자료 구조 및 알고리즘 강의](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
- [✍🏻 자료 구조 스케치](https://okso.app/showcase/data-structures)

### 빅오 표기법 (Big O Notation)

*빅오 표기법(Big O notation)*은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이나 공간 요구사항이 어떻게 증가하는지 분류하는 데 사용됩니다.
아래 차트에서 빅오 표기법으로 명시된 가장 일반적인 알고리즘 증가 차수를 확인할 수 있습니다.

![Big O graphs](https://raw.githubusercontent.com/trekhleb/javascript-algorithms/master/assets/big-o-graph.png)

출처: [Big O Cheat Sheet](http://bigocheatsheet.com/).

다음은 가장 많이 사용되는 빅오 표기법들과 다양한 입력 데이터 크기에 따른 성능 비교 목록입니다.

| 빅오 표기법 (Big O Notation) | 유형 (Type) | 10개 요소에 대한 연산 수 | 100개 요소에 대한 연산 수 | 1000개 요소에 대한 연산 수 |
| ---------------------------- | ----------- | ------------------------ | ------------------------- | -------------------------- |
| **O(1)**                     | 상수형      | 1                        | 1                         | 1                          |
| **O(log N)**                 | 로그형      | 3                        | 6                         | 9                          |
| **O(N)**                     | 선형        | 10                       | 100                       | 1000                       |
| **O(N log N)**               | 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                 |

### 자료 구조 연산 복잡도 (Data Structure Operations Complexity)

| 자료 구조 (Data Structure) | 접근 (Access) | 검색 (Search) | 삽입 (Insertion) | 삭제 (Deletion) | 코멘트 (Comments) |
| -------------------------- | :-----------: | :-----------: | :--------------: | :-------------: | :---------------- |
| **Array**                  | 1             | n             | n                | n               |                   |
| **Stack**                  | n             | n             | 1                | 1               |                   |
| **Queue**                  | n             | n             | 1                | 1               |                   |
| **Linked List**            | n             | n             | 1                | n               |                   |
| **Hash Table**             | -             | n             | n                | n               | 완벽한 해시 함수의 경우 O(1) |
| **Binary Search Tree**     | n             | n             | n                | n               | 균형 트리인 경우 O(log(n)) |
| **B-Tree**                 | log(n)        | log(n)        | log(n)           | log(n)          |                   |
| **Red-Black Tree**         | log(n)        | log(n)        | log(n)           | log(n)          |                   |
| **AVL Tree**               | log(n)        | log(n)        | log(n)           | log(n)          |                   |
| **Bloom Filter**           | -             | 1             | 1                | -               | 검색 시 위양성(false positive) 발생 가능 |

### 배열 정렬 알고리즘 복잡도 (Array Sorting Algorithms Complexity)

| 이름 (Name)           | 최선 (Best)     | 평균 (Average)      | 최악 (Worst)        | 메모리 (Memory) | 안정성 (Stable) | 코멘트 (Comments) |
| --------------------- | :-------------: | :-----------------: | :-----------------: | :-------------: | :-------------: | :---------------- |
| **Bubble sort**       | n               | n<sup>2</sup>       | n<sup>2</sup>       | 1               | Yes             |                   |
| **Insertion sort**    | n               | n<sup>2</sup>       | n<sup>2</sup>       | 1               | Yes             |                   |
| **Selection sort**    | n<sup>2</sup>   | n<sup>2</sup>       | n<sup>2</sup>       | 1               | No              |                   |
| **Heap sort**         | n&nbsp;log(n)   | n&nbsp;log(n)       | n&nbsp;log(n)       | 1               | No              |                   |
| **Merge sort**        | n&nbsp;log(n)   | n&nbsp;log(n)       | n&nbsp;log(n)       | n               | Yes             |                   |
| **Quick sort**        | n&nbsp;log(n)   | n&nbsp;log(n)       | n<sup>2</sup>       | log(n)          | No              | 퀵 정렬은 보통 O(log(n)) 스택 공간을 사용하는 in-place 방식으로 구현됨 |
| **Shell sort**        | n&nbsp;log(n)   | 갭 시퀀스에 따라 다름 | n&nbsp;(log(n))<sup>2</sup> | 1               | No              |                   |
| **Counting sort**     | n + r           | n + r               | n + r               | n + r           | Yes             | r - 배열 내 가장 큰 수 |
| **Radix sort**        | n * k           | n * k               | n * k               | n + k           | Yes             | k - 가장 긴 키의 길이 |

<!-- ## Project Backers

> ❤️️ [GitHub](https://github.com/sponsors/trekhleb) 또는 ❤️️ [Patreon](https://www.patreon.com/trekhleb)을 통해 이 프로젝트를 후원하실 수 있습니다.

[이 프로젝트를 후원하는 분들](https://github.com/trekhleb/javascript-algorithms/blob/master/BACKERS.md) `∑ = 1` -->

## Author

[@trekhleb](https://trekhleb.dev)

[trekhleb.dev](https://trekhleb.dev)에서 JavaScript 및 알고리즘에 대한 더 많은 [프로젝트](https://trekhleb.dev/projects/)와 [글](https://trekhleb.dev/blog/)을 확인해 보세요:

- 🧠 [yesbrainer.ai](https://yesbrainer.ai/) – 뻔하지 않은 결정을 위한 AI 모델 협의회 (BYOK, 비공개, 계정 불필요)
- ✍🏻 [okso.app](https://okso.app/) – 생각과 아이디어를 표현, 이해, 정리하기 위한 드로잉 앱