Skip to content

Algorithms

알고리즘의 상세 분야

알고리즘(영어: algorithm 알고리듬, IPA: [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.

Categories

평균과 최악의 경우 분석

자세한 내용은 빅-오 표기법에서 확인.

Sorting

Visualization_and_Comparison_of_Sorting_Algorithms.gif

Selection sort / Shell sort / Insertion sort
Merge sort / Quick sort / Heap sort
Bubble sort / Comb sort / Cockta sort

Finding

Routing

Mathematics

  • 유클리드 호제법 (Euclidean Algorithm): 최대공약수를 구하는 알고리즘.
  • 카라슈바 알고리즘 (Karatsuba Algorithm): 큰 수를 곱셈할 때 가감 횟수를 늘려서 곱셈 횟수를 줄이는 방법.
  • 고속 역 제곱근 (Fast inverse square root) - 조명 처리와 같은 연산에 입사각과 반사각을 계산할 때 고속 역 제곱근 알고리즘을 사용한다.

곡선

  • 베지어 곡선: 중간 중간의 Point를 지나가지 않으며, 해당 Point의 영향으로 휘어지는 곡선.
  • Ferguson / Xoons 곡선
  • Catmull-Rom 스플라인 곡선: 중간 중간의 Point를 모두 지나가는 곡선. 게임에서는 칼의 궤적같은 형태를 만들 때 자주 사용된다.
  • 베르누이의 렘니 스케이트 곡선 (Lemniscate of Bernoulli)

Computer Graphics

Image

  • jpeg
  • png (zlib)
  • Seam Carving - 이미지 내의 중요하지 않은 반복되는 부분(Seam)만 찾아서 줄이거나 확장
  • FELICS - 무손실 JPEG 코덱보다 5배 빠른 성능과 유사한 압축률을 달성하는 무손실 이미지 압축 알고리즘입니다.
  • ImageZero
  • QOI - O(n) 무손실 이미지 압축

Network Programming

Cliping

자연 현상

Collision Detection

Geometry

Fluid Simulation

사용 목적별 알고리즘 분류

암호화

키 유도 함수 (Key derivation function)

Error detection and correction

  • 반복 부호
  • 패리티 비트
  • 체크섬
  • 순환 중복 검사 (CRC)
  • 암호학적 해시 함수
  • 전방 오류 정정

합의 알고리즘 (Consensus algorithm)

Game Algorithmes

Trees

Table of Tree

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-trees

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

Favorite site

Tutorials

References

  1. GIS_DEVELOPER_-_Ray-Triangle_Intersection.pdf ↩

  2. Bowbowbow_tistory_-_line-line_intersection.pdf ↩

  3. Bowbowbow_tistory_-_two-vectors_direction.pdf ↩

  4. 2DGeometry_-line_point_position-_cross_product.pdf ↩

  5. GIS_Lab_-_Programming_algorithms.pdf ↩

  6. 1ambda.github.io-master-5c58cab.zip ↩