시냅스

입출력 시스템, I/O System Web, File 수정, Youtube 시청, game 등 컴퓨터는 입출력 작업을 주로 한다. PCI 버스로 모든 Device 와 연결한다. 메모리 맵드 입출력 Memory-mapped I/O 모든 컨트롤러는 레지스터(제어용 또는 데이터용)를 가지고 있고, 레지스터를 프로세서의 주소 공간으로 사상한다. CPU는 물리 메모리에 사상된 장치-제어 레지스터를 읽고 쓸 때 표준 데이터 전송 명령을 사용함으로써 입출력 요청을 수행하게 된다. 입출력 장치 컨트롤러는 보통 4개의 레지스터로 구성되어 있다. 입력 레지스터 : 입력을 얻기 위해 읽기를 수행한다. 출력 레지스터 : 출력하기 위해 쓰기를 수행한다. 상태 레지스터 : 현재 명령이 완료되었는지, 입력 레지스터로부터 한 바이트..

플로이드 알고리즘 Floyd algorithm 모든 지점에서 모든 지점으로의 최단 경로를 모두 구하는 경우 꼭짓점 k를 두고, k를 경유할 경우를 원래의 값과 비교하여 더 짧다면 업데이트 한다. (i,j) > (i,k) + (k,j) 와 같은 꼴이다. 다이나믹 프로그래밍 기술에 의거한다. 구현이 쉽고 간단하지만 O(n^3) 시간복잡도가 높다. 구현 int INF = 99999999; int **arr_init(LinkedGraph *graph) { int **arr = calloc(graph->currentVertexCount, sizeof(int *)); ListNode *temp; for(int i = 0; i currentVertexCount; i++) arr[i] = calloc(..

다익스트라 알고리즘 Dijkstra algorithm 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 방식 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식을 소개 구현 방식 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨 1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정..