분류 전체보기18 [C/자료구조] MST, 크루스칼(Kruskal), 프림(Prim) 알고리즘 1) MST(Minimum Spanning Tree) 신장 트리(Spanning Tree) 무방향 그래프 G(V,E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 신장 트리(Spanning Tree)라 한다. 그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 사이클을 이루지 않는다는 특징이 있다. MST란 최소 비용 신장 트리(이하 최소 신장 트리)를 뜻하며, 무방향 그래프의 간선들에 가중치가 주어진 경우, 여러 신장 트리 중에 간선들의 가중치 합이 최소인 신장 트리를 말한다. 효율적인 통신 망 설계 등에 이용될 수 있다. 2) 크루스칼(Kruskal) 크루스칼이.. 2022. 12. 21. [App Inventor/Aduino] 오작동 감지기 for 화재감지기 ◎ 연구 주제 - 화재 경보기 오작동에 의한 안전불감증 예방 및 개선을 위한 오작동 감지기 for 화재감지기를 개발 ◎ 연구 배경 - 화재가 났을 때 화재경보가 작동되지 않아 탈출이 지연되어 인명피해로 이어진 사례가 발생 특히 거동이 불편한 분들은 이러한 문제에 더욱 취약함. 또한 소방청은 오작동으로 인한 출동 건수가 많아져 안전불감증에 생기고 금전적인 손실도 약 39억 발생함. 이러한 점에서 화재 경보기 오작동이 단순하다는 것이 아닌 큰 사고으로 다가올 수 있다는 경각심을 가져야 한다 생각하고 오작동 감지기를 개발 및 개선 ◎ 연구 수행 구성 ◎ 연구 수행 내용 1) SW - 앱인벤터 - 아두이노 코드 2) HW 3) 감지기 기능 검사 어플에서 서버로 데이터 값을 전달하여 서버에서 감지기로 값을 보내 .. 2022. 12. 5. [C/자료구조] 최대, 최소 힙(heap) 정렬 구현 힙(heap) 자료구조 - 부모가 되는 노드의 값이 자식 노드보다 크거나 작은 자료구조 - 완전이진트리의 구조를 가짐 - 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 - 방식에 따라 최대 힙(max heap)과 최소 힙(min heap)으로 나뉨 힙(heap)의 구현 - 힙을 저장하는 표준적인 자료구조는 배열 이다. - 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. - 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. · 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다. - 힙에서의 부모 노드와 자식 노드의 관계 · 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 · 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 +.. 2022. 11. 30. [C/자료구조] 연결 리스트 다항식 덧셈 연결 리스트를 이용하여 희소 다항식을 표현 동적 메모리를 이용한 단순 연결 리스트로 표현하였음 한 개의 노드는 data / link 2가지의 값을 가짐 (data는 현재 노드의 값, link는 다음 노드의 주소) 노드의 data는 '계수(coef)'와 '차수(expn)'값을 가짐 이때, 연결 리스트는 '차수' 내림차순 정렬된 형태를 가짐 두 다항식을 더하는 add_poly 함수 구현 두 리스트 list1, list2 를 인자로 받음 두 다항식을 더한 결과 리스트 ListType* new_poly 생성 및 초기화 두 리스트의 감시할 노드를 가르키는 ListNode* h1, *h2 생성, 각 리스트의 head로 초기화 h1 또는 h2 가 하나라도 NULL 값이 아니면 반복 h1이 NULL인 경우, h2 노드.. 2022. 11. 20. 이전 1 2 3 4 5 다음