그래프 객체 간의 연결 관계를 표현하는 자료구조 → 매우 일반적인 자료구조 오일러 문제 모든 다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제 용어 표현 위치 → 정점(node) 다리 → 간선(edge) 오일러 정리 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재 그래프 정의 수학적 표현 : G = (V, E) V는 정점(vertex)들의 집합 E는 간선(edge)들의 집합 정점들 간의 관계를 의미 → 정점들과 간선들의 각 유한집합의 자료구조 그래프의 종류 간선의 종류 무방향 간선 : 간선을 통해 양방향으로 갈 수 있음 (A, B) (A, B) = (B, A) 방향 간선 : 한쪽 방향으로만 갈 수 있음 ≠ 그래프 종류 무방향 그래프 방향 그래프 가중치 그래프, 네트워크 간선에 비용이나..

우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 우선순위큐 ADT 객체 n개의 element형의 우선순위를 가진 요소들의 모임 연산 create() ::= 우선순위 큐를 생성 init(q) ::= 우선순위 큐 q를 초기화 is_empty(q) ::= 우선순 큐 q가 비어있는지를 검사 is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사 insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가 delete(q) : = 우선순위 큐 q로부터 가장 우선순위가 높은 요소를 삭제 및 반환 find(q) ::= 우선순위가 가장 높은 요소를 반환 우선순위 큐는 2가지로 구분 최솟값 우선수위 큐 작을수록 우선순위가 높음 최댓값 우선순위 큐 높을수록 우선순위가 높음 우선순위 큐 구현방법 배열로 구현 ..

우선순위 큐란? 우선순위를 가진 항목들을 저장하는 큐 우선순위큐 ADT 객체 n개의 element형의 우선순위를 가진 요소들의 모임 연산 create() ::= 우선순위 큐를 생성 init(q) ::= 우선순위 큐 q를 초기화 is_empty(q) ::= 우선순 큐 q가 비어있는지를 검사 is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사 insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가 delete(q) : = 우선순위 큐 q로부터 가장 우선순위가 높은 요소를 삭제 및 반환 find(q) ::= 우선순위가 가장 높은 요소를 반환 우선순위 큐는 2가지로 구분 최솟값 우선수위 큐 작을수록 우선순위가 높음 최댓값 우선순위 큐 높을수록 우선순위가 높음 우선순위 큐 구현방법 배열로 구..

스레드 이진트리 목적 : 이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회 용어 중위 선행자 : 중위 순회 시에 선행 노드 중위 후속자 : 중위 순회 시에 후속 노드 스레드(thread) : 실을 이용하여 노드들을 순회 순서대로 연결시켜 놓은 것 장점 : 순회를 빠르게 할 수 있음 단점 : 스레드를 설정하기 위해 삽입이나 삭제 함수가 더 많은 일을 해야 함 구성 방법 NULL 링크에 중위 순회할 때 후속 노드(중위 후속자)를 저장시켜놓음 → 이를 스레드 이진트리라고 함 스레드 이진트리 순회 구현 #include #include #include typedef struct TreeNode{ int data; struct TreeNode *left, *right; // 오른쪽 자식 링..

이진트리 정의 : 공집합 또는 루트와 왼쪽/오른쪽 서브트리로 구성된 유한집합(서브트리는 이진트리) 모든 노드가 2개의 서브트리를 가지고 있는 트리 서브트리는 공집할 수 있음 특징 각 노드에는 최대 2개까지의 자식 노드가 존재 각 노드의 차수 ≤ 2 → 구현하기가 편리 서브트리 간 순서 존재 ( L → R ) 성질 노드의 개수가 n개이면 간선의 개수는 n-1개 높이가 h인 이진트리인 경우 최소 h개의 노드 최대 2^h-1개의 노드 n개의 노드를 가지는 이진트리의 높이 최대 n 최소 log_2(n+1)(올림) 이진트리의 분류 포화 이진트리 트리의 각 레벨에 노드가 꽉 차있는 이진트리 완전 이진트리 높이가 h일 때, 레벨 1부터 h-1까지는 노드가 모두 채워져 있음 마지막 레벨 h는 왼쪽부터 오른쪽으로 노드가..

트리 계층적인 구조를 나타내는 자료구조 부모 - 자식 관계의 노드들로 구성 트리 용어 노드(node) : 트리의 구성요소 간선(edge) : 노드를 연결하는 관계 루트(root) : 부모가 없는 노드(A) 단말 노드(terminal node) : 자식이 없는 노드( E, F, G, H, I, J ) 비 단말 노드(non-terminal node) : 적어도 하나의 자식을 가지고 있는 노드( A, B, C, D ) 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리(점선) 자식/부모/형제/조상/자손 노드 : 인간과 동일함 레벨(level) : 트리의 각 층 번호 높이(height): 트리의 최대 레벨(3) 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 트리의 종류..

단순 연결 리스트 가장 첫 노드는 head를 가리킴 마지막 노드의 링크는 NULL로 표시 끝 노드를 찾는 시간 복잡도: O(n) 원형 연결 리스트 마지막 노드의 링크가 첫 번째 노드를 가리킴 하나의 노드에서 링크를 따라가면 모든 노드 방문 가능 모든 노드의 링크가 NULL이 아니다.(head가 NULL인 경우 제외) 변형된 원형 연결 리스트 head 포인터 하나로 리스트의 처음과 끝을 가장 효율적으로 표현(찾는다) 마지막 노드 : head가 가리킴 첫 번째 노드 : head → link가 가리킴 cf) 노드가 1개일 때 : head → link가 가리키는 게 head 가장 처음에 노드 삽입하는 경우 원형 연결 리스트가 NULL(노드 0개) 일 경우 head = node; head를 NULL에서 새로운 노..

구현 사항 - 각 프로세서들이 각자의 queue를 가지고 작업을 수행 -queue 안에는 순차적으로 실행되어야 하는 Job이 존재 - 동시에 모든 큐를 진행해서 Job을 하나씩 처리한다. - 자신의 큐가 비어있으면 다른 큐에서 Job을 뺏어 처리한다. 구현 방식 큐라고는 하지만 처리하는 일은 앞에서 하고 뺏길 때 뺏기는 큐에서는 뒤에서 뺏기기 때문에 앞과 뒤에서 둘 다 요소를 뺄 수 있는 덱을 이용해야 한다. 덱을 이용해서 큐잉 모델 형식으로 구현을 하면 된다고 생각하고 구현하였다. 구현 #include #include #define MAX_DEQUE 100 int total = 0; typedef struct{ char* data[MAX_DEQUE]; int front,rear; }Deque; void..