[자료구조] Week 11: 탐색 알고리즘 - 선형 탐색과 이진 탐색

Day 1: 탐색 알고리즘의 개념과 필요성

• 강의 내용:
  • 탐색 알고리즘의 정의와 중요성
    • 탐색 알고리즘이란 무엇인가
    • 데이터 탐색의 필요성
    • 탐색 알고리즘의 실제 응용 사례 (데이터베이스 검색, 네트워크 라우팅 등)
  • 탐색 알고리즘의 분류
    • 선형 탐색 (Linear Search)
    • 이진 탐색 (Binary Search)
• 실습:
  • 파이썬 내장 탐색 함수 사용해보기

# 파이썬 내장 탐색 함수 예제
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print("데이터에서 5의 인덱스:", data.index(5))
print("데이터에서 2의 존재 여부:", 2 in data)

 

Day 2: 선형 탐색 (Linear Search)

• 강의 내용:
  • 선형 탐색의 개념
    • 선형 탐색의 정의 및 작동 원리
    • 시간 복잡도 분석 (O(n))
  • 선형 탐색의 장단점
• 실습:
  • 선형 탐색 알고리즘 구현 및 예제

# 선형 탐색 알고리즘 구현
def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# 선형 탐색 예제
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
index = linear_search(data, 5)
print("선형 탐색 결과: 인덱스", index)  # 4 (첫 번째 5의 인덱스)

 

Day 3: 이진 탐색 (Binary Search)

• 강의 내용:
  • 이진 탐색의 개념
    • 이진 탐색의 정의 및 작동 원리
    • 시간 복잡도 분석 (O(log n))
  • 이진 탐색의 전제 조건
    • 데이터가 정렬되어 있어야 함
• 실습:
  • 이진 탐색 알고리즘 구현 및 예제

# 이진 탐색 알고리즘 구현
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

# 이진 탐색 예제
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
index = binary_search(data, 7)
print("이진 탐색 결과: 인덱스", index)  # 6 (7의 인덱스)

 

Day 4: 재귀적 이진 탐색

• 강의 내용:
  • 재귀적 이진 탐색의 개념
    • 재귀적 이진 탐색의 정의 및 작동 원리
    • 재귀적 이진 탐색의 시간 복잡도 분석 (O(log n))
  • 재귀적 이진 탐색의 구현
• 실습:
  • 재귀적 이진 탐색 알고리즘 구현 및 예제

# 재귀적 이진 탐색 알고리즘 구현
def binary_search_recursive(arr, x, low, high):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search_recursive(arr, x, low, mid - 1)
        else:
            return binary_search_recursive(arr, x, mid + 1, high)
    else:
        return -1

# 재귀적 이진 탐색 예제
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
index = binary_search_recursive(data, 7, 0, len(data) - 1)
print("재귀적 이진 탐색 결과: 인덱스", index)  # 6 (7의 인덱스)

 

Day 5: 이진 탐색 트리 (Binary Search Tree)

• 강의 내용:
  • 이진 탐색 트리의 개념
    • 이진 탐색 트리의 정의 및 특징
    • 이진 탐색 트리의 시간 복잡도 분석 (평균 O(log n), 최악 O(n))
  • 이진 탐색 트리의 주요 연산
    • 삽입, 삭제, 탐색
• 실습:
  • 이진 탐색 트리 구현 및 예제

# 이진 탐색 트리 노드 클래스 정의
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# 이진 탐색 트리 삽입 함수 정의
def insert(root, key):
    if root is None:
        return TreeNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

# 이진 탐색 트리 탐색 함수 정의
def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# 이진 탐색 트리 사용 예제
root = TreeNode(10)
root = insert(root, 5)
root = insert(root, 20)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 15)
root = insert(root, 25)

# 탐색 예제
result = search(root, 15)
print("이진 탐색 트리에서 15의 탐색 결과:", result.val if result else "찾을 수 없음")

 

Day 6: 탐색 알고리즘의 비교와 응용

• 강의 내용:
  • 탐색 알고리즘의 비교
    • 선형 탐색과 이진 탐색의 비교
    • 각 알고리즘의 장단점
  • 탐색 알고리즘의 실제 응용 사례
    • 데이터베이스 인덱싱
    • 검색 엔진
• 실습:
  • 탐색 알고리즘을 사용한 응용 예제

# 데이터베이스 인덱싱 예제
class SimpleDatabase:
    def __init__(self):
        self.data = []

    def insert(self, record):
        self.data.append(record)
        self.data.sort()

    def search(self, query):
        return binary_search(self.data, query)

# 데이터베이스 인덱싱 사용 예제
db = SimpleDatabase()
db.insert(15)
db.insert(10)
db.insert(20)
db.insert(5)
db.insert(25)

result = db.search(15)
print("데이터베이스에서 15의 탐색 결과: 인덱스", result)  # 3 (정렬된 데이터에서 15의 인덱스)

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 탐색 알고리즘을 사용한 종합 연습 문제 풀이
    • 다양한 탐색 알고리즘 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 탐색 알고리즘을 활용한 간단한 프로그램 구현
    • 예: 파일 시스템 탐색기
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 정렬된 배열에서 중복 요소 찾기
def find_duplicates(arr):
    duplicates = []
    for i in range(len(arr) - 1):
        if arr[i] == arr[i + 1] and (i == 0 or arr[i] != arr[i - 1]):
            duplicates.append(arr[i])
    return duplicates

# 중복 요소 찾기 예제
data = [1, 2, 2, 3, 4, 4, 5, 5, 5]
duplicates = find_duplicates(data)
print("중복 요소 찾기 결과:", duplicates)  # [2, 4, 5]

# 미니 프로젝트 예제: 파일 시스템 탐색기
import os

def search_files(directory, filename):
    for root, dirs, files in os.walk(directory):
        if filename in files:
            return os.path.join(root, filename)
    return "파일을 찾을 수 없음"

# 파일 시스템 탐색기 사용 예제
directory = "/path/to/search"
filename = "example.txt"
result = search_files(directory, filename)
print(f"'{filename}'의 탐색 결과:", result)

 

이 강의는 파이썬의 탐색 알고리즘, 특히 선형 탐색과 이진 탐색의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!