[Algorithm] 알고리즘 분류

알고리즘(Algorithm)의 종류, 분류

기본 알고리즘 종류

Recursive Call Algorithm (재귀 함수)

  • Maximum value or Minimum value (최대값 또는 최소값 찾기) : 가장 큰 숫자를 기억해가며 진행함
  • Euclid (유클리드 알고리즘) : 두 정수의 최대공약수(GCD)를 빠르게 구하기
  • Factorial (팩토리얼)
  • Fibonacci (피보나찌 수열)
  • Sum (합계)

Sorting Algorithm (정렬 알고리즘)

  • Selection Sort (선택 정렬)
  • Bubble Sort (버블 정렬)
  • Quick Sort (퀵 정렬)
  • Insertion Sort (삽입 정렬)
  • Shell Sort (쉘 정렬)
  • Heap Sort (힙 정렬 )
  • Merge Sort (병합 정렬)
  • Radix Sort (기수 정렬)

Searching Algorithm (탐색 알고리즘)

  • Sequential Search (순차 탐색) = Linear Search (선형탐색)
  • Binary Search (이진 탐색)
  • Red-Black tree (레드 블랙 트리)

Hash Algorithm (해시 알고리즘)

  • Hash Table (해시 테이블)

Graph Algorithm (그래프 알고리즘)

  • Graph Traversal (그래프 순회)
    • BFS(Breath First Search) (깊이 우선 검색)
    • DFS(Depth First Search) (넓이 우선 검색)
  • Graph Search (그래프 탐색,검색)
  • MST : Minimum Spanning Tree (최소신장 트리)
    • Kruscal’s algoritm (크루스 칼의 알고리즘)
    • Prim algorithm (프라임 알고리즘)
  • Shortest Path (최단경로 알고리즘)
    • Dijkstra (다익스트라)

String Matching Algorihm (문자열 검색 알고리즘)

  • 긴 텍스트에서 짧은 패턴 문자열이 어디에 있는지를 찾는 것

알고리즘 설계기법

Divide and Conquer (분할정복)

  • Merge Sort (병합 정렬)
  • Quick Sort (퀵 정렬)
  • Binary Search (이진 검색)
  • Strassen’s Matrix Multiplication (슈트라센 알고리즘)
  • Closest pair (points) (최근접 점쌍 문제)

Dynamic Programming (동적 계획법)

  • Fibonacci number series (피보나치 수열)
  • Knapsack problem (배낭 문제)
  • Tower of Hanoi (하노이의 탑)
  • All pair shortest path by Floyd-Warshall (Floyd-Warshall의 모든 페어 최단 경로)
  • Shortest path by Dijkstra (Dijkstra의 최단 경로)
  • Project scheduling (프로젝트 일정)
  • 0/1 Knapsack Problem

Greedy Algorithm (탐욕 알고리즘)

  • Huffman code (허프만 코드)
  • Travelling Salesman Problem (외판원 문제)
  • Prim’s Minimal Spanning Tree Algorithm (프림의 최소 신장트리 문제)
  • Kruskal’s Minimal Spanning Tree Algorithm (크루스칼의 최소 신장트리 문제)
  • Dijkstra’s Minimal Spanning Tree Algorithm (다익스트라의 최소 신장트리 문제)
  • Graph - Map Coloring
  • Graph - Vertex Cover
  • Job Scheduling Problem
  • Machine scheduling
  • Fractional Knapsack Problem (부분 배낭 문제)
  • Activity Selection Problem (활동 선택 문제)

Backtraking (백트래킹)

  • Backtracking (백 트래킹)
  • N Queens (N-퀸)

References

http://www.ktword.co.kr/abbr_view.php?m_temp1=5735