CS/자료구조

이진 트리(Binary Tree)는 모든 노드가 2개의 서브 트리를 가지는 트리이다. 각 노드는 최대 2개까지의 자식노드를 가질 수 있고 그 자식노드가 공집합이어도 된다. * 이진 트리의 성질 n개의 노드, n-1개의 간선 높이가 h인 이진 트리에서 노드는 최대 2^h-1개 가질 수 있고, 최소 h개를 가진다. 노드가 n개인 이진 트리에서 높이는 최대 n까지, 최소┌log(n+1)┓를 가질 수 있다. * 이진 트리의 종류 포화이진트리(Full Binary Tree) : 높이가 k인 이진 트리에서 2^k-1개의 노드를 가지는 트리 완전이진트리(Complete Binary Tree) : 높이가 k인 이진 트리에서 높이 k-1까지 노드가 모두 채워진 트리 기타 * 이진 트리의 표현 배열 이용 이진 트리를 배열..

하노이탑 문제는 백준 알고리즘 문제로 구현한 적이 있으므로 간략하게 쓰겠다. 그 링크는 https://2nnsv.tistory.com/18 [C] 백준 11729 : 하노이 탑 이동 순서 1. 문제 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 2nnsv.tistory.com 하노이 탑의 조건은 다음과 같다. 한 번에 하나의 원판 이동 맨 위의 원판만 이동 가능 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음. 중간의 막대를 임시로 사용할 수 있지만 위의 조건을 지켜야 함. int hanoi(int n, char fro..

순환의 세번째 주제인 피보나치 수열은 앞의 두 개의 숫자를 더해 뒤의 숫자를 만드는 것이다. f(n) = f(n-1) + f(n-2) 순환으로 구현하면 다음과 같다. int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); } 실제로, fibonacci(5) 를 구현하면 다음과 같다. fibonacci(5) 호출 fibonacci(4) 호출 fibonacci(3) 호출 fibonacci(2) 호출 fibonacci(1) 호출 fibonacci(0) 호출 fibonacci(1) 호출 fibonacci(0) 호출 fibonacci(2) 호출 fibonacci(1) 호출 fib..

이전 게시글과 유사하게 반복과 순환의 기법으로 프로그래밍할 것이다. power 함수를 반복적으로 구현하면 다음과 같다. int power(double x, int n) { double result = 1.0; for (int i = 0; i

팩토리얼 : n * (n-1) * ... * 2 * 1 을 구하는 연산 int factorial (int n) { if (n 0; i++) { result *= i; } return result; } factorial 연산을 반복적으로 구현하였다.

1. 우선순위 큐를 구현하는 방법 배열 기반 연결 리스트 기반 힙 기반 배열 기반 연결 리스트 기반 단점 삽입/삭제 시 모든 데이터를 한칸씩 이동, 우선순위 비교 시 모든 데이터와 비교 삽입 위치를 찾기 위해 처음부터 마지막까지 데이터의 우선순위 비교 이런 이유로 힙으로 구현하는 것이 가장 쉽다. 2. 힙 힙이란 ? : 완전 이진 트리의 일종으로 루트 노드에 우선 순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조 힙의 종류 Max Heap : 모든 노드에 저장된 값은 자식 노드의 값보다 크거나 같아야 함. Min Heap : 모든 노드에 저장된 값은 자식 노드의 값보다 작거나 같아야 함. 3. 우선순위 큐의 구현 1) 데이터 저장 과정을 간략하게 보면, 새 데이터를 마지막 위치에 저장 계속해서 부모 ..

1. 삽입 1. 가장 앞에 삽입하는 경우 - 새 노드를 만들어 추가할 데이터를 저장한다. - 새 노드의 next 필드가 현재의 head 노드를 가리키도록 한다. - 새 노드를 새로운 head로 한다. Node *tmp = (Node*)malloc(sizeof(Node)); tmp->data = "Ann"; tmp->next = head; head = tmp; 2. 중간에 삽입하는 경우 - 새 노드를 만들어 추가할 데이터를 저장한다. - 새 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다. - 새 노드를 prev의 다음 노드로 만든다. Node *tmp = (Node*)malloc(sizeof(Node)); tmp->data = "Jim"; tmp->next = prev->next; prev..

1. 연결리스트에서 하나의 노드를 표현하기 위한 구조체를 선언한다. struct node { char *data; // 데이터 필드 struct node* next; // 링크 필드 }; typedef struct node NODE; NODE *head = NULL; // 첫 노드의 주소를 저장할 포인터 data next 하나의 노드는 데이터 필드와 링크 필드로 구성된다. 링크 필드는 다음 노드의 주소를 저장하며, 첫 노드의 주소는 head 라는 포인터 변수에 따로 저장해야 한다. 2. head 노드를 생성한다. head = (NODE*)malloc(sizeof(NODE)); head->data = "Tuesday"; head->next = NULL; // 반드시 마지막 노드임을 NULL로 표시 head..

// 전화번호부 v5.0 #include #include #include #define CAPACITY 100 #define BUFFER_LENGTH 100 typedef struct person { char* name; char* number; char* email; char* group; } Person; Person ** directory; // 구조체의 포인터 배열 -> 주소값만 저장되기 때문에 복잡한 과정 생략됨 int capacity, n; char delim[] = " "; void init() { directory = (Person**)malloc(CAPACITY * sizeof(Person*)); capacity = CAPACITY; n = 0; } int readline(FILE* fp..

#include #include #include #define CAPACITY 100 #define BUFFER_LENGTH 100 typedef struct person { char* name; char* number; char* email; char* group; } Person; Person directory[CAPACITY]; int n = 0; char delim[] = " "; int readline(FILE * fp, char str[], int lim) { int ch, i = 0; while ((ch = fgetc(fp)) != '\n' && ch != EOF) if (i < lim) str[i++] = ch; str[i] = '\0'; return i; } void add(char* n..