python 에 익숙해질겸, 자료구조에 대해 복습 할겸, python 으로 자료 구조를 직접 구현 해보자.
학생때 배웠던 "C언어로 쉽게 풀어쓴 자료구조" 책의 목차 순서대로 작성 한다. (개정판이 나와서 그 당시와는 내용이 다를 수 있지만 큰 틀은 변하지 않았다.)
순환(Recursion)
- 거듭제곱 값 계산
- 피보나치 수열의 계산
- 하노이탑 문제
배열(Array)
- 배열의 응용: 다항식
- 배열의 응용: 희소 행렬
리스트(List)
- 리스트 추상 데이터 타입
- 배열로 구현된 리스트
- 연결 리스트
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
- 연결 리스트의 응용: 다항식
- 연결 리스트로 구현된 리스트
- 선형 리스트의 응용: 텍스트 에디터
스택(Stack)
- 스택 추상 데이터 타입
- 배열로 구현한 스택
- 연결 리스트로 구현한 스택
- 괄호 검사
- 수식의 계산
- 미로 탐색 문제
큐(Queue)
- 큐 추상 데이터 타입
- 배열로 구현된 큐
- 연결 리스트로 구현된 큐
- 덱(Deque)
- 큐의 응용
트리(Tree)
- 이진 트리
- 스레드 이진 트리
- 이진 탐색 트리
- 이진 탐색 트리의 응용: 영어 사전
우선순위 큐(Priority Queue)
- 우선순위 큐 추상 데이터 타입
- 우선순위 큐의 구현 방법
- 히프
- 히프의 복잡도 분석
- 히프의 응용
정렬(Sort)
- 선택 정렬
- 삽입 정렬
- 버블 정렬
- 셸 정렬
- 합병 정렬
- 퀵 정렬
- 히프 정렬
- 기수 정렬
그래프(Graph)
- 그래프 추상 데이터 타입
- 그래프의 탐색
- 깊이 우선 탐색
- 너비 우선 탐색
- 연결 성분
- 신장 트리
- 최소 비용 신장 트리
- Kruskal의 MST 알고리즘
- Prim의 MST 알고리즘
- 최단 경로
- Dijkstra의 최단 경로 알고리즘
- Floyd의 최단 경로 알고리즘
- 위상 정렬
해싱(Hashing)
- 추상 자료형 사전 구조
- 해싱의 구조
- 해시 함수
- 충돌 해결책
- 선형 조사법
- 체이닝
- 해싱의 성능 분석
탐색(Search)
- 정렬되지 않은 배열에서의 탐색
- 정렬된 배열에서의 탐색
- 정렬된 배열에서의 순차 탐색
- 이진 탐색
- 색인 순차 탐색
- 보간 탐색
- 균형 이진 탐색 트리
- AVL 트리
- 2-3 트리
- 2-3-4 트리