tose33

최소 스패닝 트리, 크루스칼 알고리즘에 대한 설명은 이미 쓴 글이 있으니 이로 대체한다. https://tose33.tistory.com/485 최소 신장 트리(MST), 크루스칼 알고리즘 (kruskal) 학교에서 배웠었는데 알고리즘 문제에 필요해서 다시 한번 정리. Union-Find 알고리즘 : (https://tose33.tistory.com/614) - 크루스칼 알고리즘 최소의 비용으로 모든 노드를 연결하는 알고리즘 - 신장 트리 tose33.tistory.com 크루스칼 알고리즘의 흐름은 다음과 같다 가중치를 기준으로 간선을 오름차순 정렬한다 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다 사이클을 형성하는 간선은 추가하지 않는다 간선의 갯수가 정점의 수보다 1개 적을때 MST는 완성..

인접 리스트 기반의 무방향 그래프 구현 연결리스트는 구현된것 사용. (DLinkedList.h, DLinkedList.c) ALGraph.h /* * 인접 리스트 기반의 무방향 그래프 구현 */ #ifndef CHAP14_ALGRAPH_ALGRAPH_H #define CHAP14_ALGRAPH_ALGRAPH_H #include "DLinkedList.h" // 연결 리스트 사용 // 정점의 이름 상수화 enum {A, B, C, D, E, F, G, H, I, J}; typedef struct _val { int numV; int numE; List *adjList; } ALGraph; // 정점갯수 nv개의 그래프 생성 void GraphInit(ALGraph *pg, int nv); void Grap..

테이블 - 테이블에 저장되는 데이터는 키(key)와 값(value)가 한 쌍을 이룬다 - 키가 존재 하지 않는 값은 저장할수 없다. - 모든 키는 중복되지 않는다. - 키를 이용해서, 데이터를 '단번에' 찾아야 한다. 다음과 같은 사원 정보에 대한 구조체가 있다고 하자. typedef struct _empInfo { int empNum; int age; } EmpInfo; empNum을 인덱스의 값으로해서 그 위치에 age 값을 저장하면, empNum의 인덱스 값을 기반으로 해당 사원의 age값을 바로 찾을수 있다. 예를들어 사원번호 100번인 사원의 나이는 EmpInfo[100] 으로 바로 찾을수 있을 것이다. 하지만 이런식으로 테이블을 만든다면 사원의 고유번호 empNum의 범위 만큼의 크기의 배열이..

이진 탐색 트리의 단점 앞서 공부했던 이진 탐색 트리는 (https://tose33.tistory.com/654) 단점이 있다. 이진 탐색 트리의 데이터 탐색의 시간복잡도는 트리의 높이에 해당하기 때문에 데이터가 N개일때 O(logN)인데, 트리의 균형이 맞지 않을수록 O(N)에 가까워 진다. 다음과 같이 1부터 5까지의 숫자를 순서대로 삽입한 이진 탐색 트리를 생각해보자 1 \ 2 \ 3 \ 4 \ 5 위 이진 탐색 트리의 높이는 5로 탐색 시간은 O(N)이 되버린다. 하지만 아래와 같이 3을 먼저 삽입한 후에 순서대로 숫자를 삽입하면 높이는 3이 된다. 3 / \ 1 3 \ \ 2 5 이런 이진 탐색 트리의 단점을 개선한 트리를 균형 잡힌 이진 트리라고 하고 여러 종류가 있는데 다음과 같다 AVL, ..