자료구조 김현성.

Slides:



Advertisements
Similar presentations
C 언어 컴퓨터학과 C 언어 ( STS ) (Chap5. Selection-Making Decisions ) C 언어.
Advertisements

스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
제6장 조건문.
슬라이드 1~21까지는 각자 복습! 슬라이드 22부터는 수업시간에 복습
배열, 포인터 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
C++ Espresso 제3장 배열과 포인터.
C++ Espresso 제3장 배열과 포인터.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
시스템 생명 주기(System Life Cycle)(1/2)
쉽게 풀어쓴 C언어 Express 제8장 함수 C Express.
쉽게 풀어쓴 C언어 Express 제8장 함수 C Express.
시스템 생명 주기(System Life Cycle)(1/2)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
2007 1학기 10 함수 활용.
제3장 추가 실습 3장 관련 C 언어 프로그래밍 실습.
쉽게 풀어쓴 C언어 Express 제8장 함수 C Express Slide 1 (of 26)
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
시스템 생명 주기(System Life Cycle)(1/2)
쉽게 풀어쓴 C언어 Express 제4장 변수와 자료형 C Express.
제5장 제어명령
6장. printf와 scanf 함수에 대한 고찰
쉽게 풀어쓴 C언어 Express 제9장 함수와 변수 C Express.
CHAP 9 : 정렬.
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 02. 프로그램의 기본구성.
쉽게 풀어쓴 C언어 Express 제3장 C프로그램 구성요소 C Express.
Chapter 9 정렬(sorting) SANGJI University Kwangman KO
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
C언어 프로그래밍의 이해 Ch05. 명령문 Phylogenetic: 계통, 발생(학)의.
Chapter 3 Flow of Control
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express.
6장 배열.
쉽게 풀어쓴 C언어 Express 제7장 반복문 C Express.
정렬과 합병.
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
개정판 누구나 즐기는 C언어 콘서트 제6장 반복문 출처: pixabay.
다음 주 과제 3장 읽어오기 숙제 해서 제출하기. 자료구조와 알고리즘, 순환 E304호,
컴퓨터 프로그래밍 기초 - 4th : 수식과 연산자 -
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
함수와 변수 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제어문 & 반복문 C스터디 2주차.
선택 정렬 #define SWAP(x, y, t) {(t) = (x); (x) = (y); (y) = (t);}
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
프로그래밍 기초와 실습 Chapter 11 Recursion.
실습과제 1(조건문, ) 표준입력으로 수축기 혈압을 입력 받아 그에 따른 적당한 표현을 화면에 출력하는 프로그램을 if-else 문을 이용하여 작성.
Fflush 사용이유 및 방법 [이유] 키보드에서 입력된 내용은 입력버퍼에 저장되었다가 Enter 키가 들어오면 프로그램으로 전달됨 이 때 입력버퍼에 있는 Enter 키도 프로그램으로 전달됨 그러므로 아래와 같은 프로그램에서 문자 하나를 입력해도 Enter키도 입력된 것으로.
#1 배열 활용 #include int main(void) { int i; int grade[5]; grade[0] = 10; grade[1] = 20; grade[2] = 30; grade[3] = 40; grade[4] = 50; for(i=0;i.
6장 반복제어문 for 문 while 문 do while 문 기타 제어문.
C언어 프로그래밍의 이해 Ch05. 명령문.
CHAP 12 : 탐색.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
-Part1- 제7장 반복문이란 무엇인가.
18장. 다차원 배열 그리고 포인터.
-Part1- 제8장 조건문이란 무엇인가 (교재 199페이지 ~ 224페이지)
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Internet Computing KUT Youn-Hee Han
쉽게 풀어쓴 C언어 Express 제6장 조건문 C Express Slide 1 (of 28)
쉽게 풀어쓴 C언어 Express 제6장 조건문 C Express.
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
-Part2- 제2장 다차원 배열이란 무엇인가.
알기쉽게 해설한 데이터구조 고 갑 승 한남대학교
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
어서와 C언어는 처음이지 제16장.
어서와 C언어는 처음이지 제23장.
어서와 C언어는 처음이지 제22장.
배열, 포인터, 함수 Review & 과제 1, 2.
프로그래밍 기법 최적화 프로그래밍.
Presentation transcript:

자료구조 김현성

교재 및 참고문헌 교재 C로 쓴 자료구조론 이석호역 사이텍미디어

평가 중간고사 30 % 기말고사 30% 과제물 30% 과제물 : 매주 1회 정도 출석 10%

제1장 기본개념

1.1 시스템 생명 주기 요구사항 분석 설계 정제와 코딩 검증

1.1 시스템 생명 주기 (1) 요구사항(requirements) • 프로젝트들의 목적을 정의한 명세들의 집합   • 프로젝트들의 목적을 정의한 명세들의 집합   • 입력과 출력 정보의 기술 (2) 분석(analysis)     • 문제들을 실제 다룰 수 있을 정도의 작은 단위로 나눔   • 상향식(bottom-up) / 하향식(top-down) (3) 설계(design)   • 자료 객체들과 수행될 연산들의 관점      - 추상 자료형(abstract data type)      - 알고리즘의 명세와 설계 기법

1.1 시스템 생명 주기 (4) 정제와 코딩(refinement & coding) • 자료 객체에 대한 표현 선택   • 자료 객체에 대한 표현 선택   • 수행될 연산에 대한 알고리즘 작성 (5) 검증(Verification)    • 정확성 증명(correctness proofs)      - 수학적 기법들을 사용하여 프로그램의 정확성 증명   • 테스트(testing) : 테스트 데이타와 수행 가능한 코드      - 프로그램의 정확한 수행 검증      - 프로그램의 성능 검사   • 오류(error) 제거      - 독립적 단위 테스트      - 통합 테스트

1.2 알고리즘 명세 알고리즘 특정한 일을 수행하기 위한 명령어의 유한 집합 finite set of instructions performing specific task

1.2 알고리즘 명세 조건(criteria) 입력 : (외부) 원인 ≥ 0 출력 : 결과 ≥ 1 명백성(definiteness) : 모호하지 않은 명확한 명령 유한성(finiteness) : 유한한 단계 후에 종료 유효성(effectiveness) : 각 연산은 실행가능 명령

1.2 알고리즘 명세  program ≡ algorithm    flowchart ≢ algorithm              (명백성과 모호성의 결여)

1.2 알고리즘 명세 예제 [선택 정렬] n ≥ 1 개의 서로 다른 정수를 정렬

1.2 알고리즘 명세 예제 [선택 정렬] : n ≥ 1 개의 서로 다른 정수를 정렬 1) “정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다”     - 정수들이 배열(array), list에 저장       -  i 번째 정수는 list[i], 1 ≤ i ≤ n, 에 저장

1.2 알고리즘 명세 예제 [선택 정렬] : n ≥ 1 개의 서로 다른 정수를 정렬 2) for (i = 0; i < n; i++) {     list[i]에서부터 list[n-1]까지의 정수 값을 검사한 결과      list[min]이 가장 작은 정수 값이라 하자;      list[i]와 list[min]을 서로 교환;    }

1.2 알고리즘 명세 • 최소 정수를 찾는 작업 ① 최소 정수가 list[i]라 가정       ② list[i]와 list[i+1] ~ list[n-1] 비교          - 더 작은 정수를 만나면 새로운 최 소정수로 선택

1.2 알고리즘 명세 • 최소 정수 값을 list[i] 값과 교환하는 작업 - 함수 정의 : swap(&a, &b) void swap(int *x, int *y) {     int temp = *x;         *x = *y;          *y = temp; }   - 매크로 정의     #define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

1.2 알고리즘 명세 void swap(int *x, int *y) /* 매개 변수 x, y는 정수형을 갖는 포인터 변수이다 */ {     int temp = *x;  /* temp 변수를 int로 선언하고  x가                         가리키는 주소의 내용을 지정한다 */        *x = *y;   /* y가 가리키는 주소의 내용을 x가                         가리키는 주소에 저장한다 */        *y = temp; /* temp의 내용을 y가 가리키는 주소에                         저장한다 */ } 

#include <stdio.h> #include <math.h> #define MAX_SIZE 101 #define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) void main(void) {    int i, n;    int list[MAX_SIZE];    printf("Enter the number of numbers to generate: ");    scanf("%d", &n);    if (n<1 || n>MAX_SIZE) {      fprintf(stderr, "Improper value of n\n");      exit(1);    }    for (i=0; i<n; i++) {/* randomly generate numbers*/      list[i] = rand() % 1000;      printf(%d  ", list[i]);    sort(list, n);    printf("\n Sorted array:\n ");    for (i=0; i<n; i++) /* print out sorted numbers */      printf("%d  ", list[i]);    printf("\n"); }

1.2 알고리즘 명세 #define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) void sort(int list[], int n) /* selection sort */ {    int i, j, min, temp;    for (i=0; i<n-1; i++) {      min = i;      for (j=i+1; j<n; j++)        if (list[j]<list[min]) min = j;       SWAP(list[i], list[min], temp);    } }

1.2 알고리즘 명세 정리 1.1 함수 SORT(list, n)는 n ≥ 1 개의 정수를 정확하게 정렬한다. 그 결과는 list[0], ..., list[n-1]로 되고 여기서 list[0] ≤ list[1] ≤... ≤ list[n-1]이다.

1.2 알고리즘 명세 증명 i=q에 대해, 외부 for문이 완료되면 list[q] ≤ list[r], q < r ≤ n 이다. 다음 반복에서는 i>q 이고 list[0]에서 list[q]까지는 변하지 않는다. 따라서 for문을 마지막으로 수행하면(즉, i=n-2), list[0] ≤ list[1] ≤... ≤ list[n-1]가 된다.

1.2 알고리즘 명세 예제 [이진탐색] : 정수 searchnum이 배열 list에 있는지 검사  - list[0] ≤ list[1] ≤... ≤ list[n-1]  - 주어진 정수 searchnum에 대해 list[i] = searchnum인 인덱스 i를 반환  - 없는 경우는 -1 반환  • 초기 값 : left = 0, right = n-1  • list의 중간 위치 : middle = (left + right) / 2  • list[middle]과 searchnum을 비교

1.2 알고리즘 명세 예제 [이진탐색] : 정수 searchnum이 배열 list에 있는지 검사 1) searchnum < list[middle] :         list[0] ≤ searchnum ≤ list[ middle - 1]         right = middle-1  2) searchnum = list[middle] :  middle을 반환  3) searchnum > list[middle] :           list[middle+1] ≤ searchnum ≤ list[n-1]           left = middle+1 ==> n개의 입력에 대해서 logn 단계를 반복 수행

1.2 알고리즘 명세 예제 [이진탐색] : 정수 searchnum이 배열 list에 있는지 검사 while (there are more integers to check) {    middle = (left + right) / 2;    if (searchnum < list[middle])       right = middle - 1;    else if (searchnum == list[middle])            return middle;         else left = middle + 1; }

1.2 알고리즘 명세 #define COMPARE(x,y) ((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)  int binsearch(int list[], int searchnum, int left, int right) {    int middle;    while (left<=right)  {      middle = (left + right)/2;      switch (COMPARE(list[middle], searchnum)) {        case  -1: left = middle + 1;            break;        case   0: return middle;        case   1: right = middle - 1;      }    }    return -1; }

1.2 알고리즘 명세 순환 알고리즘 :수행이 완료되기 전에 자기 자신을 다시 호출 - direct recursion : 자기 자신을 직접 호출 - indirect recursion : 자신을 호출한 함수를 다시 호출 • Fibonacci 수, factorial, 이항 계수    

int binsearch(int list[], int searchnum, int left, int right) { /* search list[0] ≤ list[1] ≤... ≤ list[n-1] for searchnum*/    int middle;    while (left <= right)  {      middle = (left + right) / 2;      switch (COMPARE(list[middle], searchnum)) {        case  -1: return                binsearch(list, searchnum, middle+1, right);        case   0: return middle;        case   1: return                binsearch(list, searchnum, left, middle-1);      }    }    return -1; }

1.2 알고리즘 명세 예제 [순열] : n ≥ 1 개의 원소를 가진 집합 모든 가능한 순열 -{a, b, c} : {(a,b,c),(a,c,b),(b,a,c), (b,c,a),(c,a,b),(c,b,a)} - n 원소 : n! 개의 상이한 순열 - {a, b, c, d}  1) a로 시작하는 {b, c, d}의 모든 순열  2) b로 시작하는 {a, c, d}의 모든 순열  3) c로 시작하는 {a, b, d}의 모든 순열  4) d로 시작하는 {a, b, c}의 모든 순열

void perm(char *list, int i, int n) /* generate all the permutations of list[i] to list[n]*/ {    int j, temp;    if (i == n)  {      for (j = 0; j <= n; j++)        printf("%c", list[j]);      printf("        ");    }    else  {    /* list[i] to list[n] has more than one permutation,       generate these recursively */      for ( j = i; j <= n; j++)  {        SWAP(list[i], list[j], temp);        perm(list, i+1, n);      }    } }