💻

트리(Tree) - 트리는 비선형 구조이다. 비선형 구조란 선형구조(예: 큐(Queue), 스택(Stack))과 다르게 데이터가 계층적(혹은 망)으로 구성되어있다. - 컴퓨터의 디렉터리 구조가 트리의 대표적인 예라고 볼 수 있는데, 이렇듯 계층적인 구조를 갖는 것이 트리라 할 수 있다. - 트리 용어 Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드 Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소 Edge : 노드와 노드를 연결하는 연결선 Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드 Sub-Tree : 큰 트리(전체)에 속하는 작은 트리 Level : 트리에서 각 층별로..

너비우선탐색(BFS= Breadth First Search) 는 너비를 우선으로 탐색하는 알고리즘입니다. 기본적으로 큐(Queue)를 이용하여 구현합니다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문 처리를 합니다 . 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 너비 우선 탐색은 큐(Queue)자료구조에 기초한다는 점에서 구현이 간단합니다. 실제로 구현함에 있어 큐 STL을 사용하면 좋으며 탐색을 수행함에 있어서 O(N)시간이 소요됩니다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편입니다. #include #include #define INF 999999999 ..

깊이 우선 탐색(DFS=Depth First Search) 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용합니다. 깊이 우선 탐색은 스택(Stack) 자료구조에 기초합니다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복합니다. #include #include #define MAX_SIZE 1001 typeder struct{ int index; struct Node *next; } Node; Node** a; int n, m, c[MAX_SIZE..

그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구입니다. 그래프는 2가지 방식으로 구현할 수 있습니다. 1) 인접행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식 2) 인접리스트(Adjacency List) : 리스트를 사용하는 방식 무방향 비가중치 그래프와 인접 행렬 - 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 합니다. - 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 합니다. - 무방향 비가중치 그래프가 주어졌을때 연결되어 있는 상황을 인접 행렬로 출력할 수 있습니다. #include int a[1001][1001]; int n,m; int main(void){ scanf("%d %d", &n, &m); //간선의 개수 for..

우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 먼저 나온다는 특징이 있어서 많이 활용되고 있다. 우선순위 큐는 운영체제의 작업스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우선순위 큐의 시간복잡도는 O(NlogN)이다. 일반적인 형태의 큐는 선형적인 형태를 가지고 있지만 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. (완전이진트리와 흡사) 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 최대 힙(Max Heap) 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다. 전체 트리에서 루트 노드가 가장 큰 값을 가진다. 우선순위 큐의 삽입 - 완전 이진 트리를 유지하는 형태로 순차적으로 삽..