분류 전체보기

프로세스 메모리 구조와 스택 프레임 구조

프로세스 메모리 구조 프로세스의 메모리 구조는 Text, Data, Heap, Stack 영역으로 구분되어 있다. 프로세스 메모리 구조 Text 영역 : 프로그램 코드와 상수가 정의되어 있고, 읽기만 가능한 메모리 영역이기 때문에 데이터를 저장하려고 하면 분할 충돌을 일으켜 프로세스가 중지된다. Data 영역 : 전역 변수(Global variable)와 정적 변수(Static variable)가 저장되어 있는 영역이다. Heap 영역 : 프로그래머의 필요에 따라 동적 메모리 호출에 의해 할당되는 메모리 영역이다. c언어의 기준으로 malloc() 함수나 calloc() 함수에 의해 생성된 변수들이 이 곳에 할당된다. Stack 영역 : 함수 인자 값, 함수 내의 지역 변수, 함수의 반환 주소 등이 저장..

운영체제 프로세스 스레드 메모리 구조

프로그램(Program) 어떤 작업을 위해 실행할 수 있는 파일로 정의할 수 있다. 프로세스(Process) 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램 또는 메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적 개체) 즉, 운영체제로 부터 시스템 자원을 할당받는 작업의 단위이며 실행된 프로그램을 의미한다. 할당 시스템 자원 CPU시간, 운영시 필요한 주소공간 Code, Data, Stack, Heap의 구조로 되어있는 독립된 메모리 영역 프로세스 메모리 영역 프로세스는 각각 도립된 메모리 영역(Code, Data, Stack, Heap)구조를 할당받게 되며 프로세스당 최소 1개의 메인스레드를 가지고 있다. 각 프로세스는 별도의 주소 공간에서 실행되며, 한 프로세스는 다른 프로세스의 변수나 자..

해시 테이블

해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시 함수(Hash Function)을 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Function) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)으로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되는 대표적인 해시 알고리즘에는 ..

레드-블랙 트리(Red-Black Tree)

레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 빨간색 노드의 자식은 검은색이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다) 5. 모든 리프 노드에서 Black Depth는 같다. == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 레드-블랙 트리 삽입 과정 위 설명만 보고는 레드-블랙 트리가 무엇인지 감이 쉽게 오지 않을 것이다. 레드-블랙 트리를 쉽..

[C] 이진 탐색 트리

이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이진 탐색 트리 탐색(Search) 이진 탐색 트리의 탐색은 다음과..

트리

트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 갖는다. 1. 트리는 하나의 루트 노드를 갖는다. 2. 루트 노드는 0개 이상의 자식 노드를 갖는다. 3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다. 트리의 노드는 s..

[SQL] 중첩 트리거 (Nested Trigger)

USE triggerDB;CREATE TABLE orderTBL -- 구매 테이블 ( orderNo INT AUTO_INCREMENT PRIMARY KEY, -- 구매 일련번호 userID VARCHAR(5), -- 구매한 회원 아이디 prodName VARCHAR(5), -- 구매한 물건 orderamount INT -- 구매한 개수 );CREATE TABLE prodTBL -- 물품 테이블 ( prodName VARCHAR(5), -- 물건 이름 account INT -- 남은 물건 수량 );CREA..

[SQL] 트리거

drop trigger if exists back_usertbl_update_trg; delimiter //create trigger back_usertbl_update_trgafter update on usertbl for each rowbegin insert into backup_userTBL values(old.userid,old.username, old.birthyear,old.addr,old.mobile,old.height,old.joindate, '수정',curdate(),current_use..

트리 구현

#include #include #include // 트리 구조체 typedef struct treeNode { int data; treeNode* left; // 왼쪽 노드에 대한 포인터 treeNode* right; // 오른쪽 노드에 대한 포인터 }; // 트리 객체 초기화 treeNode* makeRootNode(int data, treeNode* leftNode, treeNode* rightNode) { treeNode* root = (treeNode*)malloc(sizeof(treeNode)); root->data = data; // data 초기화 root->left = leftNode; // 왼쪽 링크 초기화 root->right = rightNode; // 오른쪽 링크 초기화 retur..

[C] 인접 행렬로 그래프 구현

// 인접 행렬 // 그래프를 인접행렬로 표현하기 #include #include #define MAX_VERTEX 30 typedef struct graphType { int n; // 정점개수 int adjMatrix_Arr[MAX_VERTEX][MAX_VERTEX]; }graphType; // 공백. 그래프를 생성하는 연산 void CreateGraph(graphType* ptr) { ptr->n = 0; // 정점 개수를 0으로 초기화 for (int i = 0; i adjMatrix_Arr[i][j] = 0; } } } // 그래프에 정점 n을 삽입하는 연산 void InsertV..