영벨롭 개발 일지

[ Spanning Tree ] Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리입니다. 그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프, 즉 Spanning Tree라고 합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다. - Spanning Tree 특징 DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리는 모든 정점들이 연결되어 있어야 한다. 신장 트리는 사이클을 포함해서는 안된다. 신장 트리는 n 개의 정점과 (n-1) 개의 간선으로 이루어져 있다. [ MST 최소 신장 트리 ] 최소 신장 트리(MST, mi..

[ 그리디 알고리즘 Greedy algorithm ] 그리디 알고리즘(greedy algorithm)은 매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘으로 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식입니다. 즉, 당장 눈 앞에 보이는 최적의 상황만을 쫓는 가장 단순한 형태의 알고리즘입니다. 때문에 욕심쟁이 또는 탐욕 알고리즘이라고 불리기도 합니다. ★ 그리디 알고리즘을 사용하기 적합한지 판단하는 기준 1. 최적 부분 구조(optimal substructure) 속성 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말합니다. 2. 그리디 선택(greedy choice) 속성 : 주..

[ 분할 정복 ] 분할 정복 (divide-and-conquer) 접근 방법은 주어진 문제의 규모가 클 때 문제를 작은 부분 문제로 나눠서 해결하는 방식입니다. 부분 문제로 나누는 작업을 반복하여 그 해답을 찾고, 다시 그 해답을 합쳐서 처음 문제에 대한 해답을 유도하는 것입니다. 분할 정복 알고리즘의 세 단계 1. 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 부분 문제로 나눕니다. 2. 정복(conquer) : 각 부분 문제에 대한 해답을 구합니다. 3. 결합(combine) : 각 부분 문제의 해답을 결합하여 전체 문제에 대한 해답을 구합니다. 일반적인 정렬 알고리즘(bubble sort, insertion sort, selection sort)은 한 쌍식 비교하여 정렬..

[ 선형 탐색 Linear Search ] 선형 탐색은 배열의 첫 번째 원소부터 차례대로 전체 원소를 방문하면서 해당 원소가 검색하려는 원소와 같은지 확인하는 방법입니다. 이 방법의 장점은 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작한다는 점입니다. 하지만 이 방법은 효율적이지 않으며, 주어진 배열이 정렬되어 있어도 그 점을 전혀 활용하지 못합니다. 선형 탐색 알고리즘의 시간 복잡도는 O(N)입니다. int linear_search(int N, vector arr) { for(int i = 0; i < arr.size(); i++){ if(arr[i] == N) return i; } return -1; } [ 이진 탐색 Binary Search ] 선형 탐색과 달리 이진 탐색은 정렬된 배열에서만 동..

[ 어떻게 하면 CPU를 효율적으로 가상화하고 제어할까? ] OS는 time sharing을 통해 물리적인 CPU를 공유함으로써 각 process에게 가상의 CPU를 제공해야 합니다. 이때 두 가지 문제가 있습니다. 1. Performance: 추가적인 overhead 없이 어떻게 virtualization을 구현해야할까? 2. Control: 어떻게 하면 CPU에 대한 제어를 유지하면서 효율적으로 process를 실행할까? ( CPU 제어 없이는 process가 영원히 실행하여 기계를 장악하거나, 접근해서는 안되는 정보에 접근함 ) [ Direct Execution ] direct execution은 program을 CPU 위에서 직접 실행하여 한 번 수행하면 종료될 때까지 수행하는 방법입니다. 이때 ..

Process API란? Prcess API란 OS가 Application에게 제공하는 interface입니다. 프로세스를 생성, 정지, 종료, 재개와 같은 기능을 제공해주는 것인데요! System call 이라고도 부릅니다. Process API인 fork(), exec(), wait()을 하나씩 살펴보겠습니다. fork() - child process 생성 fork()는 child process를 생성해줍니다. child process는 fork()를 호출한 process 즉 부모 process로부터 분리된 메모리 공간을 할당받으며 부모와 동일한 메모리 contents를 갖습니다. child process는 자신만의 register들과 PC(program counter register)를 갖습니다. ..