1. 기본개념

포인터

• & : 주소 연산자
• * : 간접지시 연산자

int i, j, *pi, *pj;

i = 20;
pi = &i;
j = *pi;
*pi = 10;
pj = &j;
*pi = *pj;

	value	address
i	20 10 20	3000
j	20	3004
pi	3000	3008
pj	3004	30012

 

동적 메모리 할당 (heap 기법)

malloc

• 필요한 양의 공간을 요구하는 함수
• 사용할 경우 : 메모리 영역의 시작 주소 반환
• 사용하지 않을 경우 : Null 포인터 반환

+ free() 함수 : 영역을 시스템에 반환

 

int i, *pi;
float f, *pf;

i = 1024;
pi = (int *)malloc(sizeof(int));
*pi = i;
f = 3.14;
pf = (float *)malloc(sizeof(float));
*pf = f;
printf("%d %d %f %f", i, *pi, f, *pf);
free(pi);
free(pf); //free 사용하지 않을 시 에러가 발생할 수 있다.

	value	address
i	1024	9000
pi	12000	9004
f	3.14	9008
pf	12004	9012
	...	...
	1024	12000
	3.14	12004

 

 

알고리즘

특정한 일을 수행하는 명령어들의 유한 집합

 

조건

• 입력 : 외부에서 제공되는 데이터가 0개 이상이어야 한다.
• 출력 : 적어도 하나의 결과를 생성해야 한다.
• 명확성 : 모호하면 안 된다.
• 유한성 : 한정된 수 뒤에는 종료한다.
• 유효성 : 실행 가능해야 한다.

 

선택정렬

서로 다른 정수를 정렬하는 프로그램

주어진 리스트에서 최소값을 찾아 제일 앞에있는 값과 교체하는 방식을 반복한다.

void sort(int list[], int n){
    int i, j, min;
    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]);
    }
}

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

// 매크로 정의
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

 

이진 탐색 (Binary Search)

이미 정렬된 배열에서 searchnum이 있는지 검사하는 프로그램

중간값을 기준으로 searchnum이 중간값보다 작으면 중간값 왼쪽값들로,

searchnum이 중간값보다 크면 중간값 오른쪽에 있는 값들을 가지고 다시 탐색하는 방식이다.

ex)

#define COMPARE(x, y) ((x)<(y)? -1 : ((x)==(y))? 0 : 1);
int compare (int x, int y){
    if(x < y) return -1;
    else if(x == y) return 0;
    else return 1;
}

int binsearch(int list[], int searchnum, int left, int right){
	while(left <= right){
    	mid = (left+right)/2;
        switch(COMPARE(list[mid], searchnum){
            case -1 : left = mid+1; break;	// list[mid] < searchnum
            case 0 : return mid;			// list[mid] == searchnum
            case 1 : right = mid-1;			// list[mid] > searchnum
        }
    }
    return -1; // 못 찾은 경우
}

 

데이터 추상화

• 기본 자료형
  • char
  • int
  • float
  • double
• 자료의 그룹화
  1. 배열 : 같은 자료형
  2. 구조 : 다른 자료형

성능 분석

• 성능평가
  • 성능평가 : 시간과 공간의 추산, 복잡도 이론
  • 성능 측정 : 컴퓨터 의존적 실행시간
• 정의
  • 공간 복잡도 : 프로그램 실행 완료시 필요한 공간의 양
  • 시간 복잡도 : 프로그램 실행 완료시 필요한 컴퓨터? 시간의 양