Algorithms
|
알고리즘(영어: algorithm 알고리듬, IPA: [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.
Categories
- 자료구조 (Data structure)
- Algorithm Visualizer - 알고리즘의 시각화.
평균과 최악의 경우 분석
자세한 내용은 빅-오 표기법에서 확인.
Sorting
|
Selection sort / Shell sort / Insertion sort |
Finding
Routing
Mathematics
- 유클리드 호제법 (Euclidean Algorithm): 최대공약수를 구하는 알고리즘.
- 카라슈바 알고리즘 (Karatsuba Algorithm): 큰 수를 곱셈할 때 가감 횟수를 늘려서 곱셈 횟수를 줄이는 방법.
- 고속 역 제곱근 (Fast inverse square root) - 조명 처리와 같은 연산에 입사각과 반사각을 계산할 때 고속 역 제곱근 알고리즘을 사용한다.
곡선
- 베지어 곡선: 중간 중간의 Point를 지나가지 않으며, 해당 Point의 영향으로 휘어지는 곡선.
- Ferguson / Xoons 곡선
- Catmull-Rom 스플라인 곡선: 중간 중간의 Point를 모두 지나가는 곡선. 게임에서는 칼의 궤적같은 형태를 만들 때 자주 사용된다.
- 베르누이의 렘니 스케이트 곡선 (Lemniscate of Bernoulli)
Computer Graphics
- Line drawing
- Scanline rendering
- Flood Fill Algorithm
- Boundary Fill Algorithm
Image
- jpeg
- png (zlib)
- Seam Carving - 이미지 내의 중요하지 않은 반복되는 부분(Seam)만 찾아서 줄이거나 확장
- FELICS - 무손실 JPEG 코덱보다 5배 빠른 성능과 유사한 압축률을 달성하는 무손실 이미지 압축 알고리즘입니다.
- ImageZero
- QOI - O(n) 무손실 이미지 압축
Network Programming
Cliping
자연 현상
- 빛 (Light)
- 레일리 산란 과 미 산란 (Rayleigh Scattering & Mie Scattering)
Collision Detection
Geometry
- 삼각형 폴리곤과 편선(Ray)의 교차점 1
- 외적을 이용해서 선분과 선분의 교차점 구하기 2
- 외적을 이용한 두 벡터의 상대적인 방향 판별 3
- 다각형과 점 위치 구하기
- 2DGeometry - 직선,선분으로 나뉘는 공간에서 한 점의 위치 구하기 4 (외적 (Cross product)을 사용하는 방법)
- Line–sphere intersection
- 점과 직선 사이의 거리 (Distance from a point to a line)
- Angle - 각도 구하는 방법.
- 더글라스-포이커 (Douglas-Peucker) 알고리즘 - 곡선 또는 다각형을 단순화. cv2.approxPolyDP 함수로 구현됨.
Fluid Simulation
사용 목적별 알고리즘 분류
- 다차원 공간 파일: 공간정보에 대한 빠른 검색이 목적이다.
- Search and Matching algorithms: 패턴매칭 또는 검색과 관련된 알고리즘.
암호화
키 유도 함수 (Key derivation function)
Error detection and correction
- 반복 부호
- 패리티 비트
- 체크섬
- 순환 중복 검사 (CRC)
- 암호학적 해시 함수
- 전방 오류 정정
합의 알고리즘 (Consensus algorithm)
Game Algorithmes
Trees
Binary trees | Binary search tree (BST), Cartesian tree, Top tree, T-tree |
Self-balancing binary search trees | AA tree, AVL tree, LLRB tree, Red-black tree, Scapegoat tree, Splay tree, Treap |
B+ tree, B*-tree, Bx-tree, ~UB-tree, 2-3 tree, 2-3-4 tree, (a,b)-tree, Dancing tree, Htree | |
Tries | Suffix tree, Radix tree, Ternary search tree, X-fast trie, Y-fast trie |
Binary space partitioning (BSP) trees | Quadtree, Octree, k-d tree, Implicit k-d tree, vp-tree |
Non-binary trees | Exponential tree, Fusion tree, Interval tree, PQ tree, Range tree, SPQR tree, Van Emde Boas tree |
Spatial data partitioning trees | R-tree, R+tree, R*tree, X-tree, M-tree, Segment tree, Hilbert R-tree, Priority R-tree |
Other trees | Heap, Hash tree, Finger tree, Order statistic tree, Metric tree, Cover tree, ~BK-tree, Doubly chained tree, iDistance, Link-cut tree, Fenwick tree |
See also
- Design pattern
- Software design
- Software design patterns
- Gang of Four (GoF)
- Algorithms
- Software architecture - 소프트웨어 아키텍처 디자인 관련 내용.
- Event driven architecture
- System Architecture
Favorite site
- Wikipedia (en) 알고리즘에 대한 설명
- Hyoung-Jun(김형준) GIS Lab: 프로그래밍/Algorithms 5
- Algorithmia - Open Marketplace for Algorithms (딥러닝을 포함한 알고리즘 오픈마켓)