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

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

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

2 이번 학기 수강신청은? 영어회화(2/3) 전산수학(3/3) 디지털로직(3/3), Lab(1/2)
Java 프로그래밍 (3/3), Lab(1/2) C 프로그래밍 연습 (3/3)

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

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

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

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

7

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

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 문제 #8 목수가 고객이 주문한 책상의 가격을 계산하고자 한다. 사용자로부터 책상의 가로 길이, 세로 길이, 나무 종류, 서랍의 개수를 입력 받아서 다음과 같이 책상의 가격을 계산하는 프로그램을 작성하라. 책상의 길이는 인치단위 정수로 입력받는다고 가정한다. 모든 책상의 제작비는 최소한 200달러이다. 책상의 면적이 750제곱인치를 초과하면 50달러를 추가한다. 만일 나무가 마호가니이면 150달러를 추가하고, 오크이면 125달러를 추가하고, 소나무이면 추가하지 않는다. 각 서랍마다 30달러를 추가한다. 총 제작비에 대해서 10%의 부가세가 부여된다. 위 문제를 분석하고, 알고리즘을 작성하라.

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

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

20 프로그램 작성 방법 프로그램 작성 과정 입력 데이터 출력 데이터 처리사항 문제 분석 알고리즘 작성 코딩

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

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

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

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

25 알고리즘 작성 다음 순서도의 출력 값은? 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

26 RAPTOR 활용 순서도 작성 Raptor source: http://raptor.martincarlisle.com

27 RAPTOR 활용 순서도 작성

28 RAPTOR: 프로시저 작성 add procedure 항목을 나타나게 하려면 mode에서 intermediate를 선택 시작
main에 마우스를 위치하고 오른쪽 버튼을 클릭하면, (add subchart, add procedure)의 항목에서 선택

29 RAPTOR: 프로시저 작성 main에서 add procedure 선택시 생성 함수 이름 입력
Input 콘트롤을 끌어당겨서 붙인다 매개변수 이름 입력 매개변수 전달방법으로 input, output, 또는 둘다 선택

30 RAPTOR: 프로시저 작성 입력 프롬프트 입력 마우스 우측 버튼 클릭시 생성 입력값을 할당하는 변수 입력
“Enter a number” x 마우스 우측 버튼 클릭시 생성 입력값을 할당하는 변수 입력

31 Call 컨트롤을 끌어와서 main 에 배치 우측 버튼을 클릭하여 ‘edit’ 선택

32 호출할 함수 입력 우측 버튼을 클릭하여 ‘edit’ 선택시 생성

33 출력변수 입력 우측버튼 클릭시 ‘edit’선택시 생성 Output 콘트롤을 끌어와서 배치

34 알고리즘 기술 언어: 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

35 알고리즘 기술 언어: 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 c: array [1..max] of integers end real a(1:n) 기타 부울 값은 true/false 사용 논리연산자: and, or, not 관계연산자: <, =, ≠, >, <=, >= 한 줄에 2개 이상 문장 나열시 세미콜론으로 구분

36 알고리즘 기술 언어: 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

37 알고리즘 작성 주어진 순서도를 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