최근 취업 시장에서 코딩 테스트는 필수적인 요소가 되었습니다. 많은 기업들이 지원자의 문제 해결 능력과 알고리즘적 사고를 평가하는 도구로 코딩 테스트를 활용하고 있습니다. 본 강좌에서는 ‘사전 찾기’라는 주제를 통해 알고리즘 문제를 해결하는 과정을 자세히 설명하겠습니다. 이 문제를 통해 문자열 처리, 정렬, 그리고 자료구조에 대한 이해를 높일 수 있습니다.
문제 설명
사전에서 단어를 찾는 일반적인 문제를 확장해보겠습니다. 주어진 단어 리스트와 특정 단어를 입력받았을 때, 그 단어가 사전에서 몇 번째 위치에 있는지를 찾는 문제입니다. 하지만 여기서는 사전이 정렬된 상태라는 전제가 주어집니다. 정렬된 단어 리스트가 주어질 때, 입력받은 단어는 사전에서 몇 번째 위치에 있는지를 반환하는 알고리즘을 구현해야 합니다.
문제 정의
fun findWordIndex(dictionary: List, target: String): Int {
// 반환할 인덱스를 초기화합니다.
// 만약 단어가 없다면 -1을 반환합니다.
}
입력
- dictionary: 정렬된 문자열 리스트 (사전)
- target: 찾고자 하는 문자열
출력
target이 사전에서 발견되면 해당 단어의 인덱스를 반환합니다. 찾지 못한 경우 -1을 반환합니다.
예제
Input: dictionary = ["apple", "banana", "grape", "kiwi", "melon"], target = "kiwi"
Output: 3
Input: dictionary = ["apple", "banana", "grape", "kiwi", "melon"], target = "orange"
Output: -1
문제 해결 과정
이 문제는 이진 탐색 알고리즘을 사용할 수 있는 좋은 대상입니다. 이진 탐색은 정렬된 리스트에서 특정 값을 빠르게 찾을 수 있는 알고리즘으로, 시간 복잡도는 O(log n)입니다. 아래에 문제를 풀기 위한 단계별 접근 방식을 설명하겠습니다.
1단계: 이진 탐색 알고리즘 이해하기
이진 탐색의 기본 아이디어는 ‘중간값’을 이용하여 탐색 범위를 반으로 줄이는 것입니다. 이진 탐색은 차례로 다음과 같은 과정을 거칩니다:
- 리스트의 시작 인덱스와 종료 인덱스를 설정합니다.
- 중간 인덱스를 계산하여 중간값을 확인합니다.
- 중간값과 찾고자 하는 값(target)을 비교합니다.
- 중간값이 target보다 작다면, 시작 인덱스를 중간 인덱스 + 1로 이동시킵니다.
- 중간값이 target보다 크다면, 종료 인덱스를 중간 인덱스 – 1로 이동시킵니다.
- 다시 중간 인덱스를 계산하여 2~5단계를 반복합니다.
- target이 리스트에 있는 경우 인덱스를 반환하고, 종료 인덱스가 시작 인덱스보다 작아지면 -1를 반환합니다.
2단계: 코틀린으로 이진 탐색 구현하기
이제 위의 이진 탐색 알고리즘을 코틀린으로 구현해보겠습니다:
fun findWordIndex(dictionary: List, target: String): Int {
var start = 0
var end = dictionary.size - 1
while (start <= end) {
val mid = (start + end) / 2
when {
dictionary[mid] == target -> {
return mid
}
dictionary[mid] < target -> {
start = mid + 1
}
else -> {
end = mid - 1
}
}
}
return -1 // target이 리스트 내에 존재하지 않음
}
3단계: 테스트 케이스 작성하기
이제 구현한 알고리즘이 올바르게 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 작성하겠습니다:
fun main() {
val dictionary = listOf("apple", "banana", "grape", "kiwi", "melon")
println(findWordIndex(dictionary, "kiwi")) // 정답: 3
println(findWordIndex(dictionary, "orange")) // 정답: -1
println(findWordIndex(dictionary, "banana")) // 정답: 1
println(findWordIndex(dictionary, "apple")) // 정답: 0
println(findWordIndex(dictionary, "melon")) // 정답: 4
}
결론
이 강좌에서는 ‘사전 찾기’라는 알고리즘 문제를 코틀린을 사용하여 해결하는 방법을 배웠습니다. 이진 탐색을 활용하여 주어진 문제를 효율적으로 해결하는 방법을 이해했으며, 이를 통해 문자열 탐색 문제에서의 기초적인 알고리즘 기술을 다질 수 있었습니다. 알고리즘 문제를 푸는 과정은 반복 연습을 통해 더욱 향상될 수 있으므로, 다양한 문제를 풀어보며 경험을 쌓아가기를 바랍니다.
감사합니다!