목차16개 항목
출처와 참고
Oleksii Trekhleb의 공개 저장소 「JavaScript Algorithms and Data Structures」를 주제별로 재구성한 노트다.
알고리즘 설계 패러다임
개별 구현을 외우기보다 완전탐색, 분할 정복, 그리디, 동적 계획법, 백트래킹이 어떤 입력 성질을 이용하는지 이해한다. 같은 문제도 여러 방법으로 풀어 시간·공간 비용을 비교할 수 있다.
Brute Force
가능한 후보를 모두 확인하는 방식이다.
대표 예제: Linear Search, Rain Terraces, Recursive Staircase, Maximum Subarray, Travelling Salesman Problem, Discrete Fourier Transform.
Greedy
각 단계에서 현재 최선의 선택을 확정한다. 그 선택의 정당성이 필요하다.
대표 예제: Jump Game, Unbound Knapsack Problem, Dijkstra Algorithm, Prim’s Algorithm, Kruskal’s Algorithm.
Divide and Conquer
문제를 작은 부분으로 나누고 답을 결합한다.
대표 예제: Binary Search, Tower of Hanoi, Pascal's Triangle, Euclidean Algorithm, Merge Sort, Quicksort, Tree Depth-First Search, Graph Depth-First Search 외 7개.
Dynamic Programming
겹치는 부분 문제를 저장하고 재사용한다.
대표 예제: Fibonacci Number, Jump Game, Unique Paths, Rain Terraces, Recursive Staircase, Seam Carving, Levenshtein Distance, Longest Common Subsequence 외 9개.
Backtracking
조건에 맞지 않는 탐색 가지를 조기에 버린다.
대표 예제: Jump Game, Unique Paths, Power Set, Hamiltonian Cycle, N-Queens Problem, Knight's Tour, Combination Sum.
Branch & Bound
현재 최선값과 하한·상한을 이용해 후보를 가지치기한다.
대표 예제: .
분야별 기타 구현 전체 목록
Cryptography
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| Polynomial Hash | 기초 | 다항식 기반 문자열 해싱 | 원본 |
| Rail Fence Cipher | 기초 | 문자 순서를 재배열하는 고전 암호 | 원본 |
| Caesar Cipher | 기초 | 알파벳 이동에 기반한 고전 치환 암호 | 원본 |
| Hill Cipher | 기초 | 행렬 연산 기반 고전 암호 | 원본 |
Machine Learning
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| NanoNeuron | 기초 | 순전파·역전파의 아주 작은 신경망 학습 예제 | 원본 |
| k-NN | 기초 | 가까운 이웃의 레이블로 분류 | 원본 |
| k-Means | 기초 | 대표 중심을 갱신하는 군집화 | 원본 |
Image Processing
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| Seam Carving | 기초 | 낮은 에너지 경로를 줄여 내용 인식 이미지 크기 조정 | 원본 |
Statistics
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| Weighted Random | 기초 | 가중치에 비례하여 무작위 추출 | 원본 |
Evolutionary algorithms
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| Genetic algorithm | 심화 | 선택·돌연변이·교배로 후보 해 탐색 | 원본 |
Uncategorized
| 항목 | 수준 | 핵심 개념 | 코드·설명 |
|---|---|---|---|
| Tower of Hanoi | 기초 | 재귀 분할로 원판 이동 | 원본 |
| Square Matrix Rotation | 기초 | 정사각 행렬의 제자리 회전 | 원본 |
| Jump Game | 기초 | 도달 가능성의 그리디·DP 비교 | 원본 |
| Unique Paths | 기초 | 격자 경로 수를 DP로 계산 | 원본 |
| Rain Terraces | 기초 | 막대 사이에 고이는 물의 양 계산 | 원본 |
| Recursive Staircase | 기초 | 계단을 오르는 경우의 수 | 원본 |
| Best Time To Buy Sell Stocks | 기초 | 최저 매수 시점과 최대 이익 계산 | 원본 |
| Valid Parentheses | 기초 | 스택으로 괄호의 짝 검사 | 원본 |
| N-Queens Problem | 심화 | 체스 퀸의 제약을 지키는 배치 | 원본 |
| Knight's Tour | 심화 | 나이트가 모든 칸을 순회하는 경로 | 원본 |
암호 예제의 Caesar·Rail Fence·Hill 등은 교육용 고전 암호다. 현대 보안 시스템의 기밀성 보장에는 검증된 현대 암호 표준과 라이브러리를 사용한다.
코드 실행과 테스트
npm install
npm run lint
npm test
npm test -- 'LinkedList'저장소는 각 자료구조·알고리즘에 개별 구현과 테스트를 둔다. 단위 테스트를 먼저 실행한 다음 경계 입력·중복·빈 데이터·음수 여부를 추가로 점검한다. Node.js 버전 요구사항은 실행할 브랜치의 설정 파일을 기준으로 확인한다. 예제 학습용 공간은 src/playground/다.
복잡도를 읽는 원칙
해시 기반 구조는 평균·최악 복잡도를 구분하고, 비교 정렬은 일반적으로 Ω(n log n) 하한과 개별 알고리즘의 최악 비용을 분리한다. 문제의 실제 비용에는 메모리 접근과 입력 분포도 포함된다.