CS (43) 썸네일형 리스트형 [인프런|13강] C로 배우는 자료구조 | 연결 리스트 (2) 연결리스트 (2) int main() { Node *head = (Node *)malloc(sizeof(Node)); head->data = "Tuesday"; head->next = NULL; Node *q = (Node *)malloc(sizeof(Node)); q->data = "Thrusday"; q->next = NULL; head->next = q; q = (Node *)malloc(sizeof(Node)); q->data = "Monday"; q->next = head; head = q; Node *p = head; while(p!=NULL) { printf("%s\n", p->data); p = p->next; // 다음 노드의 주소를 p에 담는다. 맨 마지막 노드까지 출력되기 위해! } .. [인프런|Dynamic Programming(1)] 영리한 프로그래밍을 위한 알고리즘 강좌 Dynamic Programming Recursive의 경우 이미 했던 호출을 다시 부르는 중복이 발생하여 효율이 떨어진다. ex) Fibonacci Numbers Memoization(Top-down) 배열에 중간 계산 결과를 저장한다(caching) 시작이 상위 사례부터 하위 사례(base case)까지 점점 작아지면서 호출되므로 위에서부터 시작된다하여 Top-down이라 한다. Dynamic programming(Bottom-up) 초기 작은 case부터 상위, 최종 case까지 값을 계산하면서 올라온다하여 Bottom-up이라 한다. binomial coefficient 이항계수 계산 N개 중에 K를 뽑는 경우를 계산한다. 수학적으로는 N! / (N-K)! K! 과 같이 풀 수도 있겠지만 컴퓨터 .. [인프런|그래프(1)] 영리한 프로그래밍을 위한 알고리즘 강좌 그래프 개념과 표현 - (무방향) 그래프 G=(V,E) V: 노드(node) 혹은 정점(vertex) E: 노드쌍을 연결하는 에지(edge) 혹은 링크(link) 개체(object)들 간의 이진관계를 표현 n=|V|, m=|E| - 방향그래프(Directed Graph) G=(V,E) 에지(u,v)는 u로부터 v로의 방향을 가짐 - 가중치(weighted) 그래프 에지마다 가중치(weight)가 지정 그래프의 표현 - 인접 행렬(adjacency matrix) - 인접리스트 (adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 2m개 edge1개당 2개가 필요 그래서 2*m개가 필요 degree는 인접한 정점의 개수이다. 인접리스트는 노드의 최대 개수.. [인프런|12강] C로 배우는 자료구조 | 연결 리스트 (1) 연결 리스트 (1) 개념과 기본연산 - 리스트 기본적인 연산: 삽입(insert), 삭제(delete), 검색(search) 등 리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결 리스트 - 배열 장점 랜덤 액세스가 가능하다. 어떤 위치이든 인덱스를 통해 접근 쉽다. 시작 주소 + 가고자 하는 곳의 위치(ex 4번째 칸이면 4) * 1칸의 크기(데이터 타입의 기본 바이트 ) 단점 크기가 고정 -reallocation이 필요하다. 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다. - 연결 리스트 다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능하며, 길이의 제한이 없다. 하지만 랜덤 액세스가 불가능하다. 연결 리스트는 물리적으로 연속된 공간 데이터를 저장하지 않는다 노드는.. [인프런|11강] C로 배우는 자료구조 | 전화번호부 v5.0 (2) 전화번호부 v5.0 (2) 구조체에 대한 포인터, 동적 메모리 할당 전화번호부 v5.0 (1)(구조체에 대한 포인터) 이어서 동적메모리 할당을 적용한 전화번호 프로그램을 만든다. 위 그림처럼 Person ** directory 포인터 배열에 동적메모리 할당을 한다. #define INIT_CAPACITY 100 typedef struct person { // person은 생략가능 char *name; // 배열로 쓰기 위해 *로 선언 char *number; char *mail; char *group; } Person; Person **dicrectory; int capacity; int n; void init() { directory = (Person **)malloc(INIT_CAPCITY *siz.. [인프런|10강] C로 배우는 자료구조 | 전화번호부 v5.0 (1) 전화번호부 v5.0 (1) 구조체에 대한 포인터, 동적 메모리 할당 v4.0에서 구조체를 배열로 사용하였다. 배열 각 칸에 name, number 등 등 여러 변수가 저장된다. 함수를 호출할 때 넘겨주는 매개변수를 실질매개변수라고한다. 호출되는 함수에서 넘겨받는(복사되는) 매개변수를 형식매개변수라고 한다. 위 '함수 호출 과정에서 매개변수의 복사' 그림에서 void status()에서 print_person(directory[i])를 부를 때 directory[i]가 실질매개변수가 되며 void print_person(Person p) p가 형식매개변수가 여기서 실질매개변수가 형식매개변수로 복사가 되어서 사용된다. 그러므로 구조체 배열로 선언하여 넘겨주고 받게되면 매번 함수를 호출할때마다 구조체의 항목(.. [인프런|9강] C로 배우는 자료구조 | 전화번호부 v4.0 전화번호부 v4.0 더 많은 항목, 구조체 추가 이름을 제외한 일부 항목이 누락되어도 작동되도록 한다. 추가, 검색의 경우 공백 입력이 많이 되었더라도 실제로는 공백 1개로 인식되게한다. 구조체 - 항상 같이 붙어다녀야 하는 데이터를 별개의 변수들에 분산해서 저장하는 것은 바람직하지 않다. - 어떤 한 사람의 이름, 전화번호, 이메일 주소 등이 그런 예이다. - C언어에서는 이런 경우 구조체(structure)를 사용한다. #include #include #include #define CAPACITY 100 #define BUFFER_LENGTH 100 typedef struct person { // person은 생략가능 char *name; // 배열로 쓰기 위해 *로 선언 char *number; .. [인프런|6,7,8강] C로 배우는 자료구조 | 전화번호부 v3.0 전화번호부 v3.0 전화번호부 v2.0(5강)에 더해 배열 재할당, 라인 단위 입력과 문자열 tokenizing 기능을 추가한다 #include #include #include #define INIT_CAPACITY 3 // 배열 재할당을 테스트하기 위해 작은 값으로 설정 #define BUFFER_SIZE 50 char ** names; char ** numbers; // char * 타입 배열이므로 char **이다. int capacity = INIT_CAPACITY; // size of arrays int n = 0; // 전화번호부 사람 수 char delim[] = " "; int main() { init_directory(); process_command(); return 0; } init_.. [인프런|5강] C로 배우는 자료구조 | 전화번호부 v2.0 전화번호부 v2.0 전화번호부 v1.0(4강)에 더해 파일로 저장 및 로드, 알파벳 순 정렬 기능을 추가한다 자료구조는 v1.0과 동일하며 load, save 함수가 추가된다. #include .. #define CAPACITY 100 #define BUFFER_SIZE 100 char * names[CAPACITY]; char * numbers[CAPACITY]; int n = 0; void load(); void add(); void find(); void status(); void remove(); void save(); int main() { char buffer[BUFFER_SIZE]; while (1){ printf("$ "); scanf("%s", buffer); if (strcmp(comm.. [인프런|4강] C로 배우는 자료구조 | 전화번호부 v1.0 전화번호부 v1.0 위와 같이 동작되도록 전화번호부 프로그램을 만든다. add, find, status, delete 등의 동작 구현 코딩 이전에 어떤 자료구조로 저장할지 프로그램의 자료구조를 먼저 생각해야한다. - 어떤 데이터를 다루고 유지해야 하는지 생각 전화번호부 v1.0의 경우 1. 내부적으로 저장해야하는 데이터는 여러사람의 이름, 전화번호 char * 타입의 names[], numbers[]를 선언 전화번호의 경우 '-' 기호를 사용하며 0으로 시작하는 경우 정수형일때 0이 빠지므로 문제가 된다. 그래서 char 타입을 사용한다. #include .. #define CAPACITY 100 #define BUFFER_SIZE 100 char * names[CAPACITY]; char * numbe.. 이전 1 2 3 4 5 다음
