CS/자료구조

Merge Sort Merge Sort는 하나의 리스트를 부분 리스트로 점차 분할하여 각 부분 리스트를 정렬한 다음 다시 부분 리스트를 합병해 정렬하는 방법이다. 반복적으로 구현하는 방법이 있지만 결론적으로 재귀적인 방법이 효율적이기에 재귀적인 Merge Sort를 소개할 것이다. // 정렬할 리스트를 분할해 2개의 부분 리스트 생성 int rmergeSort(element a[], int link[], int left, int right) { if (left >= right) return left; int mid = (left + right) / 2; return listMerge(a, link, rmergeSort(a, link, left, mid), rmergeSort(a, link, mid+1, ..

Stable Sorting vs Unstable Sorting Stable Sorting은 같은 두 수를 정렬할 때 그 수의 순서가 바뀌지 않고 유지되며 정렬되는 것이다. 반대로 Unstable Sorting은 같은 두 수를 정렬할 때 그 수의 순서가 서로 바뀌면서 정렬되는 것이다. Insertion Sort 삽입 정렬은 정렬된 배열에 한 숫자씩 삽입해 정렬하는 것이다. 정렬된 배열의 뒷부분부터 비교하며, 삽입하려는 수보다 큰 경우에만 인덱스를 줄여 비교한다. 따라서 같은 수인 경우에는 다음 인덱스에 정렬되기 때문에 Stable Sorting이다. void insert(element e, element a[], int i) { a[0] = e; while(e.key < a[i].key) { a[i+1] ..

1. 노드의 개수 구하기 // recursive int get_node_cnt(TreeNode* p) { int cnt = 0; if (p != NULL) { cnt = 1 + get_node_cnt(p->left) + get_node_cnt(p->right); } return cnt; } 2. 리프 노드 개수 구하기 int get_leafnode_cnt(TreeNode* p) { int cnt = 0; if (p != NULL) { if (p->right == NULL && p->left == NULL) return 1; else cnt = get_leafnode_cnt(p->left) + get_leafnode_cnt(p->right); } return cnt; } 3. 높이 구하기 int get_h..

이진 트리는 순환적으로 트리 전체를 방문한다. 순환 횟수는 트리의 높이에 비례하기 때문에 반복보다 비효율적이다. 스레드 이진트리는 일반적인 이진 트리의 순회 방법과 달리 효율적이고 스택을 사용하지 않는 순회 방법이다. 일반적으로, 이진 트리에서 노드의 개수가 n일 때 루트 노드를 제외한 n-1개 링크는 다른 노드를 가리키고 n+1개의 링크는 NULL임을 알 수 있다. 이것을 이용해서 NULL 링크에 중위 후속자(successor)를 저장해놓고 순회할 수 있게 만들 것이다. 더보기 이진 트리의 정의 1) 공집합 2) 루트와 왼쪽, 오른쪽 서브 트리로 구성된 노드들의 유한집합 3) 서브 트리 또한 이진 트리여야 한다. 이제 함수를 정의해보자. 1. 트리 노드 구조체 typedef struct TreeNode..

2 + 1 * 3 을 트리로 계산하고자 한다. 먼저, 수식을 트리로 표현하면 다음과 같다. 트리를 중위 순회한 결과가 2 + 1 * 3이다. 이 수식을 계산하기 위해서는 중위 순회로 표현된 것을 후위 순회로 바꾸어 주어야 한다. 1. 중위 수식에서 후위 수식으로 먼저, 중위 수식에서 후위 수식으로 바꾸기 위해서 스택을 사용할 것이다. 규칙은 다음과 같다. 피연산자라면 배열에 저장한다. 연산자라면 우선순위를 비교해 스택에 넣는다. 스택에 있는 연산자의 우선순위가 높은 경우 : 우선순위가 높은 연산자를 꺼내어 배열에 저장하고 우선순위가 낮은 연산자를 스택에 넣는다. 스택에 있는 연산자의 우선순위가 낮은 경우 : 스택에 넣는다. 예시는 다음과 같다. 1) 초기 상태의 모습이다. 2) 2는 피연산자이므로 배열에..

트리를 순회하는 방법은 전위, 중위, 후위 순회가 있다. 레벨 순회는 표준적인 순회 방법은 아니지만 자주 사용된다. 레벨 순회(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); }..