알고리즘 분류, 알고리즘 구분

(2020-02-05)
1. 알고리즘의 주제별 분류

  ㅇ 기초적인 알고리즘
     - 최대값 또는 최소값 찾기 등
        . 가장 큰 숫자를 기억해가며 진행함 
     - 유클리드 알고리즘
        . 두 정수최대공약수를 빠르게 구하기

  ㅇ 탐색 알고리즘 (Searching Algorithm)
     - 탐색 문제 
        . 순서화리스트(ordered list)에서 어떤 원소의 위치 및 존재유무를 찾는 것
     - 탐색문제의 해 또는 결과
        . 원소의 위치
     - 주요 종류
        . 순차 탐색(sequential search)/선형탐색(linear search)
        . 이진 탐색 (binary search) 등
        * 보통, 자료구조 형태에 따라 구분됨

  ㅇ 스트링 매칭 알고리즘 (String Matching Algorihm)
     - 긴 텍스트에서 짧은 패턴 문자열이 어디에 있는지를 찾는 것 

  ㅇ 정렬 알고리즘 (Sorting Algorithm)
     - 정렬 문제
        . 수많은 자료를 특정 목적에 맞게 순서있게 재 배열하는 것
     - 정렬문제의 해 또는 결과
        . 정렬된 배열
     - 주요 종류
        . 선택 정렬 (Selection Sort)
        . 버블 정렬 (Bubble Sort)
        . 삽입 정렬 (Insertion Sort)
        . 퀵 정렬 (Quick Sort)
        . 병합 정렬 (Merge Sort)

  ㅇ 그래프 알고리즘 (Graph Algorithm)
     - 주요 종류
        . 그래프 순회(Graph Traversal)/탐색,검색(Graph Search) 방법
        . 신장 트리(생성 트리) 작성 방법
        . 최소비용 생성트리 작성 알고리즘
        . 최단경로 알고리즘해시 알고리즘 (Hash Algorithm)

  ㅇ 최적화 알고리즘(Optimizing Algorithm) 등


2. 알고리즘확률의 개입 여부에 따른 분류

  ㅇ 결정 알고리즘 (Deterministic Algorithm)
     - 항상 정확한 답을 반환하는 알고리즘
     - 例) 위 1.항에 언급된 대부분의 알고리즘들

  ㅇ 확률 알고리즘 (Probabilistic Algorithm), 무작위 알고리즘 (Randomized Algorithm)
     - 실행될 명령이 무작위로 결정되는 알고리즘
     - 例) 
        . 몬테칼로 알고리즘 : 무작위난수를 발생시켜 근사적인 해를 구하는 알고리즘
        . 라스베가스 알고리즘 : 무작위 시간으로 정확한 해를 구하는 알고리즘


3. 알고리즘설계기법/전략/파라다임에 의한 분류

  ※ ☞ 알고리즘 설계 참조
     - 분할정복(Divide and Conquer) 전략
        . 규모가 큰 문제를 만만한 작은 조각으로 나눠 각개격파 
     - 동적계획법(Dynamic Programming) 전략
     - 탐욕 알고리즘(Greedy Algorithm) 전략 등


[알고리즘 종류] 1. 알고리즘 분류 2. 그래프 알고리즘
[기초 알고리즘] [정렬 알고리즘] [검색 알고리즘]

 
        최근수정     요약목록     참고문헌