알고리즘 유형

구현 & 시뮬레이션

• 구현 문제: "문제의 요구사항을 실제 동작하는 코드"로 구현
• 시뮬레이션 문제: "문제에서 요구하는 시나리오, 규칙, 절차를 차례대로 실행"

특징
요구사항을 빠짐없이 코드로 옮기는 것이 핵심
문제의 조건과 제약을 정확히 이해하고 처리

완전 탐색

-모든 경우의 수를 빠짐없이 조사하여 정답을 찾는 방법

특징
모든 경우를 시도하므로, 정답을 놓칠 가능성이 없다.
입력 규모가 작을 때 유리하며, 구현이 비교적 간단하다.

그리디 알고리즘

• 매 순간 가장 최선의 선택를 함으로써 전체 최적해를 구하는 방식

특징
다른 알고리즘(예: 완전탐색, 동적 계획법 등)보다 일반적으로 구현이 간단하고, 빠른 시간 안에 결과를 얻을 수 있다.

백트래킹

• 완전 탐색을 기반으로 하되, 유망하지 않은 경우(조건 불만족)는 미리 배제(가지치기) 하여 탐색 효율을 높이는 기법

특징
조건을 만족할 수 없는 상황을 빠르게 배제할 수 있어, 탐색 범위를 크게 축소할 수 있다.
대부분 재귀 함수로 구현

DC

• 문제를 작거나 유사한 하위 문제로 분할하고, 각 문제를 해결한 뒤 결과를 합쳐 최종 해를 구하는 방식

특징
분할 → 정복(해결) → 병합 단계를 거친다.
분할된 각 부분 문제는 서로 독립적이어야 한다.

DP

• 큰 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 해를 저장(메모이제이션) 하여 재활용함으로써 전체 문제의 최적 해를 구하는 알고리즘 설계 기법

특징
중복 계산을 획기적으로 줄일 수 있어, 지수 시간이 걸리는 문제도 다항 시간 안에 풀 수 있는 경우가 많다.
Top-Down 방식(메모이제이션) 또는 Bottom-up 방식(타뷸레이션)으로 구현한다.
점화식(Recurrence Relation)을 올바르게 세우는 것이 핵심