선형 검색

1.1 선형 검색의 정의

선형 검색 (때때로 순차 검색이라고도 불림) — 리스트나 배열에서 요소를 찾는 알고리즘으로, 일치하는 요소를 찾거나 모든 요소를 확인할 때까지 순차적으로 각 요소를 검사해. 이건 가장 단순한 검색 알고리즘으로, 데이터를 사전에 정렬할 필요가 없어.

주요 원칙:

• 순차적 검사: 알고리즘은 배열이나 리스트의 각 요소를 순차적으로 돌아다니면서 찾고자 하는 값과 비교해.
• 검색 종료: 찾고자 하는 값을 가진 요소를 찾으면 검색이 종료되고, 모든 요소를 확인하면 검색이 종료돼.
• 정렬 불필요: 선형 검색은 데이터가 정렬되지 않아도 사용할 수 있어.
• 적용 가능성: 선형 검색은 리스트나 배열을 포함한 반복 기능을 지원하는 모든 데이터 구조에 사용할 수 있어.

선형 검색의 시간 복잡도는 O(n)이야, 여기서 n은 배열이나 리스트의 요소 수야. 최악의 경우, 알고리즘은 찾고자 하는 값을 찾거나 그 부재를 확인하기 위해 모든 n 요소를 검사해야 해.

시간 복잡도 분석:

• 최선의 경우 (Best case): 요소가 첫 번째 위치에서 발견될 경우, O(1).
• 평균적인 경우 (Average case): 요소가 중간 어딘가에서 발견될 경우, O(n/2), 이는 O(n)과 동등해.
• 최악의 경우 (Worst case): 요소가 마지막 위치에서 발견되거나 없을 경우, O(n).

1.2 선형 검색의 단계별 구현

선형 검색 단계:

• 초기화: 검색을 위한 초기 인덱스를 설정해 (보통은 0 인덱스).
• 순차적 검사: 리스트나 배열의 각 요소가 찾고자 하는 값과 일치하는지 검사해.
• 완료 조건: 요소가 발견되면, 그 인덱스를 반환해. 모든 요소를 검사했는데 찾고자 하는 값이 없으면, 특별한 값을 반환해 (보통 -1 또는 None).

Python에서의 선형 검색 구현:

def linear_search(arr, target):
    # 배열의 각 요소를 순회해
    for index, element in enumerate(arr):
        # 현재 요소가 찾는 값과 같으면, 그 인덱스를 반환해
        if element == target:
            return index
    # 요소를 찾지 못하면, -1을 반환해
    return -1

구현 설명 단계:

• 반복문 초기화: enumerate 함수와 함께 for 반복문을 사용해서, 각 반복에서 배열의 인덱스와 요소를 반환해.
• 비교: 각 반복에서 현재 요소가 찾고자 하는 값 (target)과 비교돼.
• 인덱스 반환: 현재 요소가 찾는 값과 같으면, 그 요소의 인덱스를 반환해.
• -1 반환: 반복이 끝났는데 찾는 요소를 발견하지 못하면, -1이 반환돼.

# 사용 예시:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"요소 {target}는 인덱스 {result}에서 발견됨")  # 출력: 요소 7는 인덱스 2에서 발견됨

# 배열에 없는 요소에 대한 사용 예시:
target = 5
result = linear_search(arr, target)
print(f"요소 {target}는 인덱스 {result}에서 발견됨")  # 출력: 요소 5는 인덱스 -1에서 발견됨

1.3 선형 검색으로 해결할 수 있는 문제 예시

선형 검색은 데이터 컬렉션에서 요소를 찾는 것과 관련된 여러 문제를 해결하는 데 사용돼. 여기 몇 가지 그런 문제의 예시가 있어:

문제 1: 배열에서 요소 찾기

숫자의 배열에서 주어진 숫자를 찾아야 해.

예시:

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"요소 {target}는 인덱스 {index}에서 발견됨")  # 출력: 요소 70는 인덱스 3에서 발견됨

문제 2: 리스트에 요소 존재 여부 확인

문자열 리스트에 주어진 값이 존재하는지 확인해야 해.

예시:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"요소 {target}는 {'발견됨' if found else '발견되지 않음'}")  # 출력: 요소 cherry는 발견됨

문제 3: 최소값 또는 최대값 찾기

리스트에서 최소값이나 최대값을 찾아야 해.

예시:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"최소값: {min_value}")  # 출력: 최소값: 2

문제 4: 첫 번째 발생 찾기

리스트에서 주어진 요소의 첫 번째 발생을 찾아야 해.

예시:

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"첫 번째 발생 {target}는 인덱스 {index}에서 발견됨")  # 출력: 첫 번째 발생 2는 인덱스 1에서 발견됨

문제 5: 발생 횟수 세기

리스트에서 주어진 요소의 발생 횟수를 세어야 해.

예시:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"요소 {target}는 {count}번 발생함")  # 출력: 요소 2는 3번 발생함