알고리즘의 개념과 종류

알고리즘이란?

알고리즘은 특정 문제를 해결하기 위한 명확하고 논리적인 단계들의 집합입니다. 컴퓨터 과학에서는 컴퓨터가 특정 작업을 수행하도록 지시하는 명령어들의 집합을 의미하며, 일상생활에서도 요리 레시피, 가구 조립 설명서 등을 알고리즘의 예시로 볼 수 있습니다.

알고리즘은 다음과 같은 특징을 가집니다.

입력: 알고리즘이 처리해야 할 데이터
출력: 알고리즘의 실행 결과
명확성: 각 단계는 모호하지 않고 명확하게 정의되어야 함
유한성: 한정된 시간 안에 실행을 완료해야 함
효율성: 최소한의 시간과 자원을 사용하여 문제를 해결해야 함

알고리즘의 기본적인 종류

알고리즘은 다양한 기준으로 분류할 수 있으며, 문제 해결 방식이나 적용 분야에 따라 여러 종류가 존재합니다.

1. 문제 해결 방식에 따른 분류

• 완전 탐색 (Brute-Force): 가능한 모든 경우의 수를 탐색하여 최적의 해를 찾는 방법입니다. 단순하지만 경우의 수가 많아지면 비효율적일 수 있습니다.
• 탐욕 알고리즘 (Greedy Algorithm): 각 단계에서 가장 최선의 선택을 하는 방식으로 진행하며, 항상 최적의 해를 보장하지는 않습니다.
• 분할 정복 (Divide and Conquer): 문제를 작은 하위 문제로 나누어 해결하고, 결과를 결합하여 원래 문제의 답을 얻는 방식입니다.
• 동적 계획법 (Dynamic Programming): 하위 문제의 해를 저장하고 재활용하여 중복 계산을 피하고 효율성을 높이는 방식입니다.
• 백트래킹 (Backtracking): 모든 가능한 경우의 수를 탐색하되, 조건에 맞지 않으면 이전 단계로 돌아가 다른 경우를 시도하는 방식입니다.
• 가지치기 (Branch and Bound): 백트래킹과 유사하지만, 가능성이 없는 경우는 더 이상 탐색하지 않아 효율성을 높입니다.

2. 설계 패러다임에 따른 분류

• 재귀 알고리즘 (Recursive Algorithm): 자기 자신을 호출하여 문제를 해결하는 방식입니다.
• 반복 알고리즘 (Iterative Algorithm): 반복문을 사용하여 문제를 해결하는 방식입니다.
• 무작위 알고리즘 (Randomized Algorithm): 무작위 선택을 통해 문제를 해결하며, 항상 동일한 결과를 보장하지는 않습니다.
• 휴리스틱 알고리즘 (Heuristic Algorithm): 경험이나 직관에 기반하여 빠르게 근사적인 해를 찾는 방식입니다.

3. 적용 분야에 따른 분류

• 정렬 알고리즘 (Sorting Algorithm): 데이터를 특정 순서대로 나열합니다.
• 탐색 알고리즘 (Searching Algorithm): 데이터 집합에서 특정 값을 찾습니다.
• 그래프 알고리즘 (Graph Algorithm): 그래프 형태로 표현된 데이터의 관계를 분석하고 처리합니다.
• 문자열 알고리즘 (String Algorithm): 문자열 데이터를 처리하는 알고리즘입니다.
• 기하 알고리즘 (Geometric Algorithm): 기하학적인 문제를 해결하는 알고리즘입니다.

4. 시간 복잡도에 따른 분류

• 다항 시간 알고리즘 (Polynomial Time Algorithm): 실행 시간이 입력 크기의 다항식으로 표현되는 알고리즘입니다.
• 지수 시간 알고리즘 (Exponential Time Algorithm): 실행 시간이 입력 크기의 지수 함수로 표현되는 알고리즘입니다.
• NP-완전 문제 (NP-Complete Problem): 다항 시간 안에 해를 찾는 알고리즘이 아직 발견되지 않은 문제입니다.

이 외에도 다양한 기준으로 알고리즘을 분류할 수 있습니다. 알고리즘에 대한 이해를 높이기 위해서는 각 분류 기준과 해당 기준에 따른 알고리즘의 종류를 숙지하는 것이 중요합니다.

Reference
https://coffeebaralog.tistory.com/11
https://velog.io/@swch56/01-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A2%85%EB%A5%98