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

수경·2022년 11월 27일
0

코드스테이츠

목록 보기
30/57

브루트 포스 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)

profile
어쩌다보니 tmi뿐인 블로그😎

0개의 댓글