시냅스

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

프림 알고리즘 Prim algorithm 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중..

크루스칼 알고리즘 Kruskal algorithm 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점 사이 사이클이 발생하지 않으면(DFS) 정점을 연결한다. 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) c언어로 구현 간선 가중치를 최소 값으로 오름차순 정렬 dfs를 통해 사이클을 갖고 있는지 확인 Heap *sorted_heap(LinkedGraph *graph) // 간선의 가중치를 기준으로 최소로 정렬한다. // 여기에선 key가 가중치가 된다. { Heap *temp = createHeap(graph->currentEdgeCount); ListNod..

Spanning Tree (신장 트리) Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히..

대용량 저장장치 구조, Mass-Storage Structure 비휘발성인 보조 저장장치 Secondary Storage system HDD, SSD, NVM, magnetic tapes... 메인메모리에 프로그램을 전부 올릴 수 없기 때문에 사용한다. HDD Scheduling 접근 시간이나 탐색 시간을 최소화한다. 탐색 시간 : 어떤 device의 arm이 head를 움직이는데 특정 cylinder의 특정 sector를 찾는 것 대역폭을 최대화한다. 대역폭 : 전송된 총 바이트 수 / 첫 서비스 요청 시간 - 마지막 전송 완료 시간 (완료시간 - 요청시간) FIFO Scheduling 온대로 받는다. SCAN Scheduling 진행 방향이 맞는 순서로 처리한다. Elevator Algorithm C..

Chapter 10 Virtual Memory 물리 메모리와 논리 메모리를 완전히 분리하여 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다. 가상 메모리를 정의하고 그 이점을 설명한다. 요구 페이징을 사용하여 페이지가 메모리에 적재되는 방법을 설명한다. 페이지 교체 알고리즘에 대해 알아본다. 프로세스의 작업 집합과 프로그램 지역성에 대해 알아본다. 10.1 배경 Background 프로세스 전체가 메모리에 올라와 있다면 항상 메모리에 올라와 있지 않아도 되는 오류 처리 코드, 필요 이상으로 많은 공간을 점유하는 자료구조, 옵션이나 자주 사용되지 않는 기능 등 또한 상주하게 된다. 만일 프로그램을 일부분만 메모리에 올려놓고 실행할 수 있다면, 프로그램은 물리 메모리 크기에 제..

페이징과 스와핑 페이징 Paging 프로세스가 할당되는 물리 메모리를 frame(고정된 크기 block)으로 쪼갬 frame(e.g. 4kb)을 logical memory(e.g. 4kb)와 맞춤 -> page logical memory 와 physical memory를 완전히 분리한다. Os가 Logical 과 Physical을 Mapping 물리주소 공간이 연속적이지 않도록 관리하는 체계 외부 단편화, 관련 압축 필요성 방지 대부분 o/s에서 사용 된다. cpu가 생성하는 논리주소는 Page number(p, 페이지 테이블 인덱스) + Page offset(d, 페이지 내 offset)로 이뤄져 있다. page size는 하드웨어에 따라 다르지만 반드시 2의 거듭제곱 꼴이다. 만약 logical ad..

주메모리의 관리, Main Memory memory에 Load된 program -> process 메모리는 바이트로 이뤄진 주소를 배열로 한다. PC(Programcounter) -> 주소 -> 명령어, 필요하면 더 데이터를 더 가져오거나 내보낼 수도 있다. 기본 하드웨어 Basic HardWare 메모리 CPU는 각 처리 코어에 내장된 레지스터와 메인 메모리에만 접근할 수 있다. 명령어와 데이터들은 CPU가 접근할 수 있는 레지스터와 메인 메모리에 있어야 한다. 캐시 CPU 코어에 내장된 레지스터에는 CPU가 빠르게 접근할 수 있다. 다만 메모리에 접근하는 속도는 상대적으로 느리다. CPU와 메모리 사이에 캐시라는 빠른 속도의 메모리를 추가하여 자주 접근하는 데이터를 캐시에 둠으로써 속도 차이 문제를..

이진 탐색 트리, Binary search tree 이진 탐색 트리는 각 노드에는 값이 있다. 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다. 이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다. 다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다. 이 경우 red black tree를 이용할 수 있다. 아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다. 구현 생성 삽입 개별 node 삭제 Tree 삭제 생성 typedef struct BinSearchTreeNodeType..

힙 Heap 힙은 항상 완전 이진 트리 (위로부터 왼쪽 오른쪽 순서대로 쌓이는 것을 말한다.)의 형태를 지닌다. 부모의 값은 자식의 값보다 크거나(Max heap), 작아야(Min heap) 한다. 따라서 루트노드에는 항상 데이터 중 크거나 작은 값이 저장되어 있기 때문에 최대, 최소값 탐색에 O(1)이 걸린다. 데이터의 삽입과 삭제는 모두 O(log N)이 소요된다. 이러한 특성은 완전 이진 트리이며, 부모노드가 항상 크거나 작다는 확증에 기인한다. Max heap 구현 생성 삽입 root node 반환, Pop Heap 삭제 생성 typedef struct HeapNodeType { int key; } HeapNode; typedef struct HeapType { int maxElementCount..