탐색 알고리즘 기초 선형 탐색과 이진 탐색 쉽게 이해하기

탐색 알고리즘이란?

탐색 알고리즘은 원하는 데이터를 효율적으로 찾는 과정을 다룹니다.

우리는 일상에서도 탐색을 자주 경험합니다.

예를 들어, 전화번호부에서 이름을 찾거나, 책의 목차를 통해 원하는 페이지를 찾는 과정도 탐색의 일종입니다.

이 포스팅에서는 선형 탐색과 이진 탐색을 이해하고 그 차이를 배워보겠습니다.

 

 

탐색알고리즘의 기초와 활용

1. 선형 탐색 (Linear Search)

• 정의 : 데이터를 처음부터 끝가지 순차적으로 탐색합니다.
• 장점 : 정렬되지 않은 데이터에서도 사용할 수 있습니다.
• 단점 : 데이터가 많아질수록 탐색 시간이 증가(O(n)).
• 코드 예제

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

arr = [3, 5, 2, 4, 9]
print("인덱스:", linear_search(arr, 4))  # 출력: 3

2. 이진 탐색 (Binary Search)

• 정의 : 데이터를 절반씩 나누며 탐색하는 알고리즘으로, 정렬된 데이터에서만 사용 가능합니다.
• 장점 : 탐색 시간이 빠름(O(log n)).
• 단점 : 데이터가 정렬되어 있어야 함.
• 코드 예제

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

arr = [1, 3, 5, 7, 9]
print("인덱스:", binary_search(arr, 7))  # 출력: 3

3. 선형 탐색과 이진 탐색 비교

• 선형 탐색
  • 데이터가 정렬되지 않아도 사용 가능
  • 탐색 속도가 느림
• 이진 탐색
  • 정렬된 데이터에서만 사용 가능
  • 탐색 속도가 빠름

 

 

탐색 알고리즘 학습의 중요성

탐색 알고리즘은 데이터를 효율적으로 처리하기 위한 중요한 도구입니다.

선형 탐색은 간단하지만 비효율적이며, 이진 탐색은 정렬된 데이터에서 강력한 성능을 발휘합니다.

이번 포스팅에서 배운 알고리즘을 이해하고 나면,

앞으로 배울 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 같은 고급 알고리즘으로 나아가는 데 큰 도움이 될 것입니다.