1. 재귀, ADT

Big-O Notation

알고리즘의 효율성을 표기할 때 Big-O notation을 사용한다.

n²의 증가율을 n이 절대 따라잡을 수 없으므로 그냥 가장 큰 차수를 기준으로 따지는 것

ex) T(n) = 5n²+n+1 => O(n²)

 

Big-O의 정의

두 개의 함수 f(n), g(n)이 주어졌을 때, 모든 n>=k에 대해 f(n) <= g(n) 을 만족하는 상수 C와 k가 존재하면 f(n)의 Big-O는 O(g(n))이다.

pf)

 

 

Recursive Binary Search

개념: 전체 탐색 구간을 반으로 나눠가면서 해답을 찾아간다.

 

소스코드:

bSearchRec.c

#include <stdio.h>

int bSearchRec(int ar[], int first, int last, int target) {

	int mid;

	while (first <= last) {
		printf("inside loop \n");
		mid = (first + last) / 2;
		printf("mid: %d \n", mid);

		if (target == ar[mid]) {
			printf("found %d!, index: %d \n", target, mid);
			return mid;
		}
		else if (target < ar[mid]) {
			return bSearchRec(ar, first, mid - 1, target);
		}
		else if(target>ar[mid]){
			return bSearchRec(ar, mid + 1, last, target);
		}
		break; // break 대신 마지막 else if 없어지면 똑같은 결과 나옴
	}
	return -1;

}

main.c

#include <stdio.h>

int main(void) {
	int arr[7] = { 1, 3, 5, 7, 9, 11, 13 };
	int result1 = bSearchRec(arr, 0, sizeof(arr) / sizeof(int) - 1, 5);
	int result2 = bSearchRec(arr, 0, sizeof(arr) / sizeof(int) - 1, 4);

	if (result1 < 0) {
		printf("result1 not found \n");
	}
	else {
		printf("result1 index: %d \n", result1);
	}

	if (result2 < 0) {
		printf("result2 not found \n");
	}
	else {
		printf("result2 index: %d \n", result2);
	}
	return 0;
}

 

The Hanoi Tower

1) 원반을 A -> C로 옮긴다

2) 단, 작은 원반 위에 큰 원반을 놓을 수 없다.

 

해결 방법:

 

 

하노이 타워는 재귀 함수로 해결 가능하다!

 

코드 작성:

#include <stdio.h>

void hanoiTower(int num, char from, char by, char to) {

	if (num == 1) { //하나일 때는 그냥 옮김
		printf("move 1 from %c to %c \n", from, to);
	}
	else {
		hanoiTower(num-1, from, to, by); // 1번
		printf("move %d from %c to %c \n", num, from, to); // 2번
		hanoiTower(num - 1, by, from, to); // 3번
	}
}

 

결과:

Abstract Data Type

추상자료형이란, 구체적인 기능의 완성과정을 언급하지않고, 순수하게 기능이 무엇인지 나열한 것

 

배열을 이용한 리스트

- 리스트 종류: 순차 리스트(배열 기반), 연결 리스트(malloc기반)

- 리스트 특징

1. 데이터를 나란히 저장한다
2. 중복 데이터 허용한다

 

리스트 ADT operations

void ListInit(List * plist);
void LInsert(List * plist, Object data); //Object: 리스트의 요소
int LFirst(List* plist, Object* pdata);
int LNext(List* plist, Object* pdata);
Object Remove(List* plist);
int LCount(List* plist);

 

 

프로젝트 파일 구성

- ArrayList.h : 여러가지 상수 정의, List 구조체 선언, List를 사용할 함수 abstract하게 list up

- ArrayList.c: 실제 함수들 구현, ArrayList.h 포함시켜야

- Main.c: Array list를 실험

+ Object.h: 만약 array list의 멤버들이 구조체라면 구조체 정의, 구조체 접근 함수 선언

+ Object.c: 구조체 접근 함수 정의

 

1. 기본 (int as object)

arrayList.h

#include <stdio.h>
#include "Student.h"

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define ARR_LENGTH 10

typedef int LData; //이 부분만 고쳐주면 나중에 다른 구조체와 연결 가능
	
typedef struct __array_list {
	LData arr[ARR_LENGTH];
	int numOfData;
	int curPosition;
}ArrayList;

typedef ArrayList List;

void ListInit(List* plist);

void LInsert(List* plist, LData data);

int LFirst(List* plist, LData* pdata);

int LNext(List* plist, LData* pdata);

LData LRemove(List* plist);

int LCount(List* plist);


#endif

arraylist.c

#include <stdio.h>
#include "ArrayList.h"

void ListInit(List* plist) {
	plist->numOfData = 0;
	plist->curPosition = -1;
}

void LInsert(List* plist, LData data) {
	if (plist->numOfData >= ARR_LENGTH) {
		printf("array list is full \n");
		return;
	}
	plist->arr[plist->numOfData] = data;
	plist->curPosition++;
	plist->numOfData++;
}

int LFirst(List* plist, LData* pdata) {
	if (plist->numOfData == 0) {
		return 0;
	}
	plist->curPosition = 0;
	*pdata = plist->arr[plist->curPosition];
	return 1;
}

int LNext(List* plist, LData* pdata) {
	if (plist->curPosition >= plist->numOfData-1) {
		printf("end of list \n");
		return 0;
	}
	plist->curPosition++;
	*pdata = plist->arr[plist->curPosition];
	return 1;
}

LData LRemove(List* plist) {
	if (plist->numOfData == 0) {
		printf("no data to remove \n");
		return;
	}
	LData rdata = plist->arr[plist->curPosition];
	for (int i = plist->curPosition; i <= plist->numOfData - 1; i++) {
		plist->arr[plist->curPosition] = plist->arr[plist->curPosition + 1];
	}
    plist->numOfData--;
	return rdata;
}

int LCount(List* plist) {
	return plist->numOfData;
}

main.c

#include <stdio.h>
#include <malloc.h>
#include "ArrayList.h"

int main(void) {

	ArrayList list;
	LData data;
	LData* pdata;

	ListInit(&list);

	// save data
	pdata = (LData*)malloc(sizeof(LData));
	// set data
	*pdata = 1;
	LInsert(&list, pdata);

	pdata = (LData*)malloc(sizeof(LData));
	*pdata = 2;
	LInsert(&list, pdata);

	pdata = (LData*)malloc(sizeof(LData));
	*pdata = 3;
	LInsert(&list, pdata);

	pdata = (LData*)malloc(sizeof(LData));
	*pdata = 4;
	LInsert(&list, pdata);

	// print data inside list
	printf("print data inside list: \n");
	if (LFirst(&list, &pdata)) {
		printf("data: %d \n", *pdata);
		while (LNext(&list, &pdata)) {
		    printf("data: %d \n", *pdata);
		}
	}
	printf("\n");
}

 

2. 구조체를 적용해보기

구조체 Student를 사용해 보겠다. Student 구현을 위한 student.h 와 student.c

student.h

#include <stdio.h>

typedef struct student {
	char name[10];
	int age;
}Student;

void setStudent(Student* stu, char* n, int a); // 학생 정보 저장
void printStudent(Student* stu);// 학생 정보 프린트
int compareStudent(Student* stu1, Student* stu2);

student.c

#include <stdio.h>
#include <string.h>
#include "Student.h"

void setStudent(Student* stu, char* n, int a) {
	strcpy_s(stu->name, 10, n);
	stu->age = a;
}

void printStudent(Student* stu) {
	printf("name: %s, age: %d \n", stu->name, stu->age);
}

int compareStudent(Student* stu1, Student* stu2) {
	if (stu1->age == stu2->age)
		return 1;
	else
		return 0;
}

arraylist.h

#include <stdio.h>
#include "Student.h"

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define ARR_LENGTH 10

typedef Student* LData; //이 부분만 고쳐주면 연결됨
	
typedef struct __array_list {
	LData arr[ARR_LENGTH];
	int numOfData;
	int curPosition;
}ArrayList;

typedef ArrayList List;
void ListInit(List* plist);
void LInsert(List* plist, LData data);
int LFirst(List* plist, LData* pdata);
int LNext(List* plist, LData* pdata);
LData LRemove(List* plist);
int LCount(List* plist);

#endif

arraylist.c 는 바꿀 필요가 없다. 고로 생략

 

main.c 에서는 LData로 표시한 부분을 모두 Student로 바꿔줘야함

#include <stdio.h>
#include <malloc.h>
#include "ArrayList.h"

int main(void) {

	//LData부분을 모두 Student로 바꿔줘야 함

	ArrayList list;
	Student data;
	Student* pdata;

	ListInit(&list);

	// save data
	pdata = (Student*)malloc(sizeof(Student));
	//set data
	setStudent(pdata, "nyam", 20);
	LInsert(&list, pdata);

	pdata = (Student*)malloc(sizeof(Student));
	setStudent(pdata, "oyam", 21);
	LInsert(&list, pdata);

	pdata = (Student*)malloc(sizeof(Student));
	setStudent(pdata, "pyam", 22);
	LInsert(&list, pdata);

	pdata = (Student*)malloc(sizeof(Student));
	setStudent(pdata, "qyam", 23);
	LInsert(&list, pdata);

	// print data inside list
	printf("print data inside list: \n");
	if (LFirst(&list, &pdata)) {
		printStudent(pdata);
		while (LNext(&list, &pdata)) {
			printStudent(pdata);
		}
	}
	printf("\n");

    // delete data whose age is 22
	data.age = 22;

	if (LFirst(&list, &pdata)) {
		if (compareStudent(pdata, &data)) {
			pdata = LRemove(&list);
			free(pdata);
		}

		while (LNext(&list, &pdata)) {
			if (compareStudent(pdata, &data)) {
				pdata = LRemove(&list);
				free(pdata);
			}
		}
	}
	

	// print data inside list
	printf("print data inside list: \n");
	if (LFirst(&list, &pdata)) {
		printStudent(pdata);
		while (LNext(&list, &pdata)) {
			printStudent(pdata);
		}
	}
	printf("\n");
}

 

3. 리스트 장단점

- 장점: 참조가 쉽다. (index 기준으로 바로 접근 가능)

- 단점: 배열 길이를 정해야 한다. (위의 경우 ARR_LENGTH), 삭제할 때 데이터 이동 빈번하다