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기반)
- 리스트 특징
- 데이터를 나란히 저장한다
- 중복 데이터 허용한다
리스트 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), 삭제할 때 데이터 이동 빈번하다
'컴퓨터기본 > 자료구조' 카테고리의 다른 글
6. Binary Search Tree (0) | 2021.06.14 |
---|---|
5. Doubly Linked List (0) | 2021.06.14 |
4. General Linear Lists (0) | 2021.06.14 |
3. Queue (0) | 2021.06.14 |
2. Stack (Linked list) (0) | 2021.06.14 |