[section 2] 알고리즘(4) - 브루트 포스, 이진 탐색, DP

브루트 포스 Brute-Force Algorithm

가능한 모든 경우를 탐색하여 문제를 해결하는 방법

장점

• 알고리즘 설계와 구현이 쉬움
• 복잡한 알고리즘이 필요 없음

단점

• 데이터의 범위가 커질수록 비효율적
• 메모리 효율면에서 매우 비효율적
• 최악의 경우 매우 비효율적

종류

• 선형 구조 : 순차 탐색
• 비선형 구조 : 백트래킹, DFS, BFS

---

이진 탐색 Binary Search Algorithm

데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

조건

1. 배열
2. 정렬되어 있어야 함

방법

배열의 [현재 인덱스/2]에 접근하여 탐색

➡️ O(log n)
➡️ 가장 빠른 시간복잡도를 가지지만, 항상 최적의 해를 보장하진 않음
❗️데이터의 크기가 작은 경우 선형 탐색이 적합

---

DP (Dynamic Programming)

재귀함수로 풀어냈을 때, 지나친 중복이 발생하는 경우에 이를 피하기 위해 사용하는 알고리즘

방법

보통 배열에 값을 저장하고, 저장한 값으로 답을 도출하는 방식

예시 - 피보나치 수열

피보나치 수열 : f(n) = f(n - 1) + f(n - 2)