선형 탐색 (Linear Search) 이란?

선형 탐색이란?

선형 탐색(Linear Search)은 데이터를 하나씩 순서대로 확인하여 원하는 값을 찾는 가장 기본적인 탐색 알고리즘입니다. 

일반적으로 무언가 데이터에서 원하는 값을 찾아낸다면, 

효율적으로 찾아낼 필요가 없는 경우 자연스럽게 이 방법을 사용하고 있게 됩니다.

선형 탐색의 작동 방식

1. 처음부터 시작: 리스트나 배열의 첫 번째 요소부터 시작합니다.
2. 순차적으로 확인: 각 요소를 순서대로 확인합니다.
3. 조건 비교: 찾고자 하는 값과 현재 요소를 비교합니다.
4. 값 발견: 값이 일치하면 해당 요소의 인덱스를 반환합니다.
5. 끝까지 탐색: 리스트나 배열의 끝까지 값을 찾지 못하면 값을 찾을 수 없음을 반환합니다.

선형 탐색의 예

다음은 파이썬에서 선형 탐색을 구현한 예제입니다. 여기서는 리스트에서 특정 값을 찾는 과정을 보여줍니다.

def linear_search(arr, target):
   for i in range(len(arr)):
       if arr[i] == target:
           return i  # 값을 찾으면 인덱스를 반환
   return -1  # 값을 찾지 못하면 -1을 반환

# 예제 리스트
numbers = [3, 5, 2, 4, 9, 1, 10]

# 값을 찾기 위한 탐색
target = 4
index = linear_search(numbers, target)

if index != -1:
   print(f"값 {target}은 인덱스 {index}에 있습니다.")
else:
   print(f"값 {target}을 찾을 수 없습니다.")

선형 탐색의 장점과 단점

장점:

• 단순함: 구현이 매우 간단하고 이해하기 쉽습니다.
• 정렬 필요 없음: 데이터가 정렬되어 있지 않아도 사용할 수 있습니다.
• 작은 데이터셋: 데이터셋이 작을 때 효율적입니다.

단점:

• 비효율적: 데이터셋이 커질수록 시간이 많이 걸립니다. 최악의 경우 O(n)의 시간 복잡도를 가집니다.
• 특정 구조에서 비효율적: 데이터가 정렬되어 있거나 특정 규칙이 있는 경우 다른 탐색 알고리즘이 더 효율적일 수 있습니다.

예시: 단어 찾기 게임

문자열 리스트에서 특정 단어를 찾는 예제를 통해 선형 탐색을 이해해보겠습니다.

def linear_search(words, target):
   for i in range(len(words)):
       if words[i] == target:
           return i  # 값을 찾으면 인덱스를 반환
   return -1  # 값을 찾지 못하면 -1을 반환

# 예제 단어 리스트
words = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"]

# 값을 찾기 위한 탐색
target = "cherry"
index = linear_search(words, target)

if index != -1:
   print(f"단어 '{target}'은 인덱스 {index}에 있습니다.")
else:
   print(f"단어 '{target}'을 찾을 수 없습니다.")

요약해볼까요?

• 선형 탐색: 데이터를 하나씩 순서대로 확인하여 원하는 값을 찾는 방법.
• 작동 방식: 처음부터 시작하여 각 요소를 순서대로 확인하며, 값을 찾으면 인덱스를 반환하고, 찾지 못하면 끝까지 탐색.
• 장점: 단순하고 정렬이 필요없음.
• 단점: 데이터셋이 커질수록 비효율적.