안녕하세요! 이번 강좌에서는 취업용 알고리즘 시험에서 자주 등장하는 이진 탐색 알고리즘에 대해 알아보고, 코틀린을 이용하여 문제를 해결하는 과정을 자세히 설명하겠습니다. 이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘으로, 시간 복잡도가 O(log n)입니다. 이 강좌에서는 이진 탐색을 활용한 문제를 풀어보고, 문제 해결 과정을 세세히 다루겠습니다.
문제 설명
문제: 정렬된 배열과 특정 값이 주어질 때, 해당 값의 인덱스를 찾으세요.
만약 값이 배열에 존재하지 않는다면 -1을 반환해야 합니다.
입력:
- arr: 정수로 이루어진 오름차순 정렬된 배열
- target: 찾고자 하는 정수
출력:
- target의 인덱스 (존재하지 않으면 -1)
입력 예시
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
출력 예시
4
이진 탐색 알고리즘 개요
이진 탐색 알고리즘은 조건에 따른 두 개의 분기로 탐색 범위를 줄이는 방식입니다. 가장 일반적인 이진 탐색의 구현은 다음과 같은 단계를 포함합니다.
- 배열의 시작 인덱스와 끝 인덱스를 정합니다.
- 중간 인덱스를 계산합니다.
- 중간 값과 찾고자 하는 값(target)을 비교합니다.
- 중간 값이 target보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 탐색합니다.
- 값을 찾거나, 탐색 범위가 없어질 때까지 반복합니다.
코틀린 구현
이제 코틀린을 사용하여 이진 탐색을 구현해 보겠습니다.
fun binarySearch(arr: IntArray, target: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
if (arr[mid] == target) {
return mid // 찾은 경우 인덱스를 반환
} else if (arr[mid] < target) {
left = mid + 1 // 오른쪽 탐색
} else {
right = mid - 1 // 왼쪽 탐색
}
}
return -1 // 없으면 -1 반환
}
문제 풀이 과정
이제 문제의 예시를 가지고 이진 탐색 알고리즘을 적용해 보겠습니다.
예제 분석
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
이진 탐색의 시작 인덱스는 0, 끝 인덱스는 8입니다. 중간 인덱스를 계산해 보겠습니다:
mid = left + (right - left) / 2
= 0 + (8 - 0) / 2
= 4
arr[4]의 값은 5입니다. 타겟 값과 일치하므로, 인덱스 4를 반환합니다.
성능 분석
이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 탐색 범위가 절반으로 줄어들기 때문인데, 예를 들어 배열의 원소가 8개이면 3번의 비교로 찾을 수 있습니다. 이진 탐색은 많은 수의 데이터를 탐색하는 데 매우 효율적입니다.
결론
이번 강좌에서 우리는 이진 탐색 알고리즘의 개념과 코틀린에서의 구현 방법을 배웠습니다. 이 알고리즘은 정렬된 배열에서 특정 값을 효과적으로 찾는 데 유용합니다. 알고리즘 문제를 풀 때는 문제를 이해하고, 적절한 알고리즘을 선택하는 것이 중요합니다.
더 많은 문제를 해결하고 알고리즘을 연습해 보세요!