Algorithms

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

Categories

• 자료구조 (Data structure)
• Algorithm Visualizer - 알고리즘의 시각화.

평균과 최악의 경우 분석

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

Sorting

• Sorting Algorithms Animations
• Youtube - Visualization and Comparison of Sorting Algorithms

• 깊이 우선 탐색 (Depth-first search) (DFS)
• 너비 우선 탐색 (Breadth-first search) (BFS)

Finding

• Circular Obstacle Pathfinding - Pathfinding around a set of circular obstacles

Routing

• 경계 경로 프로토콜 (Border Gateway Protocol) (BGP)
• Equal-cost multi-path routing (ECMP)

Mathematics

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

곡선

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

Computer Graphics

• Line drawing
  • DDA
  • 브레젠험 라인 알고리즘(Bresenham's Line Algorithm)
  • wu
  • efla
• Circle drawing
  • Midpoint circle algorithm
• Filling
  • Scanline rendering
  • Flood Fill Algorithm
  • Boundary Fill Algorithm
• 곡선 (Curve)
  • Bezier curve (보간법;Interpolation)
  • Spline

Image

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

Network Programming

• Nagle's algorithm

Cliping

• Cohen–Sutherland algorithm
• Cyrus–Beck algorithm
• Sutherland–Hodgman algorithm

자연 현상

• 빛 (Light)
  • 레일리 산란 과 미 산란 (Rayleigh Scattering & Mie Scattering)
• Plasma Effect
• 물결 효과 (Ripple Effect)

Collision Detection

• 다각형의 내부 외부 판별 (Point in polygon)
• 2D Polygon Collision Detection
• Axis Aligned Bounding Box (AABB)

Geometry

• 삼각형 폴리곤과 편선(Ray)의 교차점 ¹
• 외적을 이용해서 선분과 선분의 교차점 구하기 ²
• 외적을 이용한 두 벡터의 상대적인 방향 판별 ³
• 다각형과 점 위치 구하기
• 2DGeometry - 직선,선분으로 나뉘는 공간에서 한 점의 위치 구하기 ⁴ (외적 (Cross product)을 사용하는 방법)
• Line–sphere intersection
• 점과 직선 사이의 거리 (Distance from a point to a line)
• Angle - 각도 구하는 방법.
• 더글라스-포이커 (Douglas-Peucker) 알고리즘 - 곡선 또는 다각형을 단순화. cv2.approxPolyDP 함수로 구현됨.
• Geometry:LocalToGlobal - 지역 ROI 좌표를 전역 ROI 좌표로 변환.

Fluid Simulation

사용 목적별 알고리즘 분류

• 다차원 공간 파일: 공간정보에 대한 빠른 검색이 목적이다.
• Search and Matching algorithms: 패턴매칭 또는 검색과 관련된 알고리즘.

암호화

• Cryptographic hash function
• Message authentication code (MAC)
• Blockchain

키 유도 함수 (Key derivation function)

• Argon2
• bcrypt
• crypt
• Lyra2
• PBKDF2
• scrypt

Error detection and correction

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

합의 알고리즘 (Consensus algorithm)

• Raft
• Conflict-free replicated data type (CRDT)

Game Algorithmes

• Dungeon Generation
  • Binary space partitioning (BSP)
• 고속 역 제곱근 (Fast inverse square root)

Trees

See also

• Design pattern
• Software design
• Software design patterns
• Gang of Four (GoF)
• Algorithms
• Software architecture - 소프트웨어 아키텍처 디자인 관련 내용.
• Event driven architecture
• System Architecture
• Layered Design - 패키지 순환 참조 방지를 위한 설계 방법.

Favorite site

• Wikipedia (en) 알고리즘에 대한 설명
• Hyoung-Jun(김형준) GIS Lab: 프로그래밍/Algorithms ⁵
• Algorithmia - Open Marketplace for Algorithms (딥러닝을 포함한 알고리즘 오픈마켓)

Tutorials

• Gihub - 1ambda - Algorithm ⁶

Articles

• 알고리듬 연구의 새로운 지평, "약간의 메모리가 많은 시간보다 강력할 수 있다" 증명 | GeekNews
  • [원문] For Algorithms, a Little Memory Outweighs a Lot of Time | Quanta Magazine
  • MIT 이론 컴퓨터 과학자 Ryan Williams가 발표한 새 증명은, 메모리 자원이 시간보다 더 강력한 계산 자원일 수 있음을 보임
  • 기존의 시간-공간 복잡도 관계에 대한 50년간의 정체를 깨고, 모든 알고리듬을 더 적은 메모리로 변환할 수 있는 방법을 제시
  • 증명의 핵심은, 공간 절약 시뮬레이션을 일반화해, 알고리듬의 공간 사용량을 시간의 제곱근 수준으로 줄이는 아이디어
  • 이로 인해, PSPACE와 P 클래스의 차이를 정량적으로 입증하는 데 진전을 이루었으며, 더 넓은 간격의 증명으로 이어질 가능성도 열림
  • 전문가들은 이 성과를 “놀라운 발전이자 새로운 탐험의 출발점”으로 평가하며, 향후 이 결과가 다른 이론 컴퓨터 과학 난제를 푸는 실마리가 될 수 있음

References