Data Structure and Algorithm

2018년도 1학기

수업장소: 407-508 시간 월 13:00-14:00, 수 13:00-15:00 방문장소: 407-314

사용 언어

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

교재

주교재

두 교재는 비슷한 수준으로 설명이 되어 있어서 어느 책을 써도 상관없다. 뇌를 자극하는 알고리즘은 자료구조와 알고리즘이 같이 소개되어 있고 열혈 자료구조는 자료구조에 충실하다. 세 번째 주제인 알고리즘 부분에서는 뇌를 자극하는 알고리즘을 기반으로 하고 필요에 따라 다른 책에서 내용을 가져와 보충한다.

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

개념 익히기 좋은 책

1. [번역서] "Hello Coding 그림으로 개념을 이해하는 알고리즘 (Grokking Algorithms)," 아디트야 바르가바 저, 김도형 역, 한빛미디어 go
   • 수업에서 다루는 많은 주제들을 파이썬으로 풀어낸 책. 많은 그림을 사용하여 쉽게 설명하려고 애쓴 흔적이 보이는 책. 개념을 익히고 빠르게 실습해보기 원한다면 이 책을 추천함.

곁에 두고 익히면 좋은 책

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

C 언어

1. "C Programming : A Modern Approach," K. N. King 저, W. W. Norton & Company

수업 전 활동

자료구조 및 알고리즘은 생각할 거리가 많은 과목이다. 그렇기 때문에 기본적인 것을 미리 생각하고 이해하지 않으면 시간이 갈 수록 답답해진다. 이를 해소하는 방법으로 다른 수강생들과 같이 배운 것을 토론하고 설명하는 시간을 갖으면 도움이 된다. 과외 선생님이 가장 많이 공부되는 것과 같은 원리이다. 각 주차에는 미리 생각해보고 조사할 것들 그리고 읽을 내용이 정리되어 있다. 해당 내용에 맞게 수업 전에 아래와 같이 생각하고 정리하는 시간을 갖는다.

1. 주제에 대해 미리 학습하고 자신이 이해한 것을 서로가 설명하기
2. 상대방이 한 설명과 자신의 설명을 비교하여 어느 것이 더 이해하기 쉬운 설명인지 비교하기
3. 상대방에게서 배울 것이 있었던 순으로 추천하기
4. 각자가 토론 내용 정리하여 제출

4명이 한 팀이 되어 각자가 이해하고 배운 것을 토론한다. 제출된 자료를 수업시간에 다른 수강생들과 나눈다. 그리고 그 내용을 기반으로 수업에서 다루는 주제들을 연관하여 논한다. 제출된 자료는 수업 전 활동 점수에 반영된다. 온라인으로 팀원에 대한 다음 세 가지 기준으로 순위를 정하여 제출한다. 자신을 제외한 3명의 학생에 대해 순위를 매긴다.

1. 수업 전 활동 참석 했는가
2. 성실하게 준비 했는가
3. 내가 이해하는데 기여 했는가

코드 리뷰

모든 숙제는 같이 수강한 다른 2명의 학생의 리뷰를 받아야 한다. 코드 리뷰란 작성된 코드를 읽고 버그가 있는지 요구 조건에 맞게 작성 여부 등을 검사하는 과정이다. 모든 소프트웨어 기업들은 코드 리뷰를 매우 중요하게 생각한다. 코드 리뷰를 하면서 자신의 실력도 같이 늘어 나는 경험을 해보기 바란다. 코드 리뷰하는 학생은 다음의 문항을 읽고 성실하게 답해야 한다. 제출된 코드 리뷰 결과를 참고하여 프로그래밍 과제 점수를 산정한다.

1. 코드가 누군가의 또는 인터넷의 코드를 복사 붙이기 한 것인가?
   • 복붙한 학생은 해당 과제 점수 0점
   • 발견한 학생은 복붙이라고 과제에 표기하고, 발견한 학생에게 최종 과제 점수에 +10%
2. 주석은 알기 쉽게 작성되어 있는가? (1점)
3. 변수의 이름은 사용 목적에 맞는가? (1점)
4. 함수 이름은 사용 목적에 맞는가? (1점)
5. 함수는 한 가지 목적을 위해 작성 되었는가? (1점)
6. 들여쓰기는 잘되어 있는가? (1점)
7. 요구 조건에 맞게 설계 되었는가? (1점)
8. 코드에 버그가 없는가? (1점)
9. 자신이 짠 로직과 비교하여 더 명확하고 쉽게 작성 되었는가? (1점)
10. 이 코드에서 배운 것이 있는가? (2점)

Schedule

Part I - Basic Data Structures

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

Part II - Widely used Data Structures

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

Part III - Fundamental Algorithms

주차	주제	수업 전 할 일	수업 내용	숙제	읽어오기
13	해시테이블 09_hash.pdf	1. 해시 테이블이 가장 많이 활용되는 곳은? 2. 해시를 활용하는 bloom filter를 찾아서 공부하기. 3. 친구와 토론하고 내용을 각자가 정리하여 piazza에 제출	시험 리뷰 내용 해시 함수: 공간 vs 시간 기본 해시 함수 동작 충돌 해결하기 블룸필터 이해하기	블룸 필터 구현하기	[뇌자알] 8장 [열혈] 13장 블룸필터 소개자료
14	분할정복 10_DAC.pdf	1. 분할 정복이 가장 많이 쓰이는 곳은? 2. 읽을 분량을 읽고 서로 이해한데까지 토론하기 3. 친구와 토론하고 내용을 각자가 정리하여 piazza에 제출 Battle of Austerlitz 설명 보기	퀴즈: 해시테이블 수업 전 활동 평가 내용 Revisit: 병합정렬, 피보나치수열	블룸필터 구현하기	[뇌자알] 12장
15	동적계획법 11_DP.pdf	1. 동적 계획법을 조사하기 2. 읽을 분량을 읽고 서로 이해한데까지 토론하기 3. 친구와 토론하고 내용을 각자가 정리하여 piazza에 제출	퀴즈: 분할정복 수업 전 활동 평가 내용 동적계획법 이해하기 : 탐색 vs 수학적 해법 vs 메모화 재귀 vs 동적 계획법 배낭 문제를 이용한 동적계획법 이해	Finding Longest Common Sequenece	[뇌자알] 13장 선택: [탑알트] 7장 7장_패스워크_有
16	기말고사	시험 공부	목요일 19:00-21:00 시험장소: 407동 101호 시험 범위: 해시 테이블, 분할정복, 동적 계획법 관련 배운 모든 주제	Good Luck! ;)

Review Questions

이메일로 퀴즈 이력을 판단합니다. 다음 링크에 공유 바랍니다.INFO 오직 첫 답변만 성적으로 인정합니다.

1. 2018-03-07 1st week Review Questions
2. 2018-03-14 2nd week Review Questions
3. 2018-03-19 3rd week -1 Struct Review Questions
4. 2018-03-28 4th week -2 List Review Questions
5. 2018-04-04 5th week -2 Stack Review Questions
6. 2018-04-25 8th week -2 Algorithm Analysis and Recursion
7. 2018-05-02 9th week -2 Review questions on Tree
8. 2018-05-09 10th week -2 Review questions on sorting

숙제 제출 및 질의응답

이 수업의 모든 숙제, peer review와 질의 응답은 piazza를 통해서 합니다.

Teams

Number	Names
1	김묘정, 박소희, 박철희, 심민선
2	김은진, 우이정, 정유진, 이승은
3	송명재, 김예헌, 이민지, 고성진
4	허동원, 조재현, 유준호, 박지윤
5	이가원, 김보경, 김나리, 정혜린
6	김성헌, 박진상, 오상권, 이원태
7	박다빈, 박경은, 김태훈, 최석원
8	김근홍, 이성록, 정창익, 손상민
9	구민수, 전병복, 이창희, 이혁진
10	정하륜, 노영덕, 김은민, 유민지
11	차창혁, 이종범, 이보석
12	이진혁, 권상은, 한미진

Evaluation

범주	비율	범주	비율
수업전활동	10	중간고사I	20
과제	15	중간고사II	20
퀴즈	15	기말고사	20
출석	없음	총 합	100%

공부하는 방법에 대하여

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

참고 사이트

유용한 사이트들이 있다면 추천 바랍니다.

1. visualgo 다양한 알고리즘들의 동작 방식을 시각화함
2. sorting.at 정렬 알고리즘을 비교해볼 수 있음
3. Data Structure Visualization 투박한 디자인이지만 핵심을 잘 시각화함