파이썬 코딩테스트 강좌, 사전 찾기

문제 설명

입력 형식

• 단어 목록: words (리스트 형태, 각 단어는 문자열로 구성)
• 찾고 싶은 단어: target (문자열)

출력 형식

목록에서 찾고 싶은 단어의 인덱스 (0-based index)를 리턴. 단어가 존재하지 않으면 -1을 리턴.

예제

    입력: 
    words = ["apple", "banana", "cherry", "date", "fig", "grape"]
    target = "cherry"

    출력: 2
    

문제 접근

이 문제는 이진 탐색(Binary Search) 알고리즘을 사용하여 해결할 수 있습니다. 이진 탐색은 정렬된 데이터에서 특정 값을 빠르게 찾는 데 유용한 알고리즘으로, 시간 복잡도는 O(log n)입니다.

이진 탐색 알고리즘 개요

이진 탐색은 다음과 같은 절차로 진행됩니다:

1. 리스트의 중간 요소를 찾습니다.
2. 중간 요소가 찾고자 하는 값과 일치하는지 확인합니다.
3. 일치하면 중간 요소의 인덱스를 리턴합니다.
4. 일치하지 않으면 찾고자 하는 값이 중간 요소보다 작으면 중간 요소 이전 부분에서, 크면 중간 요소 이후 부분에서 검색을 계속합니다.
5. 이 조건을 만족할 때까지 위의 과정을 반복합니다.

구현

여기서는 파이썬을 사용하여 이진 탐색 알고리즘을 구현하겠습니다. 아래는 이진 탐색을 사용한 사전 찾기 함수입니다.

def binary_search(words, target):
    left, right = 0, len(words) - 1

    while left <= right:
        mid = (left + right) // 2
        if words[mid] == target:
            return mid
        elif words[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

코드 설명

위의 binary_search 함수는 다음과 같이 작동합니다:

1. left와 right 변수를 사용하여 검색 범위를 설정합니다. 초기값은 각각 0과 len(words) - 1입니다.
2. while left <= right 루프를 사용하여 검색 범위가 유효할 때까지 반복합니다.
3. 중간 인덱스 mid를 계산합니다 (정수 나누기를 통해).
4. 만약 words[mid]가 target와 같다면 mid를 리턴하여 인덱스를 반환합니다.
5. 그렇지 않으면 words[mid]가 target보다 작으면 left를 mid + 1으로 업데이트하고, 크면 right를 mid - 1로 업데이트합니다.
6. 모든 반복이 끝났는데도 찾고자 하는 단어가 없으면 -1을 리턴합니다.

테스트 케이스

코드의 기능을 테스트하기 위해 몇 가지 케이스를 추가해보겠습니다.

if __name__ == "__main__":
    words = ["apple", "banana", "cherry", "date", "fig", "grape"]
    target = "cherry"
    result = binary_search(words, target)
    print(f"'{target}'는 인덱스 {result}에 있습니다.")  # 출력: 'cherry'는 인덱스 2에 있습니다.

    target = "orange"
    result = binary_search(words, target)
    print(f"'{target}'는 인덱스 {result}에 있습니다.")  # 출력: 'orange'는 인덱스 -1에 있습니다.
    

결론

이번 강좌에서는 파이썬의 이진 탐색 알고리즘을 사용하여 주어진 사전에서 특정 단어를 찾는 문제를 해결했습니다. 이 알고리즘은 정렬된 리스트에서 빠르게 값을 찾는 데 유용하며, 다양한 문제에 적용할 수 있습니다. 이진 탐색을 이해하고 활용하는 능력은 코딩 테스트 및 실제 프로그래밍에서 큰 도움이 됩니다.

참고 자료

• 위키백과 – 이진 탐색
• Geeks for Geeks – Binary Search