[알고리즘] Week 4: 탐색 알고리즘 I - 탐색 개념 및 기본 알고리즘

Day 1: 탐색의 개념

• 강의 내용:
  • 탐색의 정의와 중요성
    • 탐색이란 무엇인가?
    • 탐색의 필요성
    • 탐색 알고리즘의 실제 응용 사례
  • 탐색 알고리즘의 분류
    • 선형 탐색
    • 이진 탐색
• 실습:
  • 파이썬 내장 탐색 함수 사용해보기

# 파이썬 내장 탐색 함수 예제
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: 탐색 알고리즘의 비교와 응용

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

# 데이터베이스 인덱싱 예제
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)  # 2 (정렬된 데이터에서 15의 인덱스)

 

Day 6: 종합 연습

• 강의 내용:
  • 탐색 알고리즘 종합 연습
    • 다양한 탐색 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • Q&A 세션 및 피드백
• 실습:
  • 다양한 데이터셋을 사용한 탐색 알고리즘 연습
  • 알고리즘 성능 분석 및 최적화

# 종합 연습: 다양한 데이터셋 탐색
def generate_random_data(size):
    import random
    return [random.randint(0, 1000) for _ in range(size)]

# 데이터셋 생성
small_data = generate_random_data(10)
medium_data = generate_random_data(100)
large_data = generate_random_data(1000)

# 정렬된 데이터 생성
small_data.sort()
medium_data.sort()
large_data.sort()

# 탐색 알고리즘 성능 비교
def measure_time(search_func, arr, x):
    import time
    start_time = time.time()
    result = search_func(arr, x)
    end_time = time.time()
    return end_time - start_time, result

x = 500

print("작은 데이터셋 선형 탐색 시간:", measure_time(linear_search, small_data, x))
print("작은 데이터셋 이진 탐색 시간:", measure_time(binary_search, small_data, x))

print("중간 데이터셋 선형 탐색 시간:", measure_time(linear_search, medium_data, x))
print("중간 데이터셋 이진 탐색 시간:", measure_time(binary_search, medium_data, x))

print("큰 데이터셋 선형 탐색 시간:", measure_time(linear_search, large_data, x))
print("큰 데이터셋 이진 탐색 시간:", measure_time(binary_search, large_data, x))

 

Day 7: 프로젝트 준비 및 시작

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 탐색 알고리즘 프로젝트 주제 선정
    • 프로젝트 요구사항 정의
  • 프로젝트 계획 수립
    • 프로젝트 구현 계획 수립
    • 주요 기능 및 모듈 정의
• 실습:
  • 프로젝트 주제 및 계획 수립
  • 프로젝트 구현 시작

### 프로젝트 주제 예시
1. 도서 검색 시스템
2. 영화 검색 도구
3. 상품 검색 엔진

### 프로젝트 요구사항 예시
1. 도서 검색 시스템:
   - 도서 정보 입력 및 저장
   - 다양한 탐색 알고리즘을 통한 도서 검색
   - 검색된 도서 정보 출력

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 탐색 알고리즘 구현 (선형 탐색, 이진 탐색 등)
3. 데이터 출력 모듈 구현

 

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