파이썬 코딩테스트 강좌, 원하는 정수 찾기

안녕하세요! 이번 강좌에서는 ‘원하는 정수 찾기’라는 알고리즘 문제를 함께 풀어보겠습니다. 이 문제는 n개의 정수로 이루어진 리스트에서 특정 정수를 찾는 문제입니다. 이 과정에서 기본적인 알고리즘 및 데이터 구조에 대해 알아보는 시간을 가질 것입니다. 문제 설정과 함께 해결 방안을 단계별로 설명하겠습니다.

문제 설명

주어진 정수 리스트 nums와 정수 target이 있을 때, target이 리스트 nums에 존재하는 인덱스를 반환하는 함수를 작성하세요. 만약 target이 리스트에 존재하지 않으면 -1을 반환합니다.

입력 예시

  • nums = [2, 5, 1, 8, 3], target = 8 => 반환값: 3
  • nums = [2, 5, 1, 8, 3], target = 4 => 반환값: -1

문제 접근 방법

이 문제를 해결하기 위해 우리는 두 가지 접근 방식을 고려할 수 있습니다: 선형 검색과 이진 검색입니다. 두 방법은 각각의 장단점이 있으며, 성능을 비교해보는 것도 좋은 학습이 될 것입니다.

1. 선형 검색

선형 검색은 리스트를 처음부터 끝까지 순차적으로 탐색하면서 target을 찾는 방법입니다. 시간 복잡도는 O(n)입니다.

선형 검색 구현

def linear_search(nums, target):
    for index in range(len(nums)):
        if nums[index] == target:
            return index
    return -1

위 코드에서 for 루프는 리스트의 각 요소를 하나씩 확인합니다. target과 같은 요소를 찾으면 해당 인덱스를 반환하며, 리스트의 끝까지 탐색해도 찾지 못하면 -1을 반환합니다.

2. 이진 검색

이진 검색은 정렬된 리스트에서 사용할 수 있는 효율적인 검색 방법입니다. 리스트를 중간값과 비교하며 검색 범위를 절반으로 줄여나갑니다. 시간 복잡도는 O(log n)입니다. 따라서 이 방법은 검색 효율성이 중요한 경우 유용합니다.

이진 검색 구현

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

위의 이진 검색 구현에서는 left와 right 변수를 사용하여 리스트의 검색 범위를 조정합니다. 매 루프마다 중간값을 계산하고, 이 값과 target을 비교하여 검색 범위를 조정합니다.

문제 해결 과정

이제 주어진 문제를 해결하기 위해 두 개의 접근 방식을 모두 구현하고, 성능을 비교해보겠습니다.

성능 비교

선형 검색과 이진 검색의 성능을 비교하기 위해, 각 검색 알고리즘을 일정한 크기의 리스트 데이터에 대해 수행해보겠습니다. 다음은 성능 비교를 위한 테스트 코드입니다.

import random
import time

# 데이터 생성
size = 1000000
nums = sorted(random.sample(range(1, 10000000), size))
target = random.choice(nums)

# 선형 검색 성능 테스트
start_time = time.time()
print("Linear Search Result: ", linear_search(nums, target))
print("Linear Search Time: ", time.time() - start_time)

# 이진 검색 성능 테스트
start_time = time.time()
print("Binary Search Result: ", binary_search(nums, target))
print("Binary Search Time: ", time.time() - start_time)

위 코드를 실행하면 두 검색 알고리즘의 수행 시간과 결과를 확인할 수 있습니다. 대체로 이진 검색이 더 빠른 성능을 보일 것입니다.

결론

이번 강좌에서는 ‘원하는 정수 찾기’ 문제를 선형 검색과 이진 검색 두 가지 방법으로 해결해보았습니다. 각각의 알고리즘이 어떻게 작동하는지, 그리고 어떤 상황에서 사용해야 하는지에 대해 알아보았으니, 실제 코딩 테스트나 알고리즘 문제 풀이에 있어 큰 도움이 될 것입니다.

앞으로도 다양한 알고리즘 문제를 통해 코딩 능력을 향상시켜 나가시길 바랍니다. 감사합니다!