그래프 (Graph) G = (V, E) - 정점(Vertex), 간선(Edge)들의 집합으로 구성 - 정점, 간선 모두 데이터 저장 가능 Vertex : V(G) = { 1, 2, 3, 4, 5 } Edge : E(G) = { (1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5) } 그래프의 종류 ▶ 무방향 그래프 (Undirected Graph) 간선을 통해서 양방향으로 갈 수 있다 (A, B), (B, A)는 동일한 간선 ▶ 방향 그래프 (Directed Graph) 일방통행처럼 간선을 통해서 단방향으로만 갈 수 있다 (A, B), (B, A)는 서로 다른 간선 ▶ 가중치 그래프 (Weighted Graph) / 네트워크 (Network) 간선에 비용/가..

머신 스케줄링 - 동일한 기계 m개, 처리해야 하는 작업 n개가 존재 모든 기계를 가동해서 가장 최소의 시간 안에 작업을 모두 끝내는 것 = 머신 스케줄링 - 각 작업마다 완료까지 걸리는 시간이 다름 종료 시간이 최소인 기계를 선택 해당 기계에 작업시간이 최대인 작업을 할당한다 ▶ LPT 알고리즘 - ex) 여러 서버에 작업을 분배 할 경우, 가장 효율이 좋은 최적의 해(근사의 해)를 찾는 알고리즘 - 항상 종료시간이 최소인 기계를 선택 → 최소 히프를 통해서 구현 ----------------------------------------------------------------------------------------------------------- 기계들을 최소 히프에 전부 insert 최소 히프..

히프 정렬 (최대 히프) - n개의 요소를 O(nlog₂n)시간 안에 정렬 - 정렬되지 않은 배열 element a[]에 대하여 배열 a의 data들을 최대 히프에 차례대로 추가 최대 히프에서 data들을 하나씩 꺼내서 배열 a의 맨 뒤쪽부터 저장 배열 a에 대한 히프 정렬 완료 void heap_sort(element arr[], int len) { heapnode* h; h = create(); init_heap(h); for (int i = 0; i = 0; i--) { arr[i] = delete_node(h); } free(h); // 히프 동적 할당 해제 } Full Code..

우선순위 큐 (priority queue) - 일반적인 큐 : FIFO(First In First Out)구조 - 우선순위 큐 : 우선순위가 높은 데이터가 먼저 나간다 시뮬레이션 시스템, 네트워크 트래픽 제어, 작업 스케쥴링, 수치해석계산 등에 사용 자료구조 삭제되는 요소 Stack 가장 늦게 들어온 데이터 (LIFO) Queue 가장 먼저 들어온 데이터 (FIFO) Priority Queue 가장 우선순위가 높은 데이터 (Priority) 구현 방법 - 배열 / 연결리스트 / 히프 표현 방법 삽입 삭제 정렬 안된 배열/연결 리스트 O(1) O(n) 정렬 된 배열/연결 리스트 O(n) O(1) 힙 O(log n) O(log n) - 만약 n이 1000일 경우 O(n) : 1000초 / O(log₂n) :..

이진 탐색 트리 - root 기준으로 왼쪽 → root보다 작은 값 - root 기준으로 오른쪽 → root보다 큰 값 - 중위 순회 → 오름차순으로 정렬된 값 반환 1. 탐색 연산 node == NULL || key == node->key → 해당 node 리턴 key key → node = node->llink를 통해서 왼쪽 서브트리 탐색 key > node->key → node = node->rlink를 통해서 오른쪽 서브트리 탐색 - 순환 탐색 vs 반복 탐색 → 효율성 : 반복 treenode* search_recur(treenode* node, element data) { // 순환 탐색 함수 if (node == NULL || node->data == data) return n..

이진 트리 - 이진 트리에 n개의 노드가 있을 경우 2n개의 링크 존재 2n개의 링크 중, n+1개의 링크 = NULL 2n개의 링크 중, n-1개의 링크 = 다른 노드를 가리킨다 NULL 링크에 중위 선행자/후속자를 저장해 놓은 트리 = 스레드 이진 트리 스레드 이진 트리 - NULL 링크를 이용해서 순환호출 없이 트리의 노드들을 순회 가능 - 단말 노드 / 비단말 노드를 구분하기 위해 is_thread 필드 필요 - 노드의 right를 후속자를 가리키게 설정, is_thread = 1로 설정 typedef struct treenode { char data; struct treenode* left; struct treenode* right; int is_thread; // 1이면 ->right는 중위 ..

수식 트리 - 산술 연산자(+, -, *, /), 피연산자로 구성 - 피연산자 = 단말노드 - 산술 연산자 = 비단말노드 - 각 루트노드들은 산술 연산자이기 때문에 루트보다 자식 노드(피연산자)들을 먼저 방문해야한다 그러므로 후위 순회를 사용 알고리즘 root에서부터 시작해서 해당 node가 NULL이면 그냥 return (종료) -- (1) 해당 node의 left, right가 모두 NULL이면 해당 node는 단말노드 = 피연산자 ∴ return 해당 node의 data -- (2) - (1), (2)에 해당이 안되면, 각 node의 left, right에서 (1), (2) 반복 Example) root(+) → evaluate(root->left) = '*' / evaluate(root->righ..

반복적 순회 (중위 순회) - 스택을 이용해서 구현 스택에 자식 노드들을 push하고 pop하면서 순회 - 인공지능에서 지능적 탐색을 할 때 사용 알고리즘 root에서부터 root->left로 진행하면서 stack에 push ( root = root->left를 통해서 반복) -- (1) root->left가 NULL이 되면 stack에서 하나씩 pop pop한 노드를 방문해서 해당 노드에서 node->right로 이동 node->right가 NULL이면, 그냥 stack에서 pop node->right가 NULL이 아니면 node->right로 이동해서 (1) 진행 - stack이 공백이 되면 순회 종료 void inorder_iter(treenode* root) { // LVR 순으로 순회 while..

노드의 개수 1. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출) 2. 노드에 대한 각 서브트리들을 계속 순환 호출 (노드 != NULL) 3. 반환되는 값(왼쪽 서브트리, 오른쪽 서브트리 순회하면서 얻은 노드 개수)에 1을 더하기 더하기 1 : 자기 자신의 개수를 포함해야 하기 때문 int get_node_count(treenode* node) { int count = 0; if (node != NULL) count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; } 단말 노드의 개수 1. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출) 2. 순회하면서 해당 노드의 왼쪽자식 = 오른쪽자식 = NULL ..

이진 트리 순회방법 - 루트 방문 : V - 왼쪽 서브트리 방문 : L - 오른쪽 서브트리 방문 : R 루트를 언제 방문하느냐에 따라 전위(1), 중위(2), 후위(3)로 구분 ① 전위순회 (preorder traversal) : VLR 루트 노드 방문 (V) 왼쪽 서브트리 방문 (L) 오른쪽 서브트리 방문 (R) void preorder(treenode* root) { // VLR 순 if (root!=NULL) { printf("[%d] ", root->data); preorder(root->left); preorder(root->right); } } ② 중위순회 (inorder traversal) : LVR 왼쪽 서브트리 방문 (L) 루트 노드 방문 (V) 오른쪽 서브트리 방문 (R) void in..

배열로 구현한 이진트리 - 노드 i의 부모 노드 인덱스 = i/2 - 노드 i의 왼쪽 자식 노드 인덱스 = 2i - 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1 연결리스트로 구현한 이진트리 - 노드를 구조체로 표현 - 노드(데이터, 왼쪽 링크필드, 오른쪽 링크필드) typedef int element; typedef struct treenode { element data; struct treenode* left; // 왼쪽 노드로 연결하는 포인터 struct treenode* right; // 오른쪽 노드로 연결하는 포인터 }treenode; ※ Example #include #include // 연결리스트로 구현한 이진 트리 typedef int element; typedef struct treen..

트리 - 계층적 구조(hierarchical structure)을 가진 자료구조 - 부모-자식 관계의 노드들로 구성 트리의 용어 - 노드(node) : 트리의 구성요소 → A, B, C, D, E, F, G, H, I, J - 루트(root) : 각 Tree의 최상위 노드 → A - 서브 트리(subtree) : 최상위 노드를 제외한 나머지 노드 / 하나의 노드 + 그 노드들의 자식 → {B, E, F, G}, {C, H}, {D, I, J} - 간선(edge) : 노드들 사이의 선 - 단말 노드(terminal node) : 자식이 없는 노드 → E, F, G, H, I, J - 비단말 노드(nonterminal node) : 자식이 있는 노드 → A, B, C, D - 높이(height) : Tree..