나만의 작은 도서관

최대 / 최소 힙이란?최대 / 최소 힙은 이진 트리(Binary Tree, BST)의 한 종류로, 우선순위가 높은 값에 빠르게 접근하기 위해 고안된 방법이다. 각 노드는 2가지 규칙을 따라야 하며, 규칙은 아래와 같다.조건 #1. 완전 이진 트리여야 한다.조건 #2. 모든 노드의 키 값은 자식 노드의 키 값보다 우선순위가 높거나 같아야한다.  조건 2에서 큰 값이 우선 순위가 높다면 최대 힙, 작은 값이 우선 순위가 높다면 최소 힙이 된다.   최대 / 최소 힙의 특징완전 이진 트리이다. 왼쪽 서브 트리와 오른쪽 서브트리는 서로 관련이 없다. 오로지 부모 노드랑만 관련있다.중복값을 허용한다.완전 이진 트리(Complet Binary Tree)란? 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 ..

이진 검색 트리(Binary Search Tree)란? 이진 검색 트리는 이진 트리(Binary Tree, BST)의 한 종류로, 각 노드가 1가지 규칙을 따르는 자료구조이다. 규칙은 다음과 같다. 왼쪽 서브트리에 있는 모든 값은 부모 노드의 값보다 작으며, 오른쪽 서브트리에 있는 모든 값은 부모 노드의 값보다 크다.  이진 검색 트리의 특징중위 순회 시 오름차순으로 정렬된 결과를 얻을 수 있다.트리의 최솟값은 가장 왼쪽 노드에, 최댓값은 가장 오른쪽 노드에 배치된다.선임자(Predecessor)와 후임자(Succesor) 이진 검색 트리에는 선임자와 후임자라는 개념이 존재한다. 선임자와 후임자는 삭제 작업 시 사용되며, 의미는 아래와 같다.선임자(Predecessor) : 노드에 저장된 값보다 작은 값..

내부 단편화 (Internal Fragmentation) 내부 단편화는 OS가 내부적으로 사용하는 시스템으로 인해, 실제 요청한 메모리보다 더 큰 블록을 할당받아 낭비되는 메모리가 발생하는 것을 말한다. 내부 단편화가 발생하는 경우 고정 크기 메모리 할당운영체제(OS) 또는 메모리 관리자(MMU)가 메모리를 일정한 크기의 블록(ex. 페이지, 슬롯)으로 관리하기 위해, 실제 요청한 크기보다 더 큰 블록을 할당한다.ex. 페이지3.8KB의 메모리 할당을 요청했음에도 페이지 크기가 4KB로 설정되어있어 3.8KB가 아닌 4KB를 할당해준다. => 0.2KB 만큼 내부 단편화 발생메모리 정렬(Alignment)CPU는 특정 크기의 데이터(ex. 4바이트, 8바이트)를 효율적으로 처리하기 위해 주소를 특정 크기..

페이지(Page)란? 가상 메모리 시스템에서는 메모리를 블록으로 나누어 관리한다. 이때 메모리 블록을 고정된 크기로 나누어 관리한다면, 메모리 블록을 "페이지"라고 부른다. (서로 다른 크기로 나누어 관리하면 "세그멘테이션(Segmentation)"이라고 한다.) 물리 메모리의 페이지, 프레임(Frame)페이지 개념은 물리 메모리에도 존재한다. 단어의 혼동을 피하기 위해 물리 메모리에서의 페이지는 프레임(Frame)이라 부른다. (그냥 물리 페이지라 부르기도 한다) 페이지 사용법프로세스는 프레임 단위로 나눠져서 메모리(RAM)에 적재된다. OS는 프로세스가 사용하는 가상 주소 공간을 페이지 단위로 관리하고, 페이지와 프레임을 매핑하여 데이터에 접근할 수 있도록 한다. (일반적으로, 페이지와 프레임은 일대..

개요프로세스의 메모리는 독립적이다. 즉, 다른 프로세스는 프로세스 메모리에 간섭할 수 없다.그럼에도 불구하고, 프로세스는 다른 프로세스가 어떤 메모리 주소를 사용하던지 상관없이 메모리 주소를 사용할 수 있다.예를 들어, 프로세스 A 가 0x1000이라는 주소를 사용하고 있어도, 프로세스 B가 0x1000이라는 주소를 사용해도 전혀 문제없다. 이렇게 각 프로세스가 같은 주소를 사용할 수 있는 이유는 프로세스가 사용하는 주소는 실제 주소가 아닌 "가상 주소"이기 때문이다.   가상 주소란(virtual Address)? 가상 주소는 운영체제(OS)의 "가상 메모리 시스템"에서 사용하는 주소다. 프로세스는 이 가상 주소를 통해 메모리에 접근할 수 있다. 운영체제가 가상 메모리(Virtual Memory) 시스..

프로세스의 메모리 구조 프로세스 메모리는 데이터의 종류에 따라 서로 다른 영역에 저장된다. 메모리 주소가 높은 것부터 순서대로 Stack, Heap, Data Segment, Read-Only Data, Text Segment(또는 Code Segment)로 구분된다. 1. 스택(Stack)스택(stack) 메모리 영역은 함수 호출(function call)과 관련된 데이터(지역 변수, 매개변수 등)를 저장하는 메모리 공간이다. 호출 데이터를 담는 스택이라하여 "콜 스택(call stack)"이라 부른다.// 매개 변수(a, c), 지역 변수(num)등이 스택 메모리 영역에 저장된다.void func1 (int a, char c) { long long num = 10;} 가장 높은 위치의 메모리 영역프..