Jungeun's Devlog

우선순위큐(priority queue)우선순위큐(default 최대 힙)는 삽입된 요소에 대해 우선순위가 높은 데이터를 먼저 가져오는 형식의 자료구조다. 우선순위큐는 주로 힙 자료구조를 기반으로 구현된다. 힙(heap)힙은 완전이진트리의 일종으로 우선순위큐를 위해 만들어진 자료구조다.최대값/최소값을 빠르게 찾아내도록 만들어졌다.최대힙에서는 최대값, 최소힙에서는 최소값을 O(1)의 시간복잡도로 빠르게 접근할 수 있다.삽입과 삭제 연산은 트리의 높이에 비례하기 때문에 O(log N)의 시간복잡도를 가진다.이진탐색트리에서는 중복된 값을 허용하지 않는 반면 힙 트리에서는 중복된 값을 허용한다.힙은 최대힙과 최소힙 형태로 나뉜다. 최대힙부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전이진트리부모노드의 키..

위상 정렬순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것위상 정렬을 수행하게 되는 예시: 선수과목을 고려한 학습 순서 결정 진입 차수 / 진출 차수진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수진출 차수(Outdegree): 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘큐를 이용한 동작 과정이다.진입차수가 0인 노드를 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.i) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.ii) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다..

OSI 참조 모델국제표준화기구(ISO)는 서로 다른 컴퓨터가 네트워크 구조에 상관없이 통신할 수 있도록 OSI 참조 모델을 만들었다.OSI 참조 모델은 컴퓨터 통신 기능을 계층 구조로 나누어 각 계층마다 표준화된 서비스와 프로토콜을 규정한 모델로, 일종의 통신 규칙 모음이다.네트워크에 필요한 프로토콜 기능들을 7계층으로 나누어 복잡성을 줄이고 계층간의 간섭을 최소화한다.이에 따라 각 계층의 원인을 분석할 수 있어 문제 해결이 쉬워지고, 네트워크 장비의 문제 없이 데이터를 송수신할 수 있게 되었다. OSI 참조 모델의 특징계층 간 상하 구조와 독립성OSI 참조 모델의 7계층은 계층 간 상하 구조를 가진다. 상하 구조를 가진다는 것은 모든 하위 계층이 정상적으로 작동해야 상위 계층이 정상적으로 작동할 수 있..

컴퓨터 네트워크네트워크는 둘 이상의 컴퓨터와 이들을 연결하는 링크의 조합이다.네트워크의 사전적 의미는 '모뎀이나 LAN, 케이블, 무선 매체 등 통신 설비를 갖춘 컴포터로 서로 연결하는 조직이나 체계, 연결망'이다.통신 설비로 두 대 이상의 컴퓨터를 서로 연결하여 자원이나 정보를 공유할 수 있다. 네트워크 구성 요소 1) PC컴퓨터나 서버 등을 말하며, 네트워크를 사이에 두고 다양한 데이터를 송수신한다.2) 네트워크 접속 장치 / 장비통신망 구성에 가장 기본이 되는 하드웨어로, 데이터를 정상적으로 전송하기 위한 장치다. 스위치와 라우터 등이 해당한다. 스위치는 여러 대의 컴퓨터를 네트워크에 연결하기 위해 한 네트워크 안에서의 데이터 전송을 담당하고, 라우터는 여러 네트워크를 구분 짓고 연결하는 장치다.3..

POSIXPOSIX(Portable Operating System Interface)는 이식가능 운영체제 인터페이스의 약자다. 서로 다른 유닉스 운영체제의 공통 API를 정리하여 이식성이 높은 유닉스 응용프로그램을 개발하기 위한 목적으로 IEEE가 책정한 애플리케이션 인터페이스 규격이다.쉽게 말해, 어떤 OS에서 개발한 프로그램을 다른 OS에서도 쉽고 돌아가도록 하는 표준이다.표준 스트림표준 스트림(Standard Stream)은 특정한 프로그래밍 언어 인터페이스뿐만 아니라 유닉스 및 유닉스 계열 운영체제에서 컴퓨터 프로그램과 그 환경(키보드나 모니터와 같은 장치들) 사이에 미리 연결된 입출력 통로를 가리킨다.일반적으로 유닉스에서 동작하는 프로그램은 실행 시, 세 개의 스트림이 자동으로 열린다. 이를 표..

컴퓨터의 주요한 두가지 작업은 연산 작업과 입출력 작업이다. 그중 입출력 작업은 컴퓨터에 연결된 다양한 입출력 하드웨어 장치들과 어떤 식으로 상호작용하는지에 관한 작업이다.마우스, 키보드, 모니터 등 다양한 장치들이 컴퓨터와 잘 동작하게 하려면 둘 사이에 공통된 인터페이스가 존재해야 한다. 컴퓨터와 하드웨어 장치 사이의 공통된 인터페이스 역할을 수행하는 것이 입출력 관리의 핵심이다.입출력 장치의 구성하드웨어 장치는 케이블을 통해 또는 무선으로 신호를 보냄으로써 컴퓨터와 통신한다. 이때 포트를 통해 컴퓨터에 접속하는데, 하드웨어의 또 다른 구성요소는 제어기이다.제어기는 포트나 입출력 장치를 제어하는 전자회로의 집합체이며, 많은 입출력 장치는 제어기를 내장하고 있다. 입출력 장치의 동작1) 폴링 (polli..

어떤 프로그램이든 프로세스가 되기 위해 메모리에 적재되어야 실행 가능하다. 따라서 메모리는 중요한 작업 공간이고, 한정된 메모리를 다중 프로그래밍 환경에서 여러 프로세스가 함께 메모리를 사용하므로 효율적인 관리가 필요하다.메모리 관리는 운영체제를 비롯해 여러 작업을 동시에 처리할 때 메모리를 어떻게 관리하는가에 대한 문제다. 복잡한 메모리 관리는 메모리 관리 시스템(Memory Management System, MMS)이 담당한다.메모리 관리자의 역할메모리 관리는 메모리 관리자가 담당한다. 메모리 관리자는 메모리 관리 유닛(Memory Management Unit)이라는 하드웨어인데 일반적으로 메모리 관리자라고 부른다. 메모리 관리자의 작업은 가져오기, 배치, 재배치이다.각 작업에 정책을 수립하여 그 정..

스레드와 멀티스레드스레드(thread)는 프로세스 내에서 실제로 작업을 수행하는 주체를 의미한다. 모든 프로세스에는 한 개 이상의 스레드가 존재하여 작업을 수행한다. 하나의 프로세스 내에서 두 개 이상의 스레드가 동시에 작업을 수행하는 것을 멀티스레드(multi-thread)라고 한다. 멀티스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유한다.멀티스레드의 동작 방식동시성과 병렬성은 멀티스레드의 동작 방식이다. 동시성 (Concurrency)동시성은 싱글 코어에서 멀티스레드를 동작시키기 위한 방식으로 멀티태스킹을 위해 여러 개의 스레드가 번갈아가면서 실행되는 성질을 말한다. 동시성을 이용한 싱글 코어의 멀티 태스킹은 각 스레드들이 병렬적으로 실행되는 것처럼 보이지만 사실은 조금씩 번갈아가며 실행되..

IPC란?프로세스는 자신에게 할당된 메모리 내의 정보만 접근할 수 있고, 이를 벗어나서 접근할 경우 (C의 경우 segmentation fault) 오류가 발생한다. 이는 안전성을 위해 OS에서 자기 프로세스의 메모리만 접근하도록 강제하는 것이다.프로세스 간 통신(Inter Process Communication, IPC)은 프로세스끼리 서로 데이터를 주고받는 행위 또는 그에 대한 방법을 뜻한다. IPC에는 같은 컴퓨터에 있는 프로세스뿐만 아니라 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와의 통신도 포함된다.IPC 종류1) 공유 메모리 (Shared Memory)를 이용한 통신 말 그대로 메모리의 일정 영역을 공유하는 것이다. 데이터 자체를 공유하도록 지원한다.공유 메모리는 커널에서 관리된다. 프로세..

프로세스란?프로세스는 운영체제에서 하나의 작업 단위이며 태스크(task)라고도 부른다. 프로그램은 일반적으로 하드디스크 같은 저장장치에에 저장되어 있는 정적 상태고, 프로세스는 실행을 위해 메모리에 올라온 동적인 상태다.프로그램에서 프로세스로의 전환프로그램을 메모리의 적당한 위치로 가져올 때 PCB를 생성한다. 프로그램이 프로세스가 되었다는 것은 운영체제로부터 PCB를 받았다는 의미다.프로그램과 프로세스의 관계프로세스 = 프로그램 + PCB프로그램 = 프로세스 - PCB 프로세스 제어 블록 (PCB)프로세스 제어 블록(Process Control Block, PCB)은 프로세스를 실행하는데 필요한 중요한 정보를 보관하는 자료 구조로, TCB(Task Control Block) 라고도 부른다. 모든 프로세..