본문 바로가기
728x90
반응형

2022-2/자료구조28

[자료구조] 7.Sorting: Heap Sort Heap sort void adjust(int list[], int root, int n) { int rootkey = list[root], child = 2 * root; while (child list[child]) break; //그 자식보다 rootkey가 크면 멈춤 else {//자식이 rootkey보다 큰 경우 list[child / 2] = list[child]; //자식을 위로 보냄 child *= 2; } } list[child / 2] = rootkey; //rootkey 입력 } void heapsort(int list[], int n) { int i, j; int temp; for (i = n / 2; i > 0; i--) {//n/2는 자식을 가지는 가장 끝의 값 adjust(li.. 2022. 12. 13.
[자료구조] 7. Sorting Sorting의 응용 분야 이진 검색(binary search) 두 리스트의 동일성/합집합/차집합/교집합 계산 Stable Sorting 리스트에서 같은 키 값이 여러 개 존재하는 경우, 해당 값의 순서가 sorting 전의 순서로 유지되는 경우 Sort 알고리즘의 종류 Internal sorting(내부 정렬): 메모리 상에서 정렬 External sorting(외부 정렬): 리스트 내용이 커서 메모리에 저장될 수 없는 경우 사용 삽입 정렬(Insertion Sort) void insertion_sort(int list[],int n) { int next; for(int i=1;i=0 && next 2022. 12. 3.
[자료구조] 그래프 - 작업 네트워크 두 가지 종류의 네트워크가 있다. AOV (Activity on Vertex) Networks AOE (Activity on Edge) Networks AOV (Activity on Vertex) 작업을 정점으로 표현한 방향성 그래프이다. edge는 작업들간의 선후 관계를 표현한다. u에서 v로 가는 방향 경로가 존재할 때 u를 v의 predecessor, v를 u의 successor 라고 한다. 선수과목을 AOV로 표현한 예시 Topological Order vertex들 간의 선행 관계를 고려하여 모든 vertex의 선형순서를 정의하는 것. topological order은 여러 개 존재할 수 있다. 더보기 #include #include #define MAX_VERTICES 6 struct node.. 2022. 11. 29.
그래프 - 최단거리 Single Source All Destinations 하나의 출발점에서 나머지 각각의 vertex들 까지의 최단거리를 구하자.. Dijkstra Algorithm n개의 vertex가 있다 found[n]배열이 있다. 그래프는 인접 행렬로 표현, cost[n][n]이다. 결과는 distance[n]에 저장한다. #define MAX_VERTICES 6 int cost[][MAX_VERTICES] = { {0,50,10,1000,45,1000}, {1000,0,15,1000,10,1000}, {20,1000,0,15,1000,1000}, {1000,20,1000,0,35,1000}, {1000,1000,30,1000,0,1000}, {1000,1000,1000,3,1000,0} }; int distanc.. 2022. 11. 24.
Biconnected Components/최소 비용 신장트리 단절점(articulation point) 그래프 G의 vertex, v로서 v와 v에 부속된 edge들을 삭제할 경우, G가 두 개 이상의 connected component들로 분할되는 vertex들 이중 결합 그래프(biconnected graph) 단절점이 없는 connected graph 이중 결합 부분 그래프(biconnected component) (a)는 connected graph인데, 빨간색으로 그어놓은 vertex를 삭제하게 되면 그래프가 끊어지게 된다. 이 빨간 vertex들이 단절점(articulation point)인 것이다. (b)는 biconnected components들이다. 단절점이 없어 무엇 하나를 끊어도 모두 연결되어있다는 뜻이다. vertex가 두개 뿐인 것도 bi.. 2022. 11. 22.
6장 - 기초적인 그래프 연산들 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 연결 요소(Connected Components) 신장 트리(Spanning Trees) 이중 결합 요소와 단절점 Depth First Search (DFS) include #include #define FALSE 0 #define TRUE 1 #define MAX_VERTICES 10 short int visited[MAX_VERTICES];//방문표시할 리스트 node graph[MAX_VERTICES]; struct node{ int vertex; node* link; }; void dfs(int v) { struct node* w; visited[v] = TRUE; printf("%5d", v); for (w = graph[v]; w; w = w-.. 2022. 11. 18.
6. Graphs 그래프(graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조. 그래프로 표현함으로써 문제를 쉽게 모델링하여 해결할 수 있다. 그래프 데이터 타입 그래프 G의 두 가지 구성 요소 V(G): G에 포함된 vertex(정점)들의 집합 E(G): G에 포함된 edge(간선)들의 집합 G=(V,E)라고 쓰기도 함. 무방향성 그래프와 방향성 그래프. 무방향성 그래프(undirected graph): edge의 방향성이 없음. (u,v), (v,u)는 동일한 edge를 표현한다. 방향성 그래프(directed graph=Digraph): edge에 방향성이 존재함. 는 u에서 v로 간다는 뜻. 그래프에서 사용되는 용어들. 완전 그래프(complete graph): Edge의 수가 최대인 그래프. n개의 .. 2022. 11. 14.
5장 - Forests/Find-Union forest: 여러 개의 트리들을 모아놓은 것. forest로 연결할 트리 A,E,G가 있다 이 트리들을 우선 이진트리로 바꾼다.(왼쪽-자식, 오른쪽-형제) 그럼 root노드는 형제가 없기 때문에, 이진트리에서 root의 오른쪽 자식은 항상 비게 된다 이 점을 이용해서, 여러 트리들을 root의 오른쪽 자식 노드로 연결-연결한다. tree들을 forest로 표현 한 후의 inorder, preorder, postorder은 각각 어떻게 변할까? inorder, preorder의 경우는 tree일때와 forest일 때가 동일하게 나오지만 postorder은 다르다! Forest 순회 방법 preorder Traversal of Forest F F가 empty이면 return F의 첫번째 트리의 root를 .. 2022. 11. 14.
5장 - Threaded Binary Tree/Selection Tree Treaded Binary Tree n개의 노드를 갖는 이진 트리에는 2n개의 링크가 존재하는데, 2n개의 링크 중 n+1개의 링크의 값은 null이다(단말노드) 이 null링크들을 다른 노드에 대한 포인터로 대체하자. ptr->left_child=NULL인 경우 inorder predecessor을 가리키도록 변경 ptr->right_child=NULL인 경우 inorder successor을 가리키도록 변경 노드의 구조 struct thread_tree { short int left_thread; struct thread_tree* left_child; char data; short int right_thread; struct thread_tree* right_child; }; 기존의 노드에서 lef.. 2022. 11. 7.
5장 - Heaps Heap 최대 트리(max tree): 트리의 모든 노드에 대해 부모 데이터 값>자식 데이터 값 최대 힙(max heap): 최대 트리이면서 완전 이진 트리 최소 트리(min tree): 트리의 모든 노드에 대해 부모 데이터 값 heap[i / 2].key)) { heap[i] = heap[i / 2]; } heap[i] = item; } 배열의 끝에 새로운 노드를 추가한다.==> ++(*n) 추가된 위치부터 parent노드를 한 단계씩 조사한다. 부모보다 값이 크다면 자리를 바꾸고, 부모보다 값이 작아지거나 root가 될 때까지 반복한다. delete element delete_max_heap(int* n) { int parent, child; element item, temp; if (HEAP_EMP.. 2022. 11. 4.
5장 TREES 트리에 관련된 용어들 노드의 차수 (내 일촌관계 아들의 수) 단말 노드 (자식이 없는 노드) Parent, Children, Siblings Ancestor(조상), Descendants(자손) (M의 조상: H,D,A) (B의 자손: E,F,K,L) Level(루트로부터 단순 경로의 길이. 루트가 1임), Height or Depth (4) 트리의 표현 Left Child - Right Sibling 표현 왼쪽노드 - 자식, 오른쪽 노드 - 형제 이 때 모든 노드의 차수가 2 이하가 되는데, 이런 트리를 이진 트리라고 함. 이진 트리 이진트리의 모든 노드의 차수(degree)는 2를 넘지 않는다. ==> 두개를 초과하여 쪼개지지 않음 왼쪽 서브트리와 오른쪽 서브트리가 구분 편향 트리와 완전 이진트리 완.. 2022. 10. 30.
동치 알고리즘 #include #include #define MAX_SIZE 24 #define IS_FULL(ptr) (!(ptr)) #define FALSE 0 #define TRUE 1 struct node { int data; struct node* link; }; int main(void) { short int out[MAX_SIZE]; struct node* seq[MAX_SIZE], * x, * y, * top; int i, j, n; printf("Enter the size( 2022. 10. 20.
4장 - 이중 연결 리스트 지금까지의 연결 리스트는 한 노드에 링크가 하나였다. 이중 연결 리스트는 이전 노드, 다음 노드를 가리키는 링크가 각각 하나씩, 링크가 총 두개인 노드로 이루어져 있다. struct node { struct node* llink; int data; struct node* rlink; }; 물론 이중 연결 리스트도 체인형, 원형 둘 다 구현 가능하다 원형 이중 연결 리스트에 노드 추가 void dinsert(struct node* node, struct node* newnode) { //newnode를 node의 오른쪽에 추가 newnode->llink = node; newnode->rlink = node->rlink; node->rlink->llink = newnode; node->rlink = newn.. 2022. 10. 20.
추가적인 리스트 연산 추가적인 리스트 연산들 chain의 방향을 반대로 변경: invert() 두 개의 chain을 통합: concatenate() 원형 리스트에 대한 연산 수행 시, 마지막 노드에 접근하기가 어렵다. 이를 해결하기 위해 원형 리스트의 이름은 마지막 노드를 가리키도록 하자. invert() struct node * invert(struct node* lead) {//lead가 가리키는 리스트의 방향을 반대로 변경한다. struct node* middle, * tail; middle = NULL; while (lead) { //lead가 널이 아닐떄까지 tail = middle; middle = lead; lead = lead->link; middle->link = tail; //middle의 링크를 반대로 바.. 2022. 10. 20.
4장 - 연결리스트를 이용한 스택과 큐 배열과 연결 리스트의 비교 저장 방식의 차이 배열: 메모리의 인접한 곳에 저장 연결 리스트: 각 노드들은 메모리의 여러 곳에 나누어 저장되고, link포인터를 이용하여 다음 노드의 주소를 기억함 메모리 사용 측면 저장될 데이터의 수를 안다면 배열이 효과적.(연결 리스트는 data 뿐 아니라 link포인터가 필요) 데이터 수를 모를 경우, 새로 데이터가 입력될 때마다 malloc 실행 후 연결하면 되는 연결 리스트가 유리함. 정렬된 데이터의 유지 배열: 데이터가 추가될 때 기존 데이터의 위치를 변경해야 할 수 있음, 이진 검색 가능 연결 리스트: 데이터가 추가되더라도 기존 데이터의 위치 변경은 발생하지 않음. 이진 검색 불가능 배열을 이용한 스택과 큐의 구현 방법의 문제점으로 메모리 낭비, stack fu.. 2022. 10. 14.
4장 - List 배열을 이용한 순서화 리스트: 임의의 위치에 대한 삽입과 삭제 연산이 곤란. 가변 길이의 순서화 리스트 지원 불가. 연결 리스트를 이용한 순서화 리스트: 리스트는 노드들로 구성, 각 노드는 데이터와 링크로 구성됨. 링크는 리스트의 다음 노드를 가리킴. (마지막 노드의 링크는 NULL) 단일 연결 리스트(Singly Linked Lists) 각 노드들은 메모리의 인접한 곳에 위치하지 않는다. 각 노드의 주소는 프로그램 실행시 매번 다를 수 있다. 리스트의 이름 = 첫 번째 노드의 주소가 된다. 배열에 비해) 삽입과 삭제시 기존 노드들의 위치를 변경할 필요가 없다 배열에 비해) 링크 필드를 위한 추가적인 메모리 공간이 필요하다 연결 리스트의 구현(C) struct node{ int data; struct n.. 2022. 10. 9.
3장 - 수식 계산(Evaluation of Expressions) Precedence : 연산자들 간의 우선 순위(*연산이 +연산보다 우선순위 높음) Associativity: 동일한 우선순위를 갖는 연산자들간의 실행 순서 (ex: +,-,*,/ - >left to right) 중위 표기법(Infix notation) : 피연산자들 사이에 연산자가 위치함. 사람이 쓰는 방식. 계산 과정이 복잡하다 후위 표기법(Postfix notation) : 피연산자들 다음에 연산자가 위치. 괄호가 필요 없고 한번의 스캔으로 수식 계산 가능 중위표기법 3+4*2 ==> 후위표기법 342*+ (a/(b - c + d) ) * (e - a ) * c ==> abc-d+/ea-*c* Postfix 수식의 계산 앞에서부터 차례대로 피연산자(숫자)는 스택에 저장, 연산자의 경우 스택에서 숫자.. 2022. 10. 6.
3장 - 미로찾기(Stack 이용) #include #define MAX_STACK_SIZE 100 #define M 10 #define P 10 #define EXIT_ROW 10 #define EXIT_COL 10 int maze[M + 2][P + 2]; //미로 int mark[M + 2][P + 2]; //방문기록용 typedef struct { short int x; short int y; }offsets; offsets move[8]; //8개의 방향을 배열에 넣어놓고 쓸 것임 typedef struct { short int row; short int col; short int dir; }element; element stack[MAX_STACK_SIZE]; //지나간 경로를 저장할 스택 void path(void) {//미로.. 2022. 10. 5.
3장 - 스택(Stack)과 큐(Queue) 순서화 리스트의 종류 중 스택,큐가 있다. 스택(Stack) 삽입과 삭제가 'top'이라 불리는 한 쪽 끝 지점에서 발생하는 순서화 리스트 시스템 스택(Run-time Stack) 시스템에서 함수 호출을 처리하기 위해 사용 재귀함수 호출의 성능과 관련 스택의 구현 #include #define MAX_SIZE 101 typedef struct { int key; }element; element stack[MAX_SIZE]; int top = -1; //top을 -1로 초기화하였음. bool IsEmpty() { if (top = MAX_SIZE - 1) return true; else ret.. 2022. 9. 30.
2장 - 다차원 배열, 배열의 주소 다차원 배열을 저장하는 방법은 두 가지가 있다. 1. 행 우선 순서(Row major order) 2. 열 우선 순서(Column major order) 행 우선 순서의 경우 A[2][4]라는 배열 안에 A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] A[1][2] A[1][3] 순서로 저장되어 있는 것이고,(인덱스를 보면 행을 기준으로 오름차순 정리되어있다) 열 우선 순서의 경우는 A[0][0] A[1][0] A[0][1] A[1][1] A[0][2] A[1][2] A[0][3] A[1][3] 순서로 저장되어 있는 것이다.(인덱스를 보면 열을 기준으로 오름차순 정렬되어 있다) 행 우선 순서의 주소 계산 A[5][7][6] 크기의 배열이 있다고 하자 A[0][0][0.. 2022. 9. 28.
728x90
반응형

티스토리툴바