순차 탐색
이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다.
순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
- 시간복잡도: O(n)
- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.
- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다.
이진 탐색(Binary Search)
이진 탐색이란 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아나가는 알고리즘이다.
- 시간복잡도: O(logN)
- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
- 매우 빠르게 데이터를 찾을 수 있다.
과정
1. 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점 3가지 변수를 사용한다. 시작점과 끝점을 확인한 다음 둘 사이에 중간점(중간점이 실수일 때는 소수점을 버린다)을 정한다. 여기서 중간점은 7이다.
2. 그 다음 중간점 7과 찾으려는 데이터 11을 비교한다. 찾으려는 데이터가 더 크므로 중간점 이전의 값은 확인할 필요가 없다. 시작점을 9로 옮긴다.
3. 이때, 중간점이 11이 되고, 찾으려는 데이터와 동일하므로 이 시점에서 탐색을 종료한다.
구현 방법 2가지
[1. 재귀 함수를 이용하는 방법]
// 이진 탐색 소스코드 구현(재귀 함수)
public static int binarySearch(int[] arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else return binarySearch(arr, target, mid + 1, end);
}[2. 반복문 이용하는 방법]
// 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) end = mid - 1;
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else start = mid + 1;
}
return -1;
}💡 코딩테스트에서 이진탐색
- 코딩 테스트에서 자주 나오는 문제이니 암기하자! 더불어 코딩 테스트의 이진 탐색 문제는 탐색 범위가 큰 상황에서의 가정하는 문제가 많다. 따라서 탐색 범위가 2000만을 넘어가면 이진 탐색으로 문제에 접근해보길 권한다. 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.
트리 자료구조
노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고있는 개체이다.
- 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.
- 트리는 부모 노드와 자식 노드의 관계로 표현한다.
- 트리의 최상단 노드를 루트 노드라고 한다.
- 트리의 최하단 노드를 단말 노드라고 한다.
- 트리에서 일부를 떼어내도 트리구조이며 이를 서브 트리라 한다.
이진 탐색 트리
위와 같은 트리 자료구조에 데이터를 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다. 어떤 방식으로 이진 탐색을 할까?
이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
조회 과정
- 찾는 원소 값이 5이다. 이진 탐색은 루트 노드부터 방문한다. 부모 노드의 오른쪽 자식 노드는 8 이상이므로 오른쪽에 있는 모든 노드는 확인할 필요가 없다. 따라서 왼쪽 노드를 방문한다.
- 왼쪽 자식 노드인 3이 이번에는 부모 노드이다. 3은 5보다 작다. 따라서 오른쪽 노드에 방문한다.
- 현재 방문한 노드 값인 5와 찾는 원소 값이 5로 동일하다. 따라서 탐색을 마친다.
열심히 달리는 개발자