[알고리즘] 추가 자료 및 연습 문제

추가 자료

1. 선형 계획법 (Linear Programming)

• 도서:
  • "Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis
  • "Linear Programming and Network Flows" by Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali
• 온라인 강의:
  • MIT OpenCourseWare - Linear Programming
  • Coursera - Linear Optimization

2. 제약 만족 문제 (Constraint Satisfaction Problem, CSP)

• 도서:
  • "Constraint Processing" by Rina Dechter
  • "Artificial Intelligence: A Modern Approach" by Stuart Russell and Peter Norvig
• 온라인 강의:
  • Udacity - Artificial Intelligence for Robotics
  • Coursera - AI Planning

3. 고급 그래프 이론

• 도서:
  • "Graph Theory" by Reinhard Diestel
  • "Algorithm Design" by Jon Kleinberg and Éva Tardos
• 온라인 강의:
  • Coursera - Graph Algorithms
  • MIT OpenCourseWare - Advanced Data Structures

4. 고급 문자열 알고리즘

• 도서:
  • "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" by Dan Gusfield
  • "String Matching and Beyond" by Maxime Crochemore, Thierry Lecroq, and Wojciech Rytter
• 온라인 강의:
  • Coursera - Bioinformatics Algorithms
  • Udacity - Intro to Algorithms

5. 고급 기하 알고리즘

• 도서:
  • "Computational Geometry: Algorithms and Applications" by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars
  • "Geometric Algorithms and Combinatorial Optimization" by Martin Grötschel, László Lovász, and Alexander Schrijver
• 온라인 강의:
  • Coursera - Computational Geometry
  • MIT OpenCourseWare - Computational Geometry

---

연습 문제

1. 선형 계획법 연습 문제

1. 공장 생산 문제:
   • 각 공장에서 생산할 제품의 수를 결정하여 이익을 최대화하는 문제를 선형 계획법을 사용하여 해결하세요.
   • 제한 조건: 각 공장은 자원과 시간의 제한을 받습니다.
2. 다이어트 문제:
   • 주어진 식품 목록에서 최소 비용으로 필요한 영양소를 충족하는 식품 조합을 찾으세요.
   • 제한 조건: 각 식품은 특정 양의 영양소를 제공합니다.

2. 제약 만족 문제 연습 문제

1. N-Queens 문제:
   • N-Queens 문제를 해결하세요. N개의 퀸이 서로 공격하지 않도록 N x N 체스판에 배치하세요.
2. 스도쿠 퍼즐:
   • 주어진 스도쿠 퍼즐을 해결하세요.
3. 시간표 스케줄링:
   • 학교 시간표 스케줄링 문제를 해결하세요. 모든 수업이 충돌 없이 배정되도록 하세요.

3. 고급 그래프 이론 연습 문제

1. 최소 신장 트리 (Minimum Spanning Tree):
   • 주어진 그래프에서 최소 신장 트리를 찾으세요. (Kruskal 또는 Prim 알고리즘 사용)
2. 최단 경로 문제:
   • 주어진 가중치 그래프에서 최단 경로를 찾으세요. (Dijkstra 또는 Bellman-Ford 알고리즘 사용)
3. 최대 유량 문제:
   • 주어진 유량 네트워크에서 최대 유량을 찾으세요. (Ford-Fulkerson 알고리즘 사용)

4. 고급 문자열 알고리즘 연습 문제

1. 패턴 매칭 문제:
   • 주어진 텍스트에서 주어진 패턴을 찾으세요. (KMP, Boyer-Moore 또는 Rabin-Karp 알고리즘 사용)
2. DNA 서열 정렬:
   • 두 개의 DNA 서열을 정렬하고 최적 정렬 점수를 계산하세요. (Smith-Waterman 또는 Needleman-Wunsch 알고리즘 사용)
3. 서브스트링 검색:
   • 주어진 텍스트에서 모든 서브스트링을 검색하세요.

5. 고급 기하 알고리즘 연습 문제

1. 볼록 껍질 문제:
   • 주어진 점들의 집합에서 볼록 껍질을 찾으세요. (Graham's Scan 또는 Jarvis's March 알고리즘 사용)
2. 최근접 쌍 문제:
   • 주어진 점들의 집합에서 가장 가까운 두 점을 찾으세요. (분할 정복 알고리즘 사용)
3. 선분 교차 판정:
   • 주어진 선분들이 교차하는지 판정하세요.

---

이 자료와 연습 문제를 통해 여러분이 학습한 내용을 복습하고 더 깊이 있는 이해를 할 수 있기를 바랍니다. 추가 자료나 연습 문제가 필요하면 언제든지 말씀해 주세요!