전체 글

트리를 순회하는 방법은 전위, 중위, 후위 순회가 있다. 레벨 순회는 표준적인 순회 방법은 아니지만 자주 사용된다. 레벨 순회(Level Order) : 각 노드를 레벨 순으로 검사하는 순회 방법 구현 원리는 다음과 같다. 1. ptr을 큐에 삽입한다. 2. 큐가 empty가 아닐 때 큐에서 삭제하고 삭제한 값을 ptr로 둔다. 3. ptr의 왼쪽 노드와 오른쪽 노드가 있다면 각각을 큐에 삽입한다. 4. 2~3 과정을 반복한다. 1) level_order(root)인 경우 초기 상태이다. 2) ptr이 5를 가리키므로 큐에 넣는다. 3) 5의 왼쪽과 오른쪽 자식이 존재하므로 차례대로 큐에 넣는다. ptr은 여전히 5를 가리킨다. 4) 큐에서 삭제한 값이 ptr이 되고 ptr의 왼쪽과 오른쪽 자식을 큐에 ..

1. 순차탐색(Sequential search) : 정렬되지 않은 배열의 항목들을 처음부터 끝까지 하나씩 검사해 원하는 항목을 찾는 방법 구현 원리는 다음과 같다. low에서 high까지 key와 비교하고 탐색에 성공하면 위치를 반환, 실패하면 -1 반환 int seq_search(int key, int low, int high) { for (int i = low; i 찾고자 하는 값 : 찾고자 하는 값이 배열의 왼쪽에 존재 - 중앙값 < 찾고자 하는 값 : 찾고자 하는 값이 배열의 오른쪽에 존재 먼저 이진 탐색을 순환적으로 구현하면 다음과 같다. int BSearch(int key, int low, int high) { int mid; if (low list[mid]) return BSearch(key..

최단 경로 알고리즘은 대표적으로 다익스트라와 플로이드 알고리즘이 있다. Dijkstra : 어떤 정점부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 Floyd : 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 구하는 알고리즘 1. 다익스트라 알고리즘 집합 S : 최단 경로가 이미 발견된 정점들의 집합 1차원 배열 distance : 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 저장하는 배열, 해당 정점 간의 가중치가 저장 인접 행렬 weight : 가중치를 저장하는 행렬 다익스트라의 원리는 다음과 같다. 매 단계마다 집합 S에 속하지 않는 정점 중에서 distance 값이 가장 작은 정점들을 추가해 나간다. 새로운 정점이 S에 추가되면 S에 속하지 않는 정점들의 dis..

크기가 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 연산을 반복적으로 구현하였다.