Data Structure and Algorithm

사용 언어

1. 자료구조는 C언어로 개념을 설명함
2. 알고리즘은 언어와 무관한 영역이기 때문에 어떤 언어를 사용해도 상관없지만 C를 위주로 설명함

교재

주교재

두 교재는 비슷한 수준으로 설명이 되어 있어서 어느 책을 써도 상관없다. 뇌를 자극하는 알고리즘은 자료구조와 알고리즘이 같이 소개되어 있고 열혈 자료구조는 자료구조에 충실하다.

1. [한국어] "뇌를 자극하는 알고리즘," 박상현 저, 한빛미디어
   • 온라인 교재 관련 커뮤티티, 오탈자 등 정보공유 go
   • 예제 소스 및 책 소개 페이지 go
2. [한국어] "윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서," 윤성우, 오렌지미디어 go
   • 책 구매자에게 1년 온라인 무료 강의 제공
   • 발표자료 go

곁에 두고 익히면 좋은 책

1. [번역서] "다양한 예제로 학습하는 데이터 구조와 알고리즘 : 문제 해결법부터 개선법까지 (Data Structures and Algorithms Made Easy)," 나라심하 카루만치 저, 전계도 , 전형일 역, 인사이트 go
   • 소프트웨어 기술 직종 면접 준비에도 쓸 수 있을 만큼 다양한 예제를 포함.
2. [번역서] "사전처럼 바로 찾아 쓰는 알고리즘 - 바로 동작하는 실전 코드로 정리한 알고리즘 사전,"조지 T. 하인만, 게리 폴리케, 스탠리 셀코 저, 전경원 역, 한빛미디어 go
   • 조금 더 깊이 있게 공부하고 싶다면 추천하는 책
3. [한국어] "C 언어로 쉽게 풀어쓴 자료 구조," 천인국 저, 생능출판사 go
   • 부록으로 자료 구조의 개념을 이해할 수 있는 플래시 애니메이션 수록

개념 익히기 좋은 책

1. [번역서] "Hello Coding 그림으로 개념을 이해하는 알고리즘 (Grokking Algorithms)," 아디트야 바르가바 저, 김도형 역, 한빛미디어 go
   • 개념 이해하기 아주 좋은 쉬운 책, 그림이 재미있음

Schedule

Part I - Basic Data Structures

주차	주제	수업 전 할 일	수업 내용	숙제	읽어오기
1	자료구조 및 알고리즘 과목 소개 배열, 포인터, 자료구조	컴퓨터프로그래밍기초 복습	수업 소개 배열의 문법 배열과 포인터의 관계 포인터 연산자의 종류와 활용 구조체: 사용자 정의 타입	malloc()을 이용한 메모리 할당 방법과 간단한 예제 프로그램 따라하여 원리 파악하기
2	링크드 리스트	1. 링크드 리스트를 정의하고 실생활에 링크드리스트로 표현 가능 것들은 조사. 2. 위에서 찾은 것을 다른 방식으로 표현하는 방법은 무엇이고 어떤 것이 더 효율 적인가? 3. 친구와 토론하고 내용을 1페이지로 정리하여 제출	퀴즈: 배열, 포인터, 구조체, malloc 수업 전 활동 평가 개념 잡기 리스트의 주요 연산: 탐색, 삭제, 삽입, 리스트의 장단점: 어떤 경우에 배열이나 링크드 리스트를 써야 할까? 더블링크드 리스트와 환형 더블 링크드 리스트	링크드 리스트를 이용하여 다항식의 덧셈, 뺄셈과 곱셉 프로그램 작성하기	[뇌자알] 1장 [열혈] 3, 4, 5장
3	스택	1.장스택을 정의하고 실생활에서 스택이 쓰이는 사례 2. 링크드 리스트와 배열로 스택을 구현한다면 어떻게 해야 할까? 3. 친구와 토론하고 내용을 1 페이지로 정리하여 제출	퀴즈: 링크드 리스트의 주요 연산 수업 전 활동 평가 개념 잡기 스택의 기본 연산: 배열 vs 링크드 리스트 사칙 연산의 표기법: 전위, 중위 후위 표기법 스택을 이용한 계산기	후위표기법을 중위 표기법으로 변환하는 프로그램 작성하기	[뇌자알] 2장 [열혈] 6장
4	큐	1. 큐를 정의하고 실생활에서 큐가 쓰이는 사례 2. 스택 2개로 큐를 구현하는 방법은? 3. 친구와 토론하고 내용을 1페이지로 정리하여 제출	퀴즈: 스택의 주요 연산 수업 전 활동 평가 개념 잡기 큐의 기본 연산: 배열 vs 링크드 리스트	큐를 이용하여 LRU 기법 구현하기	[뇌자알] 3장 [열혈] 7장
5	트리	1. 바이너리 트리를 정의하고 사전에서 단어를 찾는 방법과 바이너리 트리로 단어를 찾는 방법을 비교해보기 2. 언제 바이너리 트리가 사용되고 이것으로 표현 가능한 것은? 3. 친구와 토론하고 내용을 1페이지로 정리하여 제출	퀴즈: 큐의 주요 연산 수업 전 활동 평가 개념 잡기 용어 정리 트리의 기본 연산 트리의 표현 방법 순회 방법: 전위, 중위, 후위	허프만 코드 구현하기	[뇌자알] 4장 [열혈] 8장
6	중간고사 I	시험 공부	수요일 13:00-15:00 강의실 추후 공지 시험 범위: 배열, 포인터, 자료구조, 링크드리스트, 스택, 큐, 트리 관련 배운 모든 주제

Part II - Widely used Data Structures

주차	주제	수업 전 할 일	수업 내용	숙제	읽어오기
7	알고리즘 성능분석, 재귀문	1.책에서 성능분석을 읽고 LINK 의 문제 풀어보기 2. 재귀문을 사용해서 좋은 점과 나쁜 점; 언제, 왜 쓰는 것이 좋을까? 3. LINK 의 코드 분석하기 4. 친구와 토론하고 내용을 각자가 1페이지로 정리하여 제출	시험 리뷰 내용 복잡도의 이해: 시간 vs 공간 빅오 표기법 재귀의 개념 재귀 필수 조건: Termination Condition 하노이의 탑	피보나치 수열을 계산하는 프로그램을 재귀문으로 그리고 순차프로그램으로 작성하고 그 성능을 비교하기(n은16, 32, 64, 128)	[뇌자알] 11장 성능분석 [열혈] 1장 성능분석 2장 재귀
8	정렬	1. 실생활에 정렬이 필요한 사례 5가지를 들고 정렬 방법을 구체적으로 작성하기 2. 가장 느린 정렬 방법과 가장 빠른 정렬 방법을 비교하고 왜 그 속도가 나오는지 이해하기 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 복잡도, 빅오 표기법, 재귀문 수업 전 활동 평가 내용 버블 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 정렬의 성능	임의의 만 개의 숫자를 생성하고, 이 숫자들을 버블, 삽입, 병합, 퀵 정렬을 이용하여 정렬하여 성능 비교하기	[뇌자알] 5장 [열혈] 10장 ‘’’참고영상 버블, 삽입 병합 퀵소트
9	탐색	1. 탐색의 속도 2. 사전에서 단어를 찾는 방법과 바이너리 트리로 단어를 찾는 방법을 비교해보기 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 버블, 삽입, 병합, 퀵 정렬, 성능 수업 전 활동 평가 내용 이진탐색트리 균형잡힌 이진 탐색 트리: Red Black 트리, AVL 트리 트리의 성능	T.B.D.	[뇌자알] 6장 [열혈] 11, 12장
10	그래프	1. 실생활에서 그래프의 예제를 찾아보자 2. 그래프의 표현 방법 조사하기 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 이진탐색 트리, RB 트리, AVL 트리, 트리의 성능 수업 전 활동 평가 내용 인접 행렬 vs 인접 리스트 그래프 순회: 깊이 우선, 너비 우선 탐색 최소 신장 알고리즘: 프림, 크루스칼 알고리즘 최단 경로 탐색	T.B.D.	[뇌자알] 9장 [열혈] 14장
11	중간고사 II	시험공부	수요일 13:00-15:00 강의실 추후 공지 시험 범위: 알고리즘 성능 분석, 정렬, 탐색, 우선순위 큐 관련 배운 모든 주제

Part III - Fundamental Algorithms

주차	주제	수업 전 할 일	수업 내용	숙제	읽어오기
12	해시테이블'		시험 리뷰 내용 해시 함수: 공간 vs 시간 기본 해시 함수 동작 충돌 해결하기	T.B.D.	[뇌자알]' 8장 [열혈] 13장
13	분할정복'	1. 분할 정복이 가장 많이 쓰이는 곳은? 2. 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 해시테이블 수업 전 활동 평가 내용 Revisit: 병합정렬, 피보나치수열	T.B.D.	[뇌자알]' 12장
14	동적계획법'	1. 동적 계획법을 조사하기 2. 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 분할정복 수업 전 활동 평가 내용 동적계획법 이해하기 : 탐색 vs 수학적 해법 vs 메모화 재귀 vs 동적 계획법 배낭 문제를 이용한 동적계획법 이해	T.B.D.	[뇌자알]' 13장 [탑알트] 7장
15	백트래킹'	1. 백트래킹을 조사하기 3. 친구와 토론하고 내용을 각자가 1 페이지로 정리하여 제출	퀴즈: 동적계획법 수업 전 활동 평가 내용 미로 탈출 8개의 퀸	T.B.D.	[뇌자알]' 15장
16	기말고사'	시험공부'	수요일 13:00-15:00 ' 강의실 추후 공지 시험 범위: 해시 테이블, 분할정복, 동적 계획법, 백트래킹 관련 배운 모든 주제

공부하는 방법에 대하여

1. 나는 프로그래머다, "까치네, 깨비메일 개발자 특집" (E27 1부 E27 link, 2부 E28 link)