CS/Data Structure

1. Heap 우선순위가 높은 요소가 먼저 나가는 특징을 가진다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. 2. 힙 추가 요소가 추가 될 때는 트리의 가장 마지막 정점에 위치한다. 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다. 완전 이진 트리의 높이는 log n 이기에 힙의 요소 추가 알고리즘은 O(log n) 시간복잡도를 가진다. class maxHeap { constructor() { this.heap = [null]; } push(value) { // 힙에 가장 끝에 추가 this.heap.push(value); let currentIdx = this.heap.length - 1; let parentIdx = Math.floor(cu..

2021. 8. 10.

CS/Operating System

들어 가기 전에 이 내용은 이전 포스팅인 프로세스란 무엇인가? 를 기반으로 작성된 글입니다. 프로그램과 프로세스의 차이 / PCB / 메모리 모델에 대해서 헷갈리는 내용이 있으시다면, 위 포스팅을 선행으로 보는 것을 권합니다. 멀티 태스킹 우리는 컴퓨터를 할 때 보통 [ 유튜브 켜놓기, 브라우저 검색, vscode 작성 ] 등 여러가지 작업을 동시에 진행합니다. 과연 컴퓨터는 이 작업을 "동시에" 처리 하는 걸까요? 정답을 미리 말씀 드리자면 "아니요" 입니다. 하나의 작업이 CPU를 점유 하고 있는다면, 다른 작업의 개입이 불가능 합니다. 그러므로 작업을 빠르게 순환 시켜주면서 우리가 마치 동시에 작업이 이루어지는 것과 같은 기분을 주는데요. 이 것을 문맥 교환(Context Switching) 이라고..

2021. 8. 10.

CS/Operating System

1. 프로세스 (Process) 프로세스는 실행 중인 프로그램을 일컫는 말입니다. 그렇다면 우리가 일반적으로 말하는 프로그램은 무엇일까요? 쉽게 생각해서 저장 장치에 존재하며 실행 되기를 기다리는 코드와 데이터의 묶음 이라고 생각 해주시면 됩니다. 이러한 프로그램이 실행이 됬을 때 비로소 우리는 프로그램을 프로세스라고 부르게 됩니다. 고로, 프로그램은 수동적(Passvie) / 프로세스는 능동적(Positive) 로 보통 표현이 되죠 :D 2. 프로그램이 프로세스가 되려면? - 실행 ""실행된 프로그램이 프로세스다" 라는 이야기를 나눴습니다. 이 때, 실행 된다는 것이 무엇을 의미 하는걸까요? 여기서 실행이란 프로그램이 메모리에 적재되어 CPU를 할당 받은 상태를 의미합니다. 그렇기에 위에서 언급한 내용..

2021. 8. 10.

CS/Data Structure

배열 ( Array ) 배열은 연속된 메모리에 저장이 되고, 사이즈 변경이 불가능합니다. 단, 자바스크립트에서는 사이즈가 동적으로 변합니다. 자바스크립트의 배열은 해시 테이블로 구현된 객체이므로 인덱스로 접근하는 경우에는 일반 배열보다 속도가 느리지만, 삽입 & 삭제의 경우에는 보다 빠른 성능을 기대 할 수 있다. ( ArrayBuffer를 쓰면 실제 배열과 비슷하게 동작이 가능 ) 연속된 메모리 구조 덕분에, 삽입과 삭제 작업은 선형 시간인 O(n) 만큼 소요 됩니다. 삽입의 경우, 새로운 값 이후의 인덱스들을 모두 뒤로 밀어야 하고, 삭제의 경우, 빈 인덱스로 이후의 값들을 당겨 와야 합니다. 삽입, 삭제는 느리지만 탐색의 경우 인덱스를 통해 O(1) 만에 접근 할 수 있습니다. 하지만, 정렬 되지 ..

2021. 8. 5.

CS/Data Structure

1. 연결 리스트의 특징 메모리가 허용하는한 요소를 제한없이 추가 할 수 있습니다. 배열과 다르게, 메모리가 연속적으로 저장 되어 있지 않기 때문이다. 탐색은 O(n)이 소요됩니다. 인덱스가 존재 하지 않기 때문에, 찾는 대상을 만날 때까지 순회를 해야합니다. 요소를 추가하거나 제거 할 때는 O(1)이 소요됩니다. 단, 요소의 추가와 삭제를 위해서는 장소의 탐색이 발생하기에 이 작업을 최소화 하는 것이 중요합니다. 링크드 리스트의 유형으로는 [Single, Double, Circular] 총 3가지가 존재합니다. 2. 배열과의 차이점 1. 배열과 연결 리스트의 가장 큰 차이점은 메모리에서 발생합니다. 2. 연결 리스트는 산발적, 배열은 연속적으로 이루어져있습니다. ( => 배열은 연속적인 메모리 구조를 ..

2021. 8. 5.

CS/Computer Network

Socket ( = The interface Betwwen the Application & Trans Port Layer ) 다른 컴퓨터 위에서 작동되는 두개의 프로세스가 소통을 하기 위해서는 "반드시" 네트워크를 거쳐서 가야합니다. 하지만, 프로세스가 보내는 메세지는 "Socket" 이라고 하는 API를 거쳐서 보내지고, 받을 수 있습니다. 개발자가 관여 할 수 있는 곳은 Application 계층에 국한이 되고, 네트워크 계층에서 선택 할 수 있는 것을 말해본다면 프로포콜의 종류 정도 고를 수 있습니다. 제가 생각하는 그림은 다음과 같습니다 ! Addressing Processes 우편을 보내기 위해 주소지가 필요한 것 처럼, 하나의 프로세스가 다른 프로세스에게 메세지를 보내려면 주소가 필요합니다. ..

2021. 7. 16.

CS/Data Structure

연결 리스트란 ? 연결리스트는 선형 자료구조로써, 연속적으로 메모리에 존재 하지 않고, 포인터를 통해서 다음 인덱스를 나타냅니다. 연결 리스트의 특징 탐색 및 수정 Linked List는 인덱스가 없어, 처음부터 탐색을 시작 하기 때문에 O(k) 이다. ( = k는 탐색 하는 대상의 위치 ) 예시로 [ 철수, 영희, 민수, 동현 ] 으로 구성된 Linked List에서 동현을 찾는다고 가정해보자. 배열의 경우는 인덱스의 값을 통해 빠르게 접근이 가능하지만, Linked List는 철수 -> 영희 -> 민수 -> 동현을 거쳐야 알 수 있다. 삽입 및 삭제 Linked List의 삽입 삭제는 이전의 next를 제거하고, 이어주는 기능만을 수행하면 되기에 O(1) 이다. 연결 리스트 구현 Node 구현 연결리..

2021. 7. 13.

CS/Computer Network

머릿말 이전 게시물을 통해, 거리벡터 & 링크상태 알고리즘에 대해서 다루었습니다. 이번에는 1) IGP 에서 사용되는 라우팅 프로토콜인 RIP & OSPF 2) EGP 에서 사용되는 BGP 프로토콜까지 알아 보겠습니다. * 라우팅 알고리즘과 프로토콜은 모두 "동적 라우팅" 에 해당됩니다. "수동 라우팅"의 경우 목적지를 관리자가 모두 설정 하기 때문에 별도의 라우팅이 요구 되지 않습니다. 들어가기 전에 인터넷은 각 기관이나 단체가 독립적으로 운영하는 네트워크들이 라우터에 의해 연결된 복잡한 네트워크 입니다. 이 때, 독립적인 네트워크를 AS(Autonomous System) 라고 부릅니다. AS의 범위를 기준으로 프로토콜이 나뉘는데, 오늘 살펴 볼 2가지 알고리즘은 AS 범위 내에 있는 IGP에 해당된다..

2021. 7. 6.