들어가며
개발자의 길을 걸은 이후 프로젝트 요구사항에 따른 기능 구현에만 초점을 맞추어 공부를 진행해왔었습니다. 그때그때 문제가 발생할 때마다 구글링을 통해 어떻게든 문제를 해결했습니다. 그러나 그마저도 다른 사람들이 해결한 방법을 적용하는 것에 급급할 따름이었습니다.
문제 해결력을 키우고 싶어 알고리즘을 공부해야 겠다고 느끼게 되었고, 이 포스팅이 바로 그 시작점입니다.
회사 생활을 하는 탓에 매일 포스팅을 올리지는 못하겠지만 앞으로 학습한 개념들을 하나씩 정리하며 포스팅할 계획입니다.
알고리즘은 개념 학습에만 그치면 겉핥기 학습 밖에 되지 않습니다. 직접 문제를 풀어보는 게 매우 중요하므로 백준 문제 풀이 또한 포스팅할 계획입니다.
여러 블로그 글을 참조하며 공부하고 정리한 내용이니 약간의 오류가 있을 수 있습니다.
혹시나 잘못된 지식이 들어가 있다면 댓글로 남겨주셨으면 합니다.
이진 탐색(Binary Search) 란?
이진 탐색은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다.
해당 값을 찾을 때까지 이 과정을 반복한다.
이진 탐색 예시
오름차순으로 정렬된 배열이 있다.
{26, 27, 42, 66, 89, 93, 101}
이 배열에서 이진 탐색을 이용하여 42의 값을 찾아보자.
- 첫 번째 시도선택한 값 66과 찾고자 하는 값 42를 비교한다.
- 42 < 66이므로 42는 66의 좌측에 존재한다는 것을 알 수 있다.
- 우선 가운데 위치한 임의의 값 66을 선택한다.
- 두 번째 시도{17, 28, 43}28 < 43 이번에는 28이 43보다 작으므로 28 우측에 위치하는 것을 알 수 있다.
- 마찬가지로 가운데의 임의의 값 28을 선택한다.
- 66을 기준으로 좌측에 있는 배열 값들을 대상으로 다시 탐색을 진행한다.
- 세 번째 시도{43}
- 배열에 값이 하나만 남게 되고 값을 확인해보면, 43 === 43 원하는 값을 찾았다.
- 28의 우측을 기준으로 배열을 다시 설정해보면
- 종료 조건만약 원하는 값이 배열에 존재하지 않는다면 어떻게 종료될까?
- 원하는 값이 탐색하고자 하는 배열에 더이상 존재하지 않으면 탐색을 종료한다.
- 탐색의 종료 조건은 원하는 값을 찾으면 종료된다.
이진 탐색 소스코드 구현 방법
인덱스의 최소, 최대 값을 따로 저장하여 탐색이 진행될 때마다 갱신하고 탐색하는 배열의 범위를 줄여나간다.
구현 방법은 두 가지가 존재한다.
- 반복문을 이용한 방법
const BSearch = (arr: number[], target: number) => {
let low = 0;
let high = arr.length - 1;
let mid;
while(low <= high) {
mid = Math.floor((low + high) / 2);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}- 재귀함수를 이용한 방법
const BSearchRecursive = (arr: number[], target: number, low: number, high: number) => {
if (low > high) return -1;
const mid = Math.floor((low + mid) / 2);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return BSearchRecursive(arr, target, low, mid-1);
} else {
return BSearchRecursive(arr, target, low+1, high);
}
}이진 탐색 시간 복잡도 및 빅오 표기
위에서 사용했던 배열에 원소 몇 개를 추가해서 다시 17을 이진 탐색으로 찾아보자.
{ 17, 26, 27, 42, 66, 89, 93, 101 }
중간 값 : 66 → 작다 → { 17, 26, 27, 42 }
중간 값 : 27 → 작다 → { 17, 26 }
중간 값 : 26 → 작다 → { 17 }
중간 값 : 17 → 종료
이진 탐색이란 이름이 붙여진 이유는 처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반으로 줄어들기 때문이다.
맨 처음 원소의 개수가 8에서 4, 2, 1 로 반씩 점차 줄어드는 것을 확인할 수 있다.
즉, 위의 경우 N=8일 때 탐색이 3회 수행됐으므로 시간 복잡도는 3이 된다.
일반화하여 생각해보자. N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, …, 1 로 실행될 것이다.
여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면, K는 N에 대해 어떻게 나타낼 수 있을까?
1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N
즉, 이진 탐색의 시간 복잡도는 O(logN)이 된다.
이진 탐색은 언제 사용하기 좋은가?
이진 탐색은 정렬된 데이터에서 특정한 값을 찾고자 할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다.
다음은 입력받는 숫자의 제곱근을 구하는 코드이다.
const squareRootLoop = (n: number) => {
let min = 0;
let max = n;
let guess;
while (min <= max) {
guess = Math.floor((min + max) / 2);
if (guess * guess == n) {
return guess;
} else if (guess * guess > n) {
max = guess - 1;
} else {
min = guess + 1;
}
}
return -1;
}
이진 탐색 정리
- 오름차순으로 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.
- 배열의 중간을 기준으로 데이터를 탐색한다.
- 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다.
- 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값들은 탐색에서 제외된다.
- 이진 탐색의 시간 복잡도는 O(logN)이다.