[자료구조] 완전탐색, 이분탐색

완전 탐색(brute force)은 말 그대로 가능란 모든 곳을 탐색한다는 의미이다.

이해를 돕기 위해 예시를 들자면, 10개의 안이 보이지 않는 상자가 있고, 그중 일부의 상자에는 사과가 있다.

상자가 안이 보이지 않기 때문에, 총 몇개의 사과가 있는지 확인하기 위해서는 10개의 상자를 모두 열어봐야 한다.

이런 종류의 탐색을 완전 탐색이라 부른다.

 

완전 탐색은 결과 값이 가장 확실하지만, 모든 경우의 수를 다 확인해야 하기 떄문에 시간이 가장 오래 걸리는 탐색 방법이다.

 

예시 문제로는 다음과 같은 문제들이 있다.

https://programmers.co.kr/learn/courses/30/lessons/42840

코딩테스트 연습 - 모의고사

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

---

이분 탐색(binary search)은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 방법 중의 하나이다.

우리가 인덱스가 붙지 않은 종이사전에서 Cat이라는 단어를 찾고자 한다고 가정하자, 대충 중간 지점을 펼쳤을 때 O가 나왔다면 우리는 그다음 탐색은 어떻게 해야 할까? 당연히 앞 부분 부터 아까의 중간 지점 중에 다시 중간 지점을 펼쳐볼 것이다. 그렇게 중간지점을 탐색하며 탐색하는 범위를 줄여가면 우리가 원하는 C라는 값을 찾는 것이 처음 부터 찾는 것보다 덜 수고로울 것이다. 이분탐색은 바로 이 아이디어를 코드화하면 되는 개념이다. 

 

여기서 주의할 점은 꼭 배열이 정렬되어 있어야 사용 가능하다는 것이다. 만약 정렬되지 않았고, 정렬+이분탐색이 다른 탐색방법을 이용하는 것보다 비효율적(시간복잡도가 높음)이라면 다른 탐색방법을 사용하는 것이 바람직할 것이다.

 

이분탐색의 예시 문제는 아래와 같은 문제들이다.

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2