검색 알고리즘이란 무엇일까?
검색(Searching)은 배열이나 리스트 같은 데이터 집합에서 특정 값(또는 조건에 맞는 요소)을 찾아내는 과정이다.
예를 들어, 반에서 학생들 이름이 적힌 명단이 있을 때 "철수"라는 이름을 찾는 것과 비슷하다.
왜 검색이 필요할까?
- 데이터 찾기 : 많은 데이터 중에서 필요한 정보를 빠르게 찾기 위해 사용된다.
- 알고리즘 문제 : 코딩 테스트에서 특정 값을 찾는 문제가 출제된다.
- 효율성 : 올바른 검색 알고리즘을 사용하면 데이터의 양이 많더라도 빠른 시간 안에 원하는 값을 찾을 수 있다.
1. 선형 검색(Linear Search)
배열의 첫 번째 요소부터 순서대로 하나씩 검사하면서 찾고자 하는 값과 일치하는지 확인한다.
특징
- 간단하고 구현하기 쉽다
- 데이터가 정렬되어 있지 않아도 사용할 수 있다.
- 최악의 경우 모든 요소를 확인해야 하므로, 시간 복잡도는 O(n)이다.
// 선형 검색 함수: 배열에서 target 값을 찾으면 해당 인덱스를 반환하고, 없으면 null 반환
fun linearSearch(arr: Array<Int>, target: Int): Int? {
for (i in arr.indices) {
if (arr[i] == target) {
return i // 찾은 경우 해당 인덱스 반환
}
}
return null // 값이 없으면 null 반환
}
fun main() {
val numbers = arrayOf(5, 3, 8, 4, 2, 10)
val target = 4
val index = linearSearch(numbers, target)
if (index != null) {
println("선형 검색: $target 값은 인덱스 $index 에 있습니다.")
} else {
println("선형 검색: $target 값을 찾을 수 없습니다.")
}
}
// arr.indices 는 배열의 인덱스 범위를 반환한다.
// 각 요소를 순차적으로 검사하여, target 값과 일치하면 해당 인덱스를 반환한다.
2. 이진 검색(Binary Search)
정렬된 배열을 반으로 나누어 원하는 값이 어느 쪽에 있는지 판단하여 검색 범위를 좁혀가는 방식이다.
특징
- 배열이 정렬되어 있어야 사용할 수 있다.
- 매 반복마다 검색 범위가 절반으로 줄어들기 때문에, 시간 복잡도는 O(log n)으로 매우 효율적이다.
// 이진 검색 함수: 정렬된 배열에서 target 값을 찾으면 해당 인덱스를 반환, 없으면 null 반환
fun binarySearch(arr: Array<Int>, target: Int): Int? {
var low = 0
var high = arr.size - 1
while (low <= high) {
val mid = (low + high) / 2 // 중간 인덱스 계산
when {
arr[mid] == target -> return mid // 중간 값이 target이면 반환
arr[mid] < target -> low = mid + 1 // target이 더 크면 오른쪽 범위로 좁힘
else -> high = mid - 1 // target이 더 작으면 왼쪽 범위로 좁힘
}
}
return null // target 값을 찾지 못하면 null 반환
}
fun main() {
val sortedNumbers = arrayOf(2, 3, 4, 5, 8, 10) // 이진 검색을 위해 정렬된 배열 필요
val target = 5
val index = binarySearch(sortedNumbers, target)
if (index != null) {
println("이진 검색: $target 값은 인덱스 $index 에 있습니다.")
} else {
println("이진 검색: $target 값을 찾을 수 없습니다.")
}
}
// 배열이 정렬되어 있다는 전제하에, low와 high 인덱스를 사용해 중간 mid을 계산한다.
'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글
| Kotiln 연습하기(9) - DFS / BFS (1) | 2025.04.11 |
|---|---|
| Kotlin 연습하기(7) - 동적 계획(DP) (0) | 2025.04.07 |
| Kotlin 연습하기(5) - 버블정렬 (0) | 2025.04.02 |
| Kotlin 연습하기(4)-재귀함수 (0) | 2025.03.31 |
| Kotlin 연습하기(3) (0) | 2025.03.27 |