자료구조 김현성

교재 및 참고문헌 교재 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);      }    } }