파이썬 데이터 구조와 알고리즘 분석 (2판)
이 책은 파이썬을 사용하여 데이터 구조와 알고리즘을 설명하는 전통적인 교재입니다. 파이썬 기초 복습, 알고리즘 분석(빅오 표기법), 기본 데이터 구조(스택, 큐, 리스트), 재귀, 탐색 및 정렬, 트리 및 그래프 알고리즘 등을 다룹니다. 실전 코드 예제를 통해 파이썬을 활용해 다양한 추상 데이터 유형을 효율적으로 구현하는 방법을 이해하는 데 도움을 줍니다.
강좌 개요
📚 콘텐츠 개요
이 책은 파이썬을 활용하여 데이터 구조와 알고리즘을 설명하는 전통적인 교과서입니다. 파이썬 기초 복습, 알고리즘 분석(빅오 표기법), 기본 데이터 구조(스택, 큐, 리스트), 재귀, 탐색 및 정렬, 트리 및 그래프 알고리즘을 다룹니다. 실전 코드 목록을 통해 독자가 파이썬으로 다양한 추상적 데이터 유형을 효율적으로 구현하는 방법을 이해할 수 있도록 돕습니다.
데이터 구조와 알고리즘을 완전히 이해해야 비로소 파이썬을 진정으로 숙달할 수 있다.
저자: 브래들리 밀러 (미국 루터 대학 컴퓨터 과학 명예 교수), 데이비드 라누움 (IBM 워슨 인지 소프트웨어 엔지니어)
감사의 말: 제1판에 대한 많은 피드백을 제공해 준 동료 스티브 허버드와 신규 자료를 제공해 준 새 판의 편집에 감사를 드립니다. 또한 전 세계의 동료들이 오류를 지적하고 의견을 제시해 주신 점에 깊이 감사드립니다. 디코라 시티의 자바 존스 카페의 메리, 보브 등 직원들에게도 감사합니다. 저희가 휴가 중에도 매장의 '정기 작가'가 되도록 허락해주셔서 고맙습니다. 또한 프랭클린, 비들 & 어소시에이츠 출판사의 직원들(특히 잠 리지와 톰 서머너)과의 즐거운 협업에 감사드립니다. 마지막으로, 저희 두 사람의 아내인 제인 밀러와 브렌다 라누움에게 특별한 감사를 드립니다. 그들의 사랑과 지지는 이 책이 현실이 되도록 해주었습니다.
🎯 학습 목표
- 컴퓨터 과학, 알고리즘, 프로그래밍 간의 관계를 이해하고, 추상적 데이터 유형(ADT)과 정보 은닉의 개념을 습득한다.
- 파이썬 내장 컬렉션 데이터 유형(리스트, 튜플, 세트, 사전)과 제어 구조(반복문, 조건문, 예외 처리)를 능숙하게 사용할 수 있다.
- 파이썬 객체 지향 프로그래밍의 핵심 요소를 익히며, 클래스 정의, 생성자, 연산자 오버로딩(예: 분수 덧셈), 유클리드 알고리즘 적용, 그리고 깊은 복사와 얕은 복사의 차이를 이해한다.
- 알고리즘의 다양한 접근 방식 비교: 동음이의어 검출의 네 가지 방법(세기, 정렬, 폭력적 탐색, 계수)과 각각의 시간 복잡도를 설명할 수 있다.
- 파이썬 컨테이너 성능 측정: 파이썬 리스트(List)와 사전(Dict)의 주요 연산에 대한 빅오 효율을 이해하고,
pop()과pop(i)의 성능 차이를 구분할 수 있다. - 성능 검증 능력:
timeit모듈을 활용하여 이론적 복잡도와 실제 실행 시간의 일치성을 실험적으로 검증할 수 있다. - 선형 데이터 구조(스택, 큐, 덱, 리스트)의 논리적 특성을 이해하고 구분할 수 있다.
- 파이썬 기본 컬렉션(예: 리스트)을 사용하여 사용자 정의 스택, 큐, 덱을 구현할 수 있다.
- 스택이 표현식 처리(중위 표기에서 후위 표기로 변환, 후위 표기 계산)와 큐가 시스템 시뮬레이션(프린터 시뮬레이션)에서 어떻게 활용되는지를 이해한다.
- 재귀의 핵심 세 원칙을 숙지하고, 기본 사례, 상태 변화, 자기 호출을 포함하는 재귀 함수를 정확히 식별하고 작성할 수 있다.
수업 共 8 课时 · 预计 24.0h
수업
Lesson
This lesson introduces the core principles of computer science, focusing on problem-solving through algorithms, procedural abstraction, and Python’s object-oriented nature. Students will learn to manage complexity by leveraging Python’s dynamic variable references, efficient built-in data structures, and robust error-handling techniques to build reliable, scalable software.
本课程深入探讨了算法分析的核心工具——大O记法，通过异序词检测案例展示了从暴力法到计数法的性能优化过程。学习重点在于理解不同操作（如列表索引与pop操作）的复杂度差异，并掌握如何通过空间换时间及选择合适的数据结构来提升程序效率。
This lesson introduces linear data structures and the concept of Abstract Data Types (ADTs), focusing on the stack as a fundamental LIFO (Last-In, First-Out) structure. Students will learn to implement stacks in Python and apply them to complex tasks, including converting infix expressions to postfix notation and evaluating those expressions efficiently.
本课程深入探讨了递归算法的核心原理，重点讲解了递归三原则（基准情况、状态改变、自我调用）以及递归与系统调用栈之间的内在联系。通过进制转换、汉诺塔及动态规划等案例，学生将学习如何将复杂问题拆解为自相似的子问题，并掌握从递归思维向高效动态规划算法的进阶转换。
This lesson explores fundamental search and retrieval algorithms, progressing from $O(n)$ sequential search to the $O(\log n)$ efficiency of binary search and the $O(1)$ potential of hash tables. Students learn to optimize data access through divide-and-conquer strategies, sophisticated hash function design, and collision-handling techniques to build efficient, dictionary-like data structures.
This lesson explores the hierarchical and recursive nature of tree data structures, covering fundamental terminology, implementation methods like nested lists and object-oriented references, and the construction of expression trees. It also introduces essential tree traversal algorithms—preorder, inorder, and postorder—and explains how these recursive patterns are applied to tasks like file system analysis and AVL tree balancing.
This lesson introduces graph theory as a powerful tool for modeling real-world problems by abstracting entities as vertices and relationships as edges. Students will learn to implement graphs using adjacency lists, compare storage efficiency, and master the Breadth-First Search (BFS) algorithm to solve pathfinding and state-space challenges.
This lesson explores the memory efficiency of Python's ArrayList, explaining how amortized analysis ensures $O(1)$ performance for append operations through strategic over-allocation. It also covers the mathematical foundations of RSA encryption, demonstrating how modular exponentiation and divide-and-conquer algorithms optimize complex calculations for secure data processing.