자료구조 with C (16) 썸네일형 리스트형 오아시스 재결합 https://www.acmicpc.net/problem/3015 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#define _CRT_SECURE_NO_WARNINGS#include stdio.h> typedef struct { // 키 int height; // 같은 키를 가진 사람 수 int num;}info; info stack[600000] = { 0 };int idx = -1; void push(info value) { stack[++idx] .. 힙 트리 내의 모든 노드가 부모 노드보다 큰 완전 이진 트리 "힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다." 연산은 두 가지 뿐 1. 새 노드 삽입 2. 뿌리 노드를 없애는 최솟값 삭제 깊이 n의 노드는 배열의 2^n - 1 ~ 2^n + 1 - 2 요소에 저장 k번 인덱스에 위치한 노드의 양쪽 자식 노드들이 위치한 인덱스 왼쪽 자식 노드 : 2k + 1 오른쪽 자식 노드 : 2k + 2 부모 노드 : (k - 1) / 2 최소 신장 트리 최소 가중치 신장 트리 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리 1. 각 구성 요소가 서로 연결 되어있어야 함 2. 가중치가 있어야 함 1. 프림 알고리즘 임의의 정점을 최소 신장 트리의 뿌리 노드로 삽입 간선 중에 가장 가중치가 작은 것을 골라 최소 신장트리에 삽입 기존 노드와 사이클을 형성해서는 안됨! 모든 정점을 연결하면 종료 1, 자료구조는 그래프를 이용 2. 그래프에 정점이 N개 존재하면 정점 추가 작업 N회 그 때마다 정점 N회 순회하면서 최소 가중치? NOPE!! 삽입과 삭제가 빠르고 최솟값을 찾는 데 비용도 거의 들지 않는 우선순위 큐를 이용한다 링크드 스택 링크드 리스트 노드 표현 1 2 3 4 5 typedef struct tagNode { int Data; struct tagNode* NextNode; } Node; cs 노드 생성 1 2 3 4 5 6 7 8 9 Node* SLL_CreateNode(int NewData) { Node* NewNode = (Node*)malloc(sizeof(Node)); NewNode->Data = NewData; // 데이터를 저장한다. NewNode->NextNode = NULL; // 다음 노드에 대한 포인터는 NULL로 초기화 한다. return NewNode;// 노드의 주소를 반환한다. } Colored by Color Scripter cs Node*를 써야하는 이유? 자동 메모리에 선언하면 함수가 끝나면 사라져버린다. .. BFS 너비 우선 탐색 꼼꼼하게 좌우를 살피며 다니자 구현을 위해 큐(QUEUE)가 필요 1. 시작 정점을 '방문했음' 표시하고 큐에 삽입 2. 큐로부터 정점을 제거. 제거한 정점의 인접 정점 중 아직 방문하지 않은 곳을 '방문했음' 표시하고 큐에 삽입 3. 큐가 비면 탐색 종료. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 void BFS( Vertex* V, LinkedQueue* Queue ) { Edge* E = NULL; printf("%d ", V->Data); V->Visited = Visited; // 시작 정점을 큐에 삽입 LQ_Enqueue( Queue, LQ_CreateNode( V.. DFS Depth First Search (DFS, 깊이 우선 탐색) 그래프 정렬 알고리즘의 기반이 된다 더 나아갈 길이 보이지 않을 때까지 깊이 들어간다 재귀를 이용 1. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시 2. 이 정점과 이웃 정점 중 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼고 다시 깊이 우선 탐색 3. 더 이상 방문하지 않은 이웃 정점이 없으면 이전 정점으로 돌아가 단계 2 수행 4. 이전 정점으로 돌아가도 더 이상 방문할 이웃 정점이 없다면 모든 정점을 방문했으므로 탐색 종료 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void DFS( Vertex* V ) { Edge* E = NULL; printf("%d ", V->Data).. 그래프 기초 그래프는 정점과 간선으로 이루어진다 정점 사이의 인접 관계를 나타내는 방법에는 인접 행렬과 인접 리스트가 있다 인접 행렬을 이용하면 정점 간의 인접 여부를 빠르게 알 수 있다. BUT! 메모리의 양이 정점의 크기 * N^2만큼 커진다 인접 리스트는 정점 간의 인접 여부를 알기 위해 리스트를 타고 순차 탐색을 해야한다.. BUT! 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리 양이 적다. 한 정점과 연결된 모든 간선을 찾는 시간 O(차수) 結論！프로그램의 목적에 따라 결정하자 인접 리스트 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 typedef struct tagVertex { VElementType Data; i.. 이전 1 2 다음
