[알고리즘] 알고리즘 패러다임에 대해서 알아보자!

알고리즘을 문제를 풀다보면 다양한 풀이방식이 존재하는데 그 풀이 방식을 알고리즘 패러다임이라고 한다. 

각 패러다임은 특정 유형의 문제를 해결하는 데 특화되어 있으며, 알고리즘을 더 효율적으로 구현하는 데 도움을 준다. 

주요 알고리즘 패러다임에 대해서 알아보자!

 

 

Brute Force 무차별 대입

어떤 문제에 대해서 가능한 모든 경우의 수를 시도하는 단순한 방법 

 

직관적이고 답을 확실하게 알 수 있다. BUT 인풋이 큰 경우에는 매우 비효율적이다. 

 

▶️ 완전 탐색, 순열/조합 문제 

 

 

 

Backtracking 백트래킹

문제를 해결하기 위해 모든 가능한 경우의 수를 탐색하되, 해답이 될 가능성이 없는 경로는 탐색을 중단하고 이전 단계로 돌아가 다른 경로를 탐색하는 방법

 

▶️ N-Queen 문제, 미로 탐색

 

 

 

Divide and Conquer 분할 정복

문제를 더 작은 부분으로 나누고, 각 부분 문제를 해결한 뒤 결과를 합쳐 전체 문제를 해결하는 방법

 

 부분 문제가 여전히 크다면 계속 쪼개는 방식으로 재귀적으로 접근한다.

 

▶️ Merge Sort, Quick Sort, 이진 탐색

 

 

 

Dynamic Programming 동적 계획법

문제를 부분 문제로 나누어 해결하고, 중복되는 계산을 줄이기 위해 이전 계산 결과를 저장하여 문제를 해결하는 방법

 

이 방법을 사용하기 위해서 만족해야할 조건  2가지가 있다. 
1. 최적부분문제 구조여야한다. ( 부분 문제의 최적 해를 이용해 전체 문제를 해결할 수 있음.)

2. 중복되는 부분 문제여야한다.  ( 같은 부분 문제를 여러 번 계산하는 상황 발생.)

 

구현 방식 또한 2가지가 있다. 

1. Memoization: 재귀를 이용하여 이전 계산 결과를 저장.

2. Tabulation: 반복문을 사용해 이전 계산 결과를 테이블에 저장

 

 

 

 

▶️ 피보나치 수열, 출발지부터 목적지까지의 최단 경로 찾기(Dijkstra's Algorithm)

 

 

Greedy Algorithm 탐욕 알고리즘

 

미래를 고려하지 않고, 현재 상황에서 가장 최적의 선택을 반복하여 문제를 해결하는 방법

 

간단하고 빠르지만 완벽한 정답이 보장되지 않는다. 

 

그리디 알고리즘이 최적의 답을 보장해주려면 문제의 조건이 

1. 문제가 최적부분문제 구조여야한다. 

2. 각 단계에서의 최적의 선택이 최종 답을 구하기 위한 최적의 선택이어야한다. 

 

▶️ 최대한 적은 동전으로 거슬러 주는 문제, Kruskal's Algorithm, Prim's Algorithm (최소 신장 트리)