흔한학생

이전 글에서 그래프에서 cycle이 만들어지지 않으며 모든 정점을 연결하는 MST를 kruskal 알고리즘으로 만들어보았다. 이번에는 그래프에서 시작 정점에서 특정 정점까지 최단거리로 연결하는 길을 찾는 방법을 알아볼 것이며 dijkstra 알고리즘을 이용할 것이다.최단경로 찾기 알고리즘Dijkstra의 최단 경로 알고리즘의 단계는 다음과 같다.집합에서 가장 짧은 경로의 정점 u를 집합에 추가집합에 없는 다른 정점까지의 거리 업데이트u를 거쳐 가는 경로가 더 짧으면 해당 값으로 업데이트이게 가능한 이유는 집합에서 가장 가까운 정점 u를 선택하면, u로 가는 더 가까운 길은 없기 때문이다.C언어 구현 방법그래프 구조체에는 vertex의 수 n과, 정점간 간선의 weight(거리)를 의미하는 2차원 배열 w..

컴퓨터구조 수업에서 RISC-V 기반으로 설명되어 있기에 리스크파이브 기반으로 파이프라이닝에서 발생하는 해저드에 대해 설명해볼 것이다. 우선 해저드 전까지 5-stage pipelining을 알아봤을 것이다. 이는 IF ID EX MEM WB 로 구성되어 있으며 각 단계 사이에는 레지스터가 존재한다. Pipeline Hazards해저드는 structure hazard, data hazard, control hazard 세 가지 종류가 있다. 자세한 것은 아래에서 설명할테지만 우선 structure hazard는 하드웨어의 lag 렉으로 발생한다. 하드웨어 자원이 연산 중 충돌하여 발생한다.data hazard는 data dependency에 의해 발생한다. 명령어가 특정 레지스터를 사용하여 수행할텐데, ..

그래프의 path그래프에는 다양한 path가 있다. 기본적인 path는 vertex에서 서로 다른 vertex로 가는 간선이다. Simple path는 시작과 끝이 같지 않은 모든 vertex와 edge가 한 번씩만 나타나는 path이다. Cycle은 시작 vertex와 끝 vertex가 동일한 simple path를 의미한다.spanning treespanning tree는 ‘신장 트리’라고도 하며 cycle 없이그래프 내의 모든 정점을 포함하는 트리를 의미한다. 때문에 정점이 n개라면 spanning tree는 n-1개의 edge를 가진다.MST vertex를 가장 적은 수의 edge로 연결한 신장 트리를 의미한다.구현방법구현 방법: Kruskal’s MST algorithmvertex의 개수 n가장..

이전 글에서는 matrix 와 연결리스트로 그래프를 구현하는 방법에 대해 알아봤다. C언어 행렬과 연결리스트로 그래프 구현하기matrix로 그래프 구현하기행 정점에서 열 정점(vertext)으로 가는 길(edge)이 있다면 1로, 없다면 0으로 구현하려고 한다.무방향 그래프라면 행렬이 대칭으로 나타날 것이다.그래프는 구조체로 선언하studentstory.tistory.com 이번에는 그래프에서 탐색을 어떻게 C언어로 구현하는지 써보려고 한다.이전 글에서도 말했지만 DFS, BFS는 search이지만 실제로는 travarsal, 즉 순회를 설명할 것이다..깊이 우선 탐색 Depth-firstmatrix로 구현된 그래프에서 깊이 우선으로 탐색하는 방법단순히 그래프를 구현하는 방법은 이전 글에서 작성하였기에 ..

이진탐색트리이진탐색트리 binary search tree 를 구현하기 위한 구조체는 다음과 같다.두 자식노드를 가리킬 수 있도록 left와 right가 있다.typedef struct TreeNode { int key; struct TreeNode *left, *right;} TreeNode;필요한 함수searchnew_nodeinsert_nodemin_value_nodedelete_nodeinorder 탐색함수 설명1) search특정 key 값을 가진 노드를 찾기위한 함수다.TreeNode * search(TreeNode * node, int key){ if (node == NULL) return NULL; if (key == node->key) return node; else if (key key)..

matrix로 그래프 구현하기행 정점에서 열 정점(vertext)으로 가는 길(edge)이 있다면 1로, 없다면 0으로 구현하려고 한다.무방향 그래프라면 행렬이 대칭으로 나타날 것이다.그래프는 구조체로 선언하고 내부에 정점의 개수와 2차원 배열을 멤버 변수로 선언할 것이다.typedef struct GraphType { int n; // 정점의 개수 int adj_mat[MAX_VERTICES][MAX_VERTICES];} GraphType;필요한 함수initinsert_vertexinsert_edgeprint_adj_mat함수 설명1) init// 그래프 초기화 void init(GraphType* g){ int r, c; g->n = 0; for (r = 0; radj_mat[r][c] = 0;}이중..

서비스 서버, 클라이언트 만들기 (service_server.py)서비스 서버의 구조서버 노드 만들기(클래스)init 정의서버를 만드는 함수 self.create_service(만든 서비스 타입, 이름, 실행함수)callback 함수 정의 (response 반환)client 로부터 request 받으면 실행main 함수객체화spin 실행shutdownif 문서비스 서버 만들기구독, 발행 노드를 만들때는 create_subscription, create_publisher를 이용했던 것처럼 이번에는 create_service를 이용한다.multi_spawn이란 이름의 MultiSpawn 데이터 타입의 서비스를 호출?callback 함수에서는 request와 response를 받고from my_first_pa..

서비스 정의 만들기srv 폴더 만들기메시지 패키지 (my_first_package_msgs) 에 srv 폴더 만들기메시지 만들때는 msg 만들었다면 서비스는 srv 폴더를 만듦srv 파일 만들기원하는 .srv 파일을 만듦메시지 msg는 종류가 한 가지 이지만 서비스는 request와 response로 두 가지이기에 구분이 필요함--- 구분자 이용하여 구분을 하는 것임int64 num---float64[] xfloat64[] yfloat64[] thetaCMakeLists.txt 수정이전에 만들었던 msg 파일과 마찬가지로 srv 파일을 알려줌 find_package(rosidl_default_generators REQUIRED)rosidl_generate_interfaces(${PROJECT_NAME} ..