우수 답변
목적 별 분류
각 알고리즘에는 목표가 있습니다. 예를 들어 빠른 정렬 알고리즘의 목적은 데이터를 오름차순 또는 내림차순으로 정렬하는 것입니다. 그러나 목표의 수는 무한하며 목적에 따라 그룹화해야합니다.
구현 별 분류
알고리즘은 다양한 기본 원칙에 따라 구현 될 수 있습니다.
- 재귀 또는 iterative 재귀 알고리즘은 특정 조건이 일치 할 때까지 반복적으로 자신을 호출하는 알고리즘입니다. 함수형 프로그래밍에 공통적 인 방법입니다. 반복 알고리즘은 루프와 같은 반복 구조를 사용합니다. 일부 문제는 하나의 구현 또는 다른 구현에 더 적합합니다. 예를 들어 하노이의 탑 문제는 재귀 적 구현에서 잘 이해됩니다. 모든 재귀 버전에는 동일한 반복 반복이 있으며 그 반대도 마찬가지입니다.
- 논리 또는 절차 적 알고리즘은 통제 된 논리적 추론으로 볼 수 있습니다. 논리 구성 요소는 계산에 사용될 수있는 공리를 표현하고 제어 구성 요소는 공리에 추론이 적용되는 방식을 결정합니다. 이것이 로직 프로그래밍의 기초입니다. 순수 논리 프로그래밍 언어에서는 제어 구성 요소가 고정되고 논리 구성 요소 만 제공하여 알고리즘이 지정됩니다.
- Serial 또는 parallel 알고리즘은 일반적으로 컴퓨터가 한 번에 하나의 알고리즘 명령을 실행한다는 가정하에 논의됩니다. 이것은 병렬 알고리즘과 반대되는 직렬 알고리즘으로, 컴퓨터 아키텍처를 활용하여 여러 명령을 한 번에 처리합니다. 그들은 문제를 하위 문제로 나누고 여러 프로세서에 전달합니다. 반복 알고리즘은 일반적으로 병렬화 가능합니다. 정렬 알고리즘은 효율적으로 병렬화 될 수 있습니다.
- 결정적 또는 비 결정적 결정적 알고리즘은 사전 정의 된 프로세스로 문제를 해결하는 반면, 비 결정적 알고리즘은 휴리스틱을 사용하여 각 단계에서 최상의 솔루션을 추측해야합니다.
디자인 패러다임 별 분류
디자인 패러다임은 전용 알고리즘이 필요한 연구 또는 문제 클래스의 영역입니다.
- 분할 및 정복 분할 및 정복 알고리즘은 인스턴스가 충분히 작아 질 때까지 문제의 인스턴스를 동일한 문제의 하나 이상의 작은 인스턴스 (일반적으로 재귀 적)로 반복적으로 축소합니다. 쉽게 해결할 수 있습니다. 분할 및 정복의 한 가지 예는 병합 정렬입니다. 데이터를 세그먼트로 분할 한 후 데이터의 각 세그먼트에 대해 정렬을 수행 할 수 있으며이를 병합하여 정복 단계에서 전체 데이터를 정렬 할 수 있습니다. 이진 검색 알고리즘은 감소 및 정복 알고리즘 이라고하는 분할 및 정복의 변형의 예로서 동일한 하위 문제를 해결하고이 하위 문제의 솔루션을 사용하여 해결합니다. 더 큰 문제입니다.
- 동적 프로그래밍 가중치 그래프에서 가장 짧은 경로는 인접한 모든 목표에서 목표까지의 최단 경로를 사용하여 찾을 수 있습니다. 정점. 문제에 대한 최적의 솔루션을 최적 솔루션에서 하위 문제까지 구성 할 수있는 경우 동적 프로그래밍을 사용하면 이미 계산 된 솔루션을 다시 계산하지 않아도됩니다. – “분할 및 정복”접근 방식과의 주요 차이점은 분할 및 정복에서 하위 문제가 독립적이라는 것입니다. 여기서 하위 문제의 중첩은 동적 프로그래밍에서 발생합니다. -다이나믹 프로그래밍과 메모가 함께합니다. 간단한 재귀와의 차이점은 재귀 호출의 캐싱 또는 메모 화에 있습니다. 하위 문제가 독립적 인 경우 이것은 쓸모가 없습니다. 메모 화를 사용하거나 이미 해결 된 하위 문제의 표를 유지함으로써 동적 프로그래밍은 많은 문제의 지수 적 특성을 다항식 복잡성으로 줄입니다.
- 탐욕스러운 방법 탐욕스러운 알고리즘은 동적 프로그래밍 알고리즘과 유사하지만 차이점은 하위 문제에 대한 솔루션을 각 단계에서 알 필요가 없다는 것입니다. 대신 현재 가장 적합한 솔루션으로 “탐욕스러운”선택을 할 수 있습니다. 가장 인기있는 탐욕스러운 알고리즘은 Kruskal이 제공 한 최소 스패닝 트리를 찾는 것입니다.
- 선형 프로그래밍 문제는 선형 집합으로 표현됩니다. 불평등 한 다음 입력을 최대화하거나 최소화하려고 시도합니다. 이는 특히 심플 렉스 알고리즘을 사용하여 유 방향 그래프의 최대 흐름과 같은 많은 문제를 해결할 수 있습니다.선형 계획법의 복잡한 변형을 정수 계획법이라고하며, 솔루션 공간은 모든 정수로 제한됩니다.
- 축소 는
변환 및 정복 문제를 다른 문제로 변환하여 해결합니다. 간단한 예 : 정렬되지 않은 목록에서 중앙값을 찾는 것은 먼저이 문제를 정렬 문제로 변환하고 정렬 된 목록에서 중간 요소를 찾는 것입니다. 축소의 주요 목표는 가능한 가장 단순한 변환을 찾는 것입니다.
- 그래프 사용 체스와 같은 많은 문제를 문제로 모델링 할 수 있습니다. 그래프에. 그래프 탐색 알고리즘이 사용됩니다. 이 카테고리에는 검색 알고리즘과 역 추적도 포함됩니다.
- 확률 및 발견 적 패러다임 확률 적 무작위로 선택하는 것. 유전학 생물학적 진화 과정을 모방하여 문제에 대한 해결책을 찾으려고 시도합니다. 무작위 돌연변이주기는 연속적인 “해결책”세대를 생성합니다. 따라서 그들은 번식과 “적자 생존”을 모방합니다. Heuristic 일반적인 목적은 최적의 솔루션을 찾는 것이 아니라 완벽한 솔루션을 찾기위한 시간이나 리소스가 실용적이지 않은 대략적인 솔루션입니다.
복잡도 별 분류
일부 알고리즘은 선형 시간으로 완료되고 일부는 기하 급수적으로 완료됩니다. 일부는 완료되지 않습니다.
출처 : 알고리즘 분류
답변
다음은 알고리즘을 분류하는 또 다른 방법입니다.
경쟁 프로그래밍에는 4 가지 주요 문제가 있습니다. 패러다임을 해결합니다.
즉, 주어진 문제를 해결하기 위해 취해야하는 다양한 접근 방식 / 도구가 있습니다.
- Brute Force / Complete Search : 모든 가능성을 살펴보고 최상의 솔루션을 선택하는 방법입니다.
- 장점 : 간단합니다. 모든 가능성을 고려하고 있으므로 항상 해결책을 찾아야합니다.
- 단점 : 항목 수가 증가함에 따라 가능성의 수는 기하 급수적으로 증가합니다.
- 나누기 및 정복 : 문제를 더 작은 부분으로 분할 한 다음 해결하는 방법 부속. 바이너리 검색을 생각해보세요.
- Greedy 접근 방식 : 미래를 고려하지 않고 현재 시간에 가장 적합한 옵션을 선택하는 방법입니다.
- 장점 : 빠르고 간단하며 최상의 솔루션을 얻거나 좀 더 가까워 질 수 있습니다.
- 단점 : 대부분의 경우 최상의 솔루션을 얻지 못합니다.
- 동적 프로그래밍 : 이전에 찾은 하위 솔루션을 사용하여 솔루션을 구축하는 방법입니다. 확실히 고급 기술 중 하나이지만 매우 강력하고 적용 가능합니다.
- 장점 : 다항식 시간의 많은 문제에 대한 최적의 솔루션을 찾습니다 ( 무차별 대입은 기하 급수적으로 걸릴 수 있습니다.)
- 단점 : 파악하고 적용하기 어렵고 다양한 상태와 재발을 이해하는 데 시간이 걸립니다.
li>
출처
Halim, Steven 및 Felix Halim. 경쟁 프로그래밍 : 프로그래밍 콘테스트의 새로운 하한선 . Lulu, 2013.