CS

교착 상태

교착 상태 교착 상태란 두 개 이상의 프로세스가 서로 가지고 있는 자원을 무작정 기다리려 결국은 아무것도 진행되지 못하는 상태를 뜻합니다. 교착 상태를 해결 하기 위해서는 첫째, 교착 상태가 발생했을 때 상황을 정확히 알아야 하고 둘째, 교착 상태가 발생하는 근본적인 원인을 알아야 합니다. 우선 교착 상태가 발생했을 때 상황을 정확히 알기 위하여 이를 그래프로 표현하는 방법부터 알아보겠습니다. 자원 할당 그래프 자원 할당 그래프는 다음과 같이 4가지 규칙으로 그려집니다. 1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현합니다. 2. 사용할 수 있는 자원의 갯수는 자원 사각형 내에 점으로 표현합니다. 3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면, 자원에서 프로세스를 향해 화살표를 표시합니다...

이진 탐색 트리(BST)에 대하여

이진 탐색 트리란? 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리를 뜻합니다. 이진탐색 트리(Binary Search Tree)는 이진 탐색(Binary Search)와 연결 리스트(Linked list)를 결합한 이진트리입니다. 이진 탐색은 시간복잡도가 O(logN)이지만 정렬된 상태를 유지해야 함으로 삽입이나 삭제가 불가능합니다. 연결 리스트는 삽입이나 삭제시 O(1)의 상수 시간복잡도로 처리 가능하지만, 탐색 시간복잡도가 O(N)입니다. 정리하자면 이 둘의 장점을 챙긴 자료구조가 이진 탐색트리입니다. 이진 탐색 트리의 특징 - 모든 왼쪽 자식의 노드의 값이 부모 노드의 값보다 작습니다. - 모든 오른쪽 자식의 노드의 값이 부모 노드의 값보다 큽니다. - 각 노드들은 서로 유일한 값을 가..

Array와 List의 차이는?

배열(Array)과 리스트(List)는 모두 선형 자료구조입니다. 선형 자료구조란 원소들을 순서대로 나열한 집합을 뜻합니다. 지금 부터 각각에 대해서 특징과 차이가 무엇인지 살펴보도록 하겠습니다! 배열 (Array) 배열이란 같은 성질을 같은 항목들의 집합을 뜻합니다. 아래 그림과 같이 모든 요소들이 정수(int)를 자료형으로 갖고 있는 것을 확인할 수 있습니다. 중간에 문자열이나 다른 성질을 갖는 요소들이 들어올 수 없습니다. 또한 메모리 상에 연속적으로 데이터가 저장됩니다. 순차적으로 저장된 데이터를 참조하는데 Index가 사용됩니다. 이러한 배열에는 몇가지 특징들이 있습니다. 차례대로 살펴보도록 하겠습니다. 배열은 고정된 크기를 같습니다. 배열을 사용하기 전에 크기를 미리 지정을 하고 사용하기 때문..

프로세스 동기화란

동기화 프로세스는 서로 데이터를 주고받으며 협력하며 실행됩니다. 이렇게 협력적으로 실행되는 프로세스들은 일정한 순서에 맞게끔 실행되어야 합니다. 그래서 동기화가 필요합니다. 동기화란 프로세스들 사이에서 수행 시기를 맞추는 것을 의미합니다. 프로세스 간에 수행 시기를 맞추는 것은 크게 2가지를 내포하고 있습니다. 1. 실행 순서 제어 프로세스를 올바른 순서대로 실행하는 것을 의미합니다. 글을 쓰는 프로세스와 글을 읽는 프로세스가 있다고 가정해봅시다. 만약 두 프로세스를 아무 순서대로 실행하게 된다면, 글을 쓰기도 전에 글을 읽는 프로세스가 실행될 것입니다. 글을 읽는 프로세스는 글 안에 값이 존재해야만 읽을 수 있는 특정 조건이 만족되어야 실행을 이어나갈 수 있습니다. 따라서 글을 읽기전에 글을 쓰는 프로..