탐색 (목차)

탐색 알고리즘

📌 1. 탐색(Search) 알고리즘 개요

• 탐색 알고리즘이란?
• 탐색 알고리즘의 종류 및 분류 (선형 탐색, 이진 탐색, 해싱, 그래프 탐색 등)
• 시간 복잡도와 효율성 개념 소개
• 탐색과 정렬의 관계

🔍 실습: C에서 배열을 생성하고 기본적인 값을 출력하는 코드 작성

---

📌 2. 선형 탐색(Linear Search)

• 선형 탐색의 개념 및 동작 방식
• 최선/최악/평균 시간 복잡도 분석 (O(n))
• 선형 탐색의 한계점

🔍 실습

• 배열에서 특정 값을 찾는 선형 탐색 구현 (for 루프 사용)
• 배열 크기 증가 시 실행 속도 비교 (clock() 사용)

---

📌 3. 이진 탐색(Binary Search)

• 이진 탐색 개념 및 필요 조건 (정렬된 배열)
• 이진 탐색의 동작 원리 (중간값 기준 비교)
• 재귀(Recursive) vs 반복(Iterative) 방식의 구현 비교
• 시간 복잡도 분석 (O(log n))

🔍 실습

• 정렬된 배열에서 특정 값을 찾는 이진 탐색 구현
• qsort()를 사용하여 배열 정렬 후 이진 탐색 적용
• 재귀 함수와 반복문 방식 구현 비교

---

📌 4. 점프 탐색(Jump Search) & 보간 탐색(Interpolation Search)

• 점프 탐색(Jump Search) 개념 및 구현 (O(√n))
• 보간 탐색(Interpolation Search) 개념 및 구현 (데이터가 균등 분포일 때 효율적)

🔍 실습

• 점프 탐색과 보간 탐색을 구현하고 실행 속도 비교

---

📌 5. 해싱(Hashing) 기법

• 해싱(Hashing)의 개념과 필요성
• 해시 함수(Hash Function) 및 충돌 해결 방법 (체이닝, 개방 주소법)
• 해시 테이블(Hash Table) 구현

🔍 실습

• C에서 struct와 배열을 이용한 간단한 해시 테이블 구현
• 충돌 해결을 위한 체이닝(연결 리스트) 기법 적용

---

📌 6. 그래프 탐색 개요 (Graph Search)

• 그래프(Graph)란? (정점과 간선의 개념)
• 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 소개
• 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)의 차이점

🔍 실습

• 인접 행렬과 인접 리스트를 사용하여 그래프 구현

---

📌 7. 깊이 우선 탐색(DFS, Depth First Search)

• DFS 개념 및 원리
• 재귀(Recursive) 방식과 스택(Stack) 기반 반복(Iterative) 방식 비교
• 그래프에서 DFS를 활용하는 예시 (미로 찾기, 위상 정렬)

🔍 실습

• 재귀 함수 기반 DFS 구현
• 스택을 이용한 반복 DFS 구현
• 미로 탐색 알고리즘 적용

---

📌 8. 너비 우선 탐색(BFS, Breadth First Search)

• BFS 개념 및 원리
• 큐(Queue) 자료구조를 이용한 BFS 구현 방식
• BFS의 활용 예시 (최단 경로 문제, 네트워크 연결 확인)

🔍 실습

• 큐를 이용한 BFS 구현
• 최단 경로 문제 해결 (예: 미로 탈출)

---

📌 9. 최단 경로 탐색 알고리즘

• 다익스트라(Dijkstra) 알고리즘 개념 및 구현 (우선순위 큐 활용)
• 벨만-포드(Bellman-Ford) 알고리즘 개념 및 차이점

🔍 실습

• 다익스트라 알고리즘을 C에서 구현하여 그래프의 최단 경로 탐색

---

📌 10. 고급 탐색 기법 및 응용

• 이진 검색 트리(BST, Binary Search Tree) 소개 및 탐색
• A* 탐색 알고리즘 개요 및 응용 (게임 개발, 경로 탐색)

🔍 실습

• 이진 검색 트리 구현 및 탐색 연산 (insert, search, delete)
• 간단한 길 찾기 문제에서 A* 알고리즘 구현

---

📌 11. 탐색 알고리즘 성능 비교 프로젝트

• 다양한 탐색 알고리즘을 동일한 데이터셋에서 실행하여 성능 비교
• 입력 크기 증가에 따른 실행 시간 변화 분석
• 실생활에서 탐색 알고리즘이 활용되는 사례 연구 (데이터베이스 검색, 웹 크롤링 등)

🔍 실습

• 정렬된/정렬되지 않은 데이터에서 선형 탐색 vs 이진 탐색 비교
• 해시 테이블 vs 선형 탐색 성능 비교

---

📌 12. 최종 프로젝트: 실전 문제 해결

💡 프로젝트 예제

1. 도서 관리 시스템 → 해시 테이블을 이용한 빠른 도서 검색 기능 구현
2. 길 찾기 프로그램 → 그래프 탐색 알고리즘을 활용한 경로 탐색 기능 개발
3. 간단한 AI 게임봇 → A* 알고리즘을 이용한 최적 경로 탐색 구현

---

🔔 마무리 및 학습 방향

• 탐색 알고리즘 성능 최적화 방법
• 다양한 문제에 대한 알고리즘 선택 방법
• 자료구조와 알고리즘 심화 학습을 위한 추천 도서 및 자료