1. 교과목 학습목표 |
데이터를 효율적으로 관리하고 사용하기 위한 자료구조의 개념과 분류 및 자료의 저장과 활용 방법에 대하여 학습하고 게임 제작 시 보다 효율적인 게임 데이터 관리 및 활용을 할 수 있는 능력을 배양하여 게임 프로그램의 성능과 안정적인 개발을 할 수 있는 기본기를 향상 시키는데 목표가 있다. |
2. 교재 및 참고문헌 |
IT CookBook, C C++로 배우는 자료구조론 (한빛미디어,주우석) |
3. 주차별 강의(실습·실기·실헙)내용 |
주별 |
강의(실습·실기·실험)내용 |
과제 및 기타 참고사항 |
제 1 주 |
1부. 기초다지기
- 1장. 객체지향 방법론
- 01. 객체지향 개념
- 02. 객체 클래스와 상속
- 03. C++와 객체지향
- 04. 절차적 설계와의 비교
|
|
제 2 주 |
2장. 추상 자료형
- 01. 추상 자료형 개념
- 02. 추상 자료형과 C
- 03. 추상 자료형과 C++
|
|
제 3 주 |
3장. 포인터, 배열, 구조체
- 01. 포인터
- 02. 참조 호출과 값 호출
- 03. 배열
- 04. 구조체
- 05. 활성화 레코드
- 06. 디버깅을 위한 매크로
- 07. 표준 라이브러리 헤더와 프로그래밍
|
|
제 4 주 |
4장. 재귀호출
- 01. 상징적 의미
- 02. 이진탐색
- 03. 재귀적 팩토리얼
- 04. 문자열 뒤집기
- 05. K번째 작은 수 찾기
- 06. 피보나치 수열
- 07. 재귀 함수의 작성
- 08. 재귀호출의 필요성
- 09. 꼬리 재귀
|
|
제 5 주 |
5장. 리스트
- 01. 추상 자료형 리스트
- 02. C에 의한 구현
- 03. C++에 의한 구현
- 04. 배열과 연결 리스트 비교
|
|
제 6 주 |
6장. 스택
- 01. 스택 개념
- 02. 추상 자료형 스택
- 03. C에 의한 스택 구현
- 04. C++에 의한 스택 구현
- 05. 리스트에 의한 스택 구현
- 06. 스택 응용 예
- 07. 깊이 우선 탐색
- 08. 스택과 재귀호출
- 09. 재귀호출 제거
|
스택을 이용하여 미로에 갇힌 생쥐가 출구를 찾는 문제를 자료구조를 구현한다. |
제 7 주 |
중간고사 |
- |
제 8 주 |
7장. 큐
- 01. 큐 개념
- 02. 추상 자료형과 큐
- 03. C++ 연결 리스트에 의한 큐 구현
- 04. C++ 배열에 의한 큐 구현
- 05. 추상 자료형 리스트에 의한 큐 구현
- 06. 큐 응용 예
- 07. 너비우선 탐색
- 08. 덱
|
|
제 9 주 |
8장. 알고리즘과 효율
- 01. 알고리즘
- 02. 알고리즘의 정확성
- 03. 정확성 증명
- 04. 알고리즘의 효율
- 05. 효율 분석 예
- 06. 분할상각 복잡도
- 07. 분할상각 복잡도
|
|
제 10 주 |
9장. 정렬 알고리즘과 효율
- 01. 정렬의 분류
- 02. 선택 정렬
- 03. 버블 정렬
- 04. 삽입 정렬
- 05. 셸 정렬
- 06. 합병 정렬
- 07. 쾌속 정렬
- 08. 외부 정렬
- 09. 최선의 정렬효율
- 10. 버켓 정렬과 셈 정렬
- 11. 기수 정렬
|
정렬의 자료구조를 응용하여 영어사전을 위한 정렬을 구현한다. |
제 11 주 |
10장. 트리
- 01. 트리 개요
- 02. 추상 자료형 트리
- 03. 배열에 의한 이진트리 구현
- 04. 포인터에 의한 이진트리 구현
- 05. 스택과 스레드 이진트리
- 06. 이진트리의 복사
- 07. 이진 탐색트리
|
|
제 12 주 |
11장. 우선순위 큐
- 01. 우선순위 큐 개요
- 02. 추상 자료형 우선순위 큐
- 03. 배열, 연결 리스트, 트리에 의한 구현
- 04. 힙에 의한 우선순위 큐 구현
|
|
제 13 주 |
12장. 탐색 알고리즘
- 01. 키, 레코드, 탐색
- 02. 이진탐색
- 03. 보간탐색
- 04. 이진 탐색트리
- 05. 기수탐색
- 06. 해시
- 07. 자료구조의 선택
|
|
제 14 주 |
13장. 균형 탐색트리
- 01. AVL 트리
- 02. 스플레이
- 03. 23 트리04. 234 트리
- 05. 레드블랙 트리
- 06. B트리
|
|
제 15 주 |
기말고사 |
- |
4. 성적평가 방법 |
중간고사 |
기말고사 |
과제물 |
출결 |
기타 |
합계 |
비고 |
30% |
30% |
20% |
20% |
- |
100% |
- |
5. 수업 진행 방법 |
- |
6. 수업에 특별히 참고하여야 할 사항 |
- |
7. 문제해결 방법(실험·실습 등의 학습과정의 경우에 작성) |
- |
8. 강의유형 |
이론중심( ), 토론, 세미나 중심( ), 실기 중심( ), 이론 및 토론, 세미나 병행( ), 이론 및 실험, 실습 병행( ) |