키워드
자료구조를 사용하는 이유? 많은 양의 데이터를 효율적으로 저장하고 찾을 수 있다!
완전탐색(Brute Force)와 그리디 알고리즘(Greedy Algorithm)
1. 완전 탐색
정의
- 가능한 모든 경우의 수를 전부 확인하여 문제를 해결하는 방법
= 가능한 모든 방법을 일일이 다 해보는 것
장점
- 구현이 단순하고 이해하기 쉽다
- 모든 경우를 확인하므로 반드시 답을 찾을 수 있다
단점
- 실행시간이 오래걸린다
- 경우의 수가 늘어나면 현실적으로 해결하기 어려워짐
그리디 알고리즘
정의
- 현재 상황에서 가장 좋아보이는 것을 선택
= 각 단계에서 최적이라고 생각되는 것을 선택하기!
즉, 그때그때 좋아보이는거 고르는거지 회의실 문제에서는 그때그때 젤 빨리끝나는거 골랐음
장점
- 구현이 단순하고 실행 속도가 빠르다
- 직관적이다
단점
- 항상 최적해를 찾을 순 없다
- 각 단계에서의 최적의 선택이 전체의 최적 해가 아닐 수 있다
=> 특정 조건에서만 최적해가 보장된다
배열
for-each로 빠르게 직접 값 참조를 할 수 있다 원소 골라서 할 순 없으니까
int[] scores = {1,2,3,4,5};
for(int score: scores){
sout(score);//1,2,3,4,5
}이진탐색 : 매 단계마다 탐색 범위를 절반으로 줄여가며 검색을 수행
단, 정렬된 배열에서만 가능하다!
