[TIL] 코드스테이츠 SEB BE Day 26

in TIL

💡 Today I Will Learn

  • Brute-Force Algorithm
  • Binary Search Algorithm

✏️ Summary

BFA (Brute-Force Algorithm)

모든 경우를 시행하여 문제를 해결한다. 시간복잡도 및 공간복잡도를 고려하지 않고 해결방법을 찾는다.

BFA의 한계

문제가 복잡할수록 상당히 많은 자원을 필요로 하여 비효율적일 수 있다.

BFA의 사용예제

1. 순차 검색 (Sequential Search): 배열안의 요소를 순차적으로 검색할 때
2. 문자열 매칭: 찾고자하는 문자열이 해당 문자열에 존재하는 지 순차적으로 검색할 때
3. 정렬: 선택정렬, 삽입정렬, 버블정렬과 같은 알고리즘

BSA (Binary Search Algorithm)

Divide & Conquer (분할정복법)으로 문제를 푸는 방식으로 아래 단계와 같다.

1. 배열 중간의 인덱스(mid)를 저장
2. mid가 찾는 target이라면 return
3. mid보다 크거나, 작으면 start 및 end를 다시 설정한다.

  • 오름차순 및 내림차순된 배열에서의 검색에 사용한다.
  • 데이터 양이 많을수록 효율적이다.
  • 찾고자하는 데이터가 양끝에 존재할 때 가장 비효율적이다.

BSA 사용예제

  • 도서관의 도서코드를 통한 검색
  • 사전 검색

📌 정리

알고리즘 뒷 파트로 오면서 개인적으로 어려운 DP 문제들을 맞닥뜨렸다. 사실 어렵다 생각하는 이유가 앞서 그리디처럼 많이 접해보지 않아서라 생각된다.

이번 알고리즘 파트부터 Daily Coding이 아침마다 계속 되는데, 추가적으로 Greedy, DP 문제도 많이 풀어봐야겠다👍

🎯 Tomorrow

  • Algorithm in Math

Back to [TIL] 코드스테이츠 SEB BE Day 25