OS services to User - ui : cli, gui와 같이 user interface를 제공한다. - user program execution : 프로그램을 load해서 memory에 넣고 실행한다. 끝나면 종료한다. - i/o operations : 입출력을 운영한다. - file systems manipulation : 디스크를 관리하는 역할 - communication : 프로세스가 정보를 변경하면, 네트워크를 통해 컴퓨터 사이에 정보를 주고받는다. - error detection : 말 그대로 에러를 감지한다. OS Services for resource management - resource : 하드웨어 - cpu, 메모리(시간적인 개념 - cpu로 1초에 끝나는, 10초에 끝나는)..

1. 운영체제란? operating system : operating(운영하다, 뭔가를 managing하다) + system(범위 내에서 구성워들 사이에 관계, 역할들을 규정지어 놓은 체계) => 뭔가(컴퓨터)를 운영하기 위해 고안된 시스템 운영체제는 모든 것이 코드로 되어 있는 100% software이다. ex) windows, android, ios. windows를 제외한 대부분 운영체제는 unix에서 파생되었다. 운영체제의 구조는 아래와 같다. user/developers-application-os-devices os는 전자장치가 있는 모든 디바이스에 필요하다. 하지만 못 올려서, 올라가지 못 할 수도 있다. 다시 말해 os는 효율성을 위한 프로그램으로, 하드웨어를 제어[관리, 운영]하는 프로그..

Prim 알고리즘 Prim('프림') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Prim 알고리즘은 트리를 점점 확장시켜 최소 비용 신장트릴 만드는 방법이다. Krusal 알고리즘은 처음부터 모든 노드를 추가하고 시작했지만 prim 알고리즘의 시작노드는 1개이다. 또한 krusal 알고리즘은 모든 간선중 최소비용을 가지는 간선을 우선으로 고려했다면 prim 알고리즘은 현재 신장트리가 포함중인 노드에 부속된 간선들 중에서 최소 비용을 가지는 간선을 우선으로 고려한다는 차이점이 있다. 아래 표를 통해 자세히 알아보자 초기화 그래프 G에서의 임의의 시작 노드 r을 선택하여, 신장 트리 H를 초기화 V(H) = r E(H) = 0 (공집합) 루프 Step-1 V(H)와 부속된 간선들 중에서 (..

Kruskal 알고리즘 Kruskal('크루스칼') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Kruskal 알고리즘은 그래프의 모든 간선을 비용 순으로 정렬한 다음, 낮은 비용을 가지는 간선을 차례대로 선택하여 신장 트리를 완성해 가는 방법이다. 아래 표를 통해 자세히 알아보자 초기화 (1) 그래프 G의 최 소 비용 신장 트리 H를 다음과 같이 초기화한다. H= (V(G),E(H)) 단, (E(H))= 0 (공집합) (2) 그래프 G의 모든 간선을 가중치 값에 따라 오름차순으로 정렬한다. 루프 Step-1 정렬된 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환을 발생시키지 않는 간선 e를 추출 Step-2 그래프 G의 모든 노드가 연결될 때까지 step-1 을 반복한다. 가장..

신장 트리(Spanning Tree)의 개념 앞서 그래프에 대한 내용을 다루었다. 내용을 살펴보면 그래프 G는 노드 V와 간선 E의 집합으로 정의된다는 것을 알 수 있다. 다시 정리하자면 그래프는 노드와 노드들을 연결하는 간선들의 집합으로 구성되어있고 그래프의 정의를 식으로 나타내면 G=(V,G)이다. 이번에 다룰 내용은 일반적인 그래프 G에 대한 신장 트리(Spanning Tree)에 관한 것이다. 여기서 ‘신장(spanning)’은 모든 노드를 포함한다는 뜻이다. 만약 노드가 5개인 그래프 G에 대해 신장트리를 만든다고 한다면 신장트리는 반드시 저 5개 노드를 포함하고 있어야 한다. 하지만 신장 트리도 엄연히 트리의 일종이기 때문에 그래프와 다른 트리의 특징인 순환 구조를 가지면 안된다. 정리하자면 ..

넓이-우선 탐색 넓이 우선 탐색은 현재 방문한 노드 이전 노드에 인접한 노드를 우선적으로 방문하는 탐색 알고리즘이다. 큐로 구현하는 넓이-우선 탐색 넓이 우선 탐색은 이전 노드를 기록을 가지고 있어야 하기 때문에 재귀적으로 동작하지 않는다. 우리는 넓이 우선 탐색을 구현하기 위해서 큐의 '선입선출' 특성을 이용할 것이다. 우리는 방문한 노드와 인접한 노드들을 큐에 추가할 것이고 큐는 '선입선출' 특성을 가지기 때문에 현재 노드와 인접한 노드보다 이전 노드와 인접한 노드들을 먼저 반환할 것이다. 아래는 큐를 이용한 BFS의 의사 코드이다. BFS(node v){ 큐 Q v (방문 처리); Q.enqueue(V) while(! is_Empty(Q)) u=Q.dequeue() for( all w (u의 인접 ..

그래프 탐색(Search 혹은 Traversal) 그래프의 탐색은 간선을 이용하여 그래프 상의 모든 노드를 한 번씩 방문하는 것을 말한다. 예를 들어 한 도시를 기점으로 모든 도시를 방문하고자 한다면 우리는 어떤 순서로 방문해야 모든 도시를 방문할 수 있을까? 이를 해결하기 위한 그패트의 탐색 방법으로 가장 대표적이고 기초적인 2가지 방법이 있다. 1) 깊이-우선 탐색(DFS: Depth-First Search) 2) 넓이-우선 탐색(BFS: Breadth-First Search) 깊이 우선 탐색은 현재 방문한 노드와 인접한 노드를 우선이 하는 탐색 방법이고 넓이 우선 탐색은 현재 방문한 노드보다 우선적으로 이전 노드에서 방문하지 않고 인접한 노드를 우선 탐색한다. 아래 그림을 통해 간단히 설명해보자. ..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 인접행렬을 이용한 그래프 구현 그래프 G의 각 도드 사이의 간선을 2차원 배열로 저장하는 것이다. 각 노드 사이에 간선이 존재할 경우 해당 배열의 값을 1로 없을때는 0으로 저장한다. 여기서 무방향 그래프라면 반대로 똑같이 1로 저장해주면 된다. 무방향 그래프의 이러한 성질을 대칭성(symmetry)라고 한다. 참고로 인접 행렬에서 각 노드의 차수를 구하고 싶다면 인접 행렬의 각 행 또..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 그래프 관련 용어들 그래프를 실제 규현하고 그래프 기반의 다양한 알고리즘을 살펴보기 전에 그래프와 관련된 용어들을 알아보자. 인접(Adjacent) 두 개의 노드를 연결하는 간선이 존재하는 경우 두 노드는 인접(Adjacent)되었다고 한다. 다음 그림을 통해 자세히 살펴보자. 부속(Incident) 두 개의 노드를 연결하는 간선이 존재하는 경우 이 간선은 두 노드에 각각 부속(Inci..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 이전 글에서 표로 정리한 그래프 종류에 대해 자세히 알아보자 구분 종류 설명 간선의 방향성 무방향 그래프 간선에 방향이 없는 그래프 방향 그래프 간선에 방향이 있는 그래프 간선의 가중치 가중 그래프 간선에 가중치가 할당된 그래프 구조적 특징 완전 그래프 연결가능한 최대 간선 수를 가진 그래프 부분 그래프 원래의 그래프에서 일분의 노드나 간선을 제외하여 만든 그래프 다중 그래프 중복된 간..