데이터 구조 - 소개 순천향대학교 컴퓨터공학과 2016. 3. 3 하 상 호.

Presentation on theme: "데이터 구조 - 소개 순천향대학교 컴퓨터공학과 2016. 3. 3 하 상 호."— Presentation transcript:

1 데이터 구조 - 소개 순천향대학교 컴퓨터공학과 하 상 호

2 강의 개요 강의실 및 시간: 과목 홈페이지: 교재: M 610
Tue 09:00 ~ 10:30, Thr 13:30 ~ 15:00 과목 홈페이지: > 강의 자료 > 데이터 구조: 이론 및 실습 교재: C 언어로 쉽게 풀어쓴 자료구조(개정판), 천인국 외 2명, 생능출판사, 2014.

3 강의 개요 학부 기초 과목(반드시 수강해야 함) 무엇을 배우는가? 컴퓨터 공학에서 매우 기초적이면서도 중요한 과목
프로그램에서 빈번히 사용되는 자료구조를 살펴본다 배열, 구조체 리스트, 스택, 큐, 트리, 그래프 이러한 구조를 조작하는 다양한 연산 알고리즘을 배운다 이러한 구조를 활용하는 문제를 해결한다. 알고리즘을 분석하고 평가한다

4

5 강의 개요 강의 내용 2학기 알고리즘에서 1장 자료구조와 알고리즘 2장 순환 3장 배열, 구조체, 포인터 4장 리스트
5장 스택 중간고사 6장 큐 7장 트리 8장 우선순위 큐 9장 정렬 10장 그래프 11장 해싱 12장 탐색 2학기 알고리즘에서

6 강의 개요 수강시 유의사항 학습 평가 이 강좌의 선수과목은 C 프로그래밍 반드시 데이터 구조 실습을 함께 수강해야 함
과제물이 제시되며, 제출기한을 엄수해야 함 퀴즈를 실시함 강의 자료는 과목 홈페이지에 사전에 게시하며, 수업 전에 반드시 출력해와야 함 학습 평가 중간고사: 25%, 기말고사: 25%, 퀴즈: 20% 보고서: 25%, 기타: 5%

7 WIU_데이터구조 카페 활용 Café 주소 카페에서 무엇을 볼 수 있는가? 웹/앱에 네이버 카페 가입
카페 앱 설치: ‘네이버카페’ 앱 검색/설치 수강생은 반드시 카페 가입해야 함 카페에서 무엇을 볼 수 있는가? 주차별 게시판 운영 학습 목표 및 내용 자기 성찰 게시판(reflection bulletin board) 운영 토론 게시판 운영 학습 자료: 퀴즈

8 WIU_데이터구조 카페 활용 여러분은 카페에서 무엇을 하는가? 자기 성찰 게시판 과목 포트폴리어 작성
자신이 이해한 것을 다시 한번 복습해보고 적어보는 게시판 모든 수강생은 주차별 게시판에 자기가 이해한 것을 정리하여 올려야 함 오프라인 그룹 스터디 내용을 핸드폰 사진으로 찍어 올릴 수 있음 다른 학생이 이해한 것을 보고서 부족한 부분을 이해 과목 포트폴리어 작성 한 학기동안 올린 게시글을 한글 파일에 복사(화면캡쳐)하여 붙여서 하나의 파일로 만들어 제출 (term 프로젝트) WIU 게시글 기반 포트폴리오 우수 콘테스트 참여 (대학 교수학습지원센터 주관)

9 Questions? 여러분의 C 프로그래밍 능력은?

10 문제 #1 2개의 정수 값을 전달받고, 이들의 평균 값을 구하여 반환하는 C 함수 calc_avg()를 작성하라.

11 문제 #2 2개의 정수 값을 전달받아서, 이들의 값을 교환하여 반환하는 C 함수 swap()을 작성하라.

12 문제 #3 초단위의 시간을 전달받아서 시, 분, 초 단위로 변환하여 반환하는 C 함수 sec2hour()를 작성하라.
x seconds p Hours q Minutes r Seconds

13 문제 #4 사용자로부터 전화 통화시간(분단위)을 전달받아서 다음 기준으로 통화 요금을 계산하여 반환하는 C 함수 calc_fee()를 작성하라. 통화 요금은 분당 100원이다. 통화 시간이 60분을 넘어서면 요금에 15%가 할인된다. 통화 요금에 4%의 부가세가 추가된다. 단, 부가세는 할인 요금이 적용된 후에 추가된다.

14 문제 #5 한 은행 구좌에 입금된 금액을 전달받아서 10년 후에 그 구좌 잔고를 계산하여 반환하는 calc_balance()를 작성하라. 단, 년 이율이 6%이며, 이율은 복리로 계산된다고 가정한다.

15 문제 #6 100개의 정수를 포함한 배열을 전달받아서 최대 값을 구하여 반환하는 c 함수 get_max()를 작성하라.

16 문제 #7 한 개의 정수를 전달받아서 그 수에 포함된 수들의 합을 구하여 반환하는 C 함수 isum()을 작성하라. 12345
15

17 프로그램 작성 방법 주어진 문제에 대해서 어떻게 프로그램을 작성하는가?

18 프로그램 작성 방법 주어진 문제에 대해서 어떻게 프로그램을 작성하는가? 프로그램 구성

19 프로그램 작성 방법 프로그램 작성 과정 알고리즘 작성 분석 수행 입력 데이터 처리사항 출력 데이터

20 프로그램 작성 방법 문제 요구사항을 정확히 기술 문제를 분석한다 알고리즘을 작성한다 프로그램을 작성한다
문제를 완벽하고 모호함없이 기술 문제가 무엇을 요구하는지 기술 문제를 분석한다 문제의 입력과 출력을 식별 입출력변수 정의 및 관계식 도출 문제해결 제약사항 및 추가 요구사항 고려 알고리즘을 작성한다 문제 해결 과정을 단계적으로 기술 알고리즘 생성(데이터를 읽어들이고, 데이터를 처리하고, 그 결과를 출력) 프로그램을 작성한다 코딩 프로그램을 테스트하고 검증한다 다양한 입력 데이터에 대해서 테스트 입력 및 출력 데이터에 기준하여 프로그램 검증

21 프로그래밍 보고서 작성 방법 다음 6단계로 구분하여 순서대로 작성해야 한다. 그렇지 않으면 평가되지 않거나 감점이 불가피하다.
문제 요구사항을 정확히 기술 다음 6단계로 구분하여 순서대로 작성해야 한다. 그렇지 않으면 평가되지 않거나 감점이 불가피하다. 문제를 분석한다 알고리즘을 작성한다 프로그램을 작성한다 프로그램을 테스트하고 검증한다 의견

22 문제 분석 I O P E 입력 데이터 출력 데이터 처리사항: 입출력관계 예제 입력 데이터 식별
각 데이터에 대한 변수명, 타입 결정 I 출력 데이터 출력 데이터 식별 각 데이터에 대한 변수명, 타입 결정 O 처리사항: 입출력관계 출력 데이터가 입력 데이터로 어떻게 도출 되는지 고려 입출력 데이터간의 관계식 도출 입출력 데이터 관계 도출을 위한 예제 생성 P 예제 예제 제시 E

23 알고리즘 작성 알고리즘 기술 언어 순서도(flow chart) 의사코드(또는 유사코드)(pseudocode)

24 알고리즘 작성 다음 순서도의 출력 값은? start end readData Declare int A[50] variables
int i, tmp readData 다음 순서도의 출력 값은? tmp←A[0] i←1 i < n no yes A[i]>tmp no yes tmp 출력 tmp←A[i] i++ end

25 알고리즘 기술 언어: SPARKS While 문 For 문 Do-while 문 배정문 조건문 Case 문 변수 <- 식
if (조건식) then S1 else S2 endif if (조건 식) then S Case 문 case { : cond1: S1 : cond2: S2 … : condn: Sn : else: Sn+1 endcase While 문 while cond do S repeat For 문 for variable <- start to finish by increment do Do-while 문 loop until cond repeat

26 알고리즘 기술 언어: SPARKS 함수 변수 선언 타입 입출력문 기타 procedure 함수이름 (매개변수리스트)
declarations S return 식 end 함수이름 입출력문 read(매개변수 리스트) print(매개변수리스트) 변수 선언 Integer a, b 타입 Integer, real, character, boolean Integer a(0..size-1) type term = record a: real b: integer end real a(1:n) 기타 부울 값은 true/false 사용 논리연산자: and, or, not 관계연산자: <, =, ≠, >, <=, >= 한 줄에 2개 이상 문장 나열시 세미콜론으로 구분

27 알고리즘 기술 언어: SPARKS procedure MAX(a, n) global real xmax parameters integer n; real a(1:n) local integer i xmax <- a(1) for i <- 2 to n do if a(i) > xmax then xmax <- a(i) endif repeat end MAX start integer xmax call readData(a, n) call MAX(a, n) print(xmax) end

28 알고리즘 작성 주어진 순서도를 SPARKS의 알고리즘 기술 언어로 변환하라. start end readData Declare
variables int A[50] int i, tmp readData 주어진 순서도를 SPARKS의 알고리즘 기술 언어로 변환하라. tmp←A[0] i←1 i < n no yes A[i]>tmp no yes tmp 출력 tmp←A[i] i++ end