탐색 알고리즘 문제

9.1 선형 탐색과 이진 탐색을 이용한 문제 예시

선형 탐색

배열에서 요소를 찾기 문제: 숫자 배열과 목표값이 주어졌을 때, 배열에서 목표값의 인덱스를 찾아야 해.

해결책: 각 배열 요소를 검사하기 위해 선형 탐색을 사용해.

구현 예시:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 사용 예시:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # 출력: 2

이진 탐색

정렬된 배열에서 요소를 찾기 문제: 정렬된 숫자 배열과 목표값이 주어졌을 때, 배열에서 목표값의 인덱스를 찾아야 해.

해결책: 배열을 반으로 나누어 목표값을 찾기 위해 이진 탐색을 사용해.

구현 예시:

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

# 사용 예시:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # 출력: 3

9.2 탐색 최적화를 위한 해시 테이블 사용 문제

1. 배열에서 중복 요소 찾기

문제: 숫자 배열이 주어졌을 때, 배열에서 중복 요소를 모두 찾아 반환해야 해.

해결책: 이미 나온 숫자를 추적하기 위해 해시 테이블을 사용해. 만약 숫자가 다시 나오면, 중복 목록에 추가해.

구현 예시:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 사용 예시
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 출력: [2, 4]

2. 주어진 합과의 쌍 찾기

문제: 숫자 배열과 목표 합이 주어졌을 때, 목표 합을 만드는 모든 숫자 쌍을 찾아야 해.

해결책: 숫자를 저장하고 현재 숫자와 목표 합을 만드는 쌍이 되는지를 확인하기 위해 해시 테이블을 사용해.

구현 예시:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 사용 예시
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 출력: [(1, 5), (7, -1), (1, 5)]

9.3 다양한 탐색 방법의 결합 사용

복잡한 문제에서는 최적의 효율성을 위해 여러 탐색 방법을 함께 사용하는 것이 필요해. 선형 탐색, 이진 탐색, 해시 테이블의 결합 사용은 문제를 더 효과적이고 유연하게 풀 수 있게 해줘.

예시 1: 배열에서 요소를 찾고 다른 배열에서 그 존재를 확인하기

두 개의 숫자 배열이 주어졌을 때, 첫 번째 배열의 요소 중 두 번째 배열에 존재하는 요소를 찾아야 해.

해결책:

• 두 번째 배열의 요소들을 저장하기 위해 해시 테이블을 사용해.
• 첫 번째 배열의 각 요소에 대해 해시 테이블에 그 존재 여부를 확인해.

구현 예시:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # 두 번째 배열의 해시 테이블
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# 사용 예시:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # 출력: [3, 4, 5]

예시 2: 해시 테이블을 이용하여 아나그램 부분 배열 확인하기

문자열 배열과 패턴 문자열이 주어졌을 때, 배열 내의 어떤 부분 문자열이 패턴의 아나그램인지 확인해야 해.

해결책:

• 패턴의 문자 빈도를 세기 위해 해시 테이블을 사용해.
• 문자열 배열을 순회하며, 각 부분 문자열이 문자 빈도에 맞는지를 확인하기 위해 "슬라이딩 윈도우"를 사용해.

구현 예시:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# 사용 예시:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # 출력: True

9.4 학습 내용을 위한 실습 문제

문제 1: 정렬되지 않은 배열에서 요소 찾기

숫자 배열과 목표값이 주어졌을 때, 배열에서 목표값의 인덱스를 찾아야 해. 선형 탐색을 사용해.

예시:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 사용 예시:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # 출력: 2

문제 2: 배열에서 중복 찾기

숫자 배열이 주어졌을 때, 해시 테이블을 사용하여 배열에서 중복을 모두 찾아 반환해야 해.

예시:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 사용 예시:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # 출력: [3, 1]