27일차: 알고리즘(Greedy, Brute-Force, Binary Search)

❯ Greedy 알고리즘

탐욕 알고리즘이라고도 하며, 선택의 순간마다 최적의 선택을 해서 해답에 도달하는 방법을 말한다.

<문제 해결 절차>

1. 선택 : 현재 상태에서 최적의 해답 선택

2. 적절성 검사 : 선택된 답이 문제 조건을 만족하는지 검사

3. 해답 검사 : 원래 문제가 해결되었는지 검사하고, 해결이 되지 않았으면 다시 선택단계로 돌아가서 반복함

 

<탐욕 알고리즘의 성립 조건>

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후 선택에 영향을 주지 않아야한다.

2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 해결방법으로 구성된다.

❯ Brute-Force 알고리즘 (완전 탐색)

모든 값을 대입하여 올바른 값을 찾는 방법.

모든 경우를 시도해보는것으로, 공간복잡도나 시간복잡도를 고려하지 않고 어떻게든 해답을 찾으려는 방법을 말한다.

문제가 복잡해질수록 많은 자원을 필요로하는 비효율적인 알고리즘이 될 수 있다.

DFS, BFS, 버블 정렬, 선택 정렬 알고리즘이 이 알고리즘을 활용한 사례이다.

❯ Binary Search 알고리즘 (이진 탐색)

데이터가 정렬된 상탱체서 절반씩 범위를 나누어서 분할정복기법으로 값을 찾아내는 방법.

쉽게 생각할 수 있는 예로  UP/DOWN 게임이 해당한다.

시간복잡도는 O(log n) 이다. 데이터 양이 많을수록 효율이 높다. 그러나 배열에만 적용할 수 있고, 정렬되어있어야한다.

사전 검색, 도서관 검색, 리소스 사항 파악 등이 활용 사례이다.

---

문제를 푸는데 어떤 방식으로 접근하는것이 좋을지 생각해보지 않고, 무조건 답만 찾겠다!!는 태도로 풀고있다고 느꼈다.

이때까지 배운 문제 풀이 방식이 어떤게 있는지 한번 쭉 정리해보고 문제별로 어떤 접근법이 좋을지 먼저 생각해보는 자세가 필요할 것 같다.