크기가 n x n인 방향 그래프 a가 존재한다. 이때의 진출 차수와 진입 차수를 구하려고 한다. 더보기 정점에서 나가는 노드의 차수를 진출차수(out-degree), 정점으로 들어오는 노드의 차수를 진입차수(in-degree)라 한다. 방향 그래프 a가 인접 행렬과 인접 리스트 각각으로 구현되었을 때의 진출/진입 차수를 계산하고자 한다. 1. 인접 행렬 1) 진출 차수(out-degree) -> 인접 행렬로 구현된 경우 정점 v에 해당하는 행에서 n까지 탐색하면 된다. int Count_OutDegree(GraphType *g, int v) { int cnt = 0; for (int i = 0; in; i++) { cnt += adj_list[v][i]; } return cnt; } n만큼만 반복하면 되..
분류 전체보기
이진 트리를 순회하는 방법은 전위, 중위, 후위의 3가지 방법이 있다. 전위(preorder) : 루트 - 왼쪽 - 오른쪽 중위(Inorder) : 왼쪽 - 루트 - 오른쪽 후위(Postorder) : 왼쪽 - 오른쪽 - 루트 1. Preorder Traversal void preorder(TreeNode *p) { if (p == NULL) return; printf("%d", p->data); preorder(p->left); preorder(p->right); } 2. Inorder Traversal void inorder(TreeNode *p) { if (p == NULL) return; inorder(p->left); printf("%d", p->data); inorder(p->right); }..
이진 트리(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..
* ** *** **** ***** ****** ******* #include int main() { for (int i = 0; i < 7; i++) { for (int j = 0; j < 7 - i; j++) printf(" "); for (int k = 0; k
