복습노트 복습노트

C++ 에서 사용할 수 있는 STL중 하나인 map입니다. 먼저 map을 사용하기 위해서는 위와 같이 헤더파일을 입력해줍니다. mapmap 이런식의 선언으로 사용가능합니다. map은 pair 형태로 data가 저장되며 로 이루어 집니다. map은 key의 중복값을 허용하지 않으며, 저장될 때는 key를 기준으로 자동적으로 오름차순으로 저장됩니다. 저장되는 형태는 red-black tree형태로 저장됩니다. 따라서 삽입이나 삭제를 할 때 시간복잡도가 O(log n)을 보장합니다. 1) 선언 key의 data type과 value의 data type을 결정할 수 있습니다. mapm1; mapm2; mapm3; mapm4; 2) 삽입 mapmap1; map1.insert({ 1,"kang" });//key가 ..

자료구조인 그래프를 탐색하는 방법입니다. #define MAX_VERTICES 50 typedef struct node* node_pointer; typedef struct node { int vertex; node_pointer link; }; node_pointer graph[MAX_VERTICES]; int n = 0; 기본 설정입니다. 변수 n은 현재 사용하고 있는 정점의 갯수 를 나타냅니다. DFS (깊이 우선 탐색) Root node 한개를 선택해 하나의 자식 노드를 집중적으로 계속 탐색하고 탐색이 끝나면 Root node의 다음 자식 노드를 선택해 또 탐색하는 방법입니다. void dfs(int v) { node_pointer w; visited[v] = TRUE; printf("%5d", ..

Union은 각각의 tree가 서로 연결되어 있지 않고 독립적으로 있을때 서로 독립되어 있는 tree를 연결시키는 작업입니다. 여기서 Disjointset이란 서로소 집합이란 의미로 서로 집합된 부분에서 중복되는 수가 없어야 합니다. 예를들어 다음과 같은 tree가 있을때 우리는 parent 배열을 만들 수 있습니다. S1의 Root는 0이고 S2의 Root는 4고 S3의 Root는 2입니다. 따라서 parent 배열에서 인덱스번호 0, 4, 2는 -1입니다. 즉, 대장이라는 의미입니다. S1의 자식 node 6, 7, 8은 0을 가리키므로 parent배열 6, 7, 8은 0입니다. 나머지 tree들도 마찬가지 입니다. 물론 이렇게 union&find를 할 수 있지만 이번시간에는 ,weighted uni..

binary search tree는 우리가 이전에 배운 탐색 알고리즘을 용이하게 하기 위한 자료구조입니다. 각 root node의 왼쪽은 root node보다 작고 오른쪽은 root node보다 큰 수가 들어가게 되면서 어떤 수를 찾을 때 root node와 비교해주어 작으면 왼쪽으로가고 크면 오른쪽으로 가면서 탐색을하게 됩니다. typedef struct node* tree_pointer; typedef struct node { int data; tree_pointer left, right; }node; 다음과 같은 tree 선언을 해줍니다. Search (Recursive) 재귀함수 탐색과정을 재귀적으로 수행하는 방법입니다. tree_pointer search(tree_pointer root, int..

heap 자료구조는 크게 두 가지로 나뉘어 집니다. max heap 과 min heap 이 있습니다. Max heap 루트 노드가 자식 노드보다 큰 경우 입니다. 이러한 heap의 자료구조는 우선 순위 큐(Priority Queue) 에서 사용됩니다. 우선 순위 큐는 일반적인 큐와 달리 우선순위에 해당하는 값이 큐의 맨 앞에 위치하고 삭제할때도 가장 먼저 삭제 됩니다. 우선순위는 사용자에 따라 설정할 수 있는데 (max, min) 등 다양하게 설정 가능합니다. 따라서 뒤에 설명할 예시는 max 우선순위 큐를 heap 자료구조로 구현한 예시 입니다. #define MAX_ELEMENTS 200 #define HEAP_FULL(n) (n==MAX_ELEMENTS-1) #define HEAP_EMPTY(n) ..

순회 알고리즘이란 tree의 각 node를 한번씩 방문하는 알고리즘입니다. typedef struct node* treepointer; //노드를 가리키는 포인터 typedef struct node { //노드생성 int data; treepointer left, right; //노드의 오른쪽,왼쪽을 가리키는 포인터 }node; Inorder 중위 순회 왼쪽 branch(가지)를 모두 방문한 후 node를 방문하고 오른쪽 branch를 방문합니다. 다음 그림에서 보면 중위순회를 하게 되면 output은 A / B * C * D + E가 됩니다. void inorder(treepointer ptr) { //중위 순회 if (ptr) { inorder(ptr->left); //왼쪽 자식 먼저 printf("..

Doubly Linked List는 이중연결리스트 입니다. Singly Linked List가 일방적인 방향으로 연결되었다면 반대로 Doubly Linke List는 양방향으로 연결되어 node의 연결을 용이하게 합니다. Doubly Linked List는 Circular로 구현할 수 있고 아닐 수 도 있습니다. typedef struct node* node_pointer; typedef struct node { node_pointer llink; //왼쪽 포인터 int item; //data node_pointer rlink; //오른쪽 포인터 }; 위의 그림은 Doubly Linked List의 header node입니다. 특징은 왼쪽 부분은 포인터 가운데 부분은 data 오른쪽 부분도 포인터 입니다..

Chain 형태 typedef struct list_node *list_pointer; typedef struct list_node{ char data; list_pointer link; }; Invert (연결 리스트 거꾸로) list_pointer invert(list_pointer lead) { list_pointer middle, trail; middle = NULL; while (lead) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; } return middle; } middle이 맨 앞으로 가고 lead가 NULL이 되면 함수가 종료됩니다. Comcatenate (연결 리스트 연결) list_pointer ..