[Algorithm] 풀이 방식 분류

알고리즘 풀이 방식 분류

여러 알고리즘 문제를 풀기 위한 다양한 방식이 존재한다. 어떤 상황에서 어떤 알고리즘을 적용해야하는지 알아보자.

---

모듈러 연산 %

• 기본적으로, 어떤 숫자를 다른 숫자로 나눈 나머지를 구할 때
• 데이터가 순환하여 반복하는 구조인 경우(원형적 자료구조)

에라토스테네스의 체

• 여러 개의 수가 소수인지 판별할 때

이분 탐색

• 주어진 데이터와 구하려는 값이 서로 반비례 관계일 때

누적합

• 수열의 특정 구간의 합을 빠르계 구할 때

슬라이딩 윈도우

• 고정적인 개수의 구간의 합을 빠르계 구할 때

투 포인터

• 가변적인 개수의 구간의 합을 빠르계 구할 때

그리디(탐욕법)

• 부분적인 단계에서 최선의 선택을 하며 최종 해를 구할 때

브루트포스(완전탐색)

• 가능한 모든 경우의 수를 구하여 도출할 때

백트래킹(가지치기)

• 조건에 만족하지 않는 경우를 걸러내고 탐색할 때
• 완전탐색보다는 효율적인 탐색이 필요할 때

---

가중치에 따른 풀이 방식 분류

알고리즘 문제를 그래프에 적용할 때의 해결 방법을 나열한다.

BFS(너비 우선 탐색) & DFS(깊이 우선 탐색)

• 가중치가 하나로 고정되는 경우

0-1 BFS(Deque 사용)

• 가중치가 0 또는 1만 있는 경우

Dijkstra(다익스트라)

• 가중치가 여러개이고, 0 또는 양수로만 이뤄져 있는 경우

Bellman Ford(벨만 포드)

• 가중치가 여러개이고, 음수도 포함되는 경우

Floyd Warshall(플로이드 워셜)

• 가중치가 여러개이나, 임의의 경로만 찾는 경우

DP(동적 계획)

• 순환성이 없는 그래프에서, 이전 값을 가져와 다음 값을 찾는 경우
• 단방향성을 띠는 자료 형태에서 사용

---