[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