IT 내맘대로 끄적끄적

[자료구조] B+ tree & B- tree 검색을 위한 이진탐색트리 이진탐색트리는 컴퓨터 트리 자료구조로 각각의 노드가 최대 두 개의 자식 노드를 가집니다. 부모노드를 기준으로 왼쪽서브트리의 노드들은 모두 부모노드보다 작고, 오른쪽 서브 트리의 노드들은 모두 부모노드보다 큽니다. 이러한 특성 덕분에 어떤 수를 탐색할 때 시간복잡도는 트리의 높이가 h라고 했을 때, O(h)가 됩니다. 이진탐색 트리가 다음과 같이 경사 이진 트리 형태이면, 높이가 n이므로 O(n)의 시간복잡도를 가져서 비효율적입니다. 이러한 문제점을 해결하기 위해 Balance tree가 등장했습니다. Balance tree는 노드가 삽일될 때마다 자동으로 균형을 맞춰주는 트리입니다. B- tree, B+ -tree, B* -tree는 Balance tree중 하나로 이진 트리와 다르게 노드가 2개이상의 자식을 가질 수 있습니다. 주로 데이터베이스의 인덱스가 B- tree 구조입니다. B- tree M차 b- tree는 한 노드에 들어갈 수 있는 최대 키의 개수가 M개입니다. M차 b-tree의 특성은 다음과 같습니다. 한 노드의 키가 N개라면, 그 노드의 자식의 갯수는 반드시 N+1이어야 한다. 따라서 tree의 max degree는 M+1) root node가 leaf node인경우를 제외하고 항상 최소 2개의 자식을 가진다. root node를 제외한 모든 노드는 적어도 l M/2 l 개의 키를 가지고 있어야 한다. 모든 leaf node들은 같은 level에 있어야 한다. node내의 key값들은 오름차순이다. (중복된 키 허용 x) node의 자료 Dk 왼쪽 서브트리는 Dk보다 작은 값들이고, 오른쪽 서브트리는 Dk보다 큰 값들이다. B+ -tree B+ -tree는 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색, 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료입니다. 주...

[자료구조] 메모리 구조(스택(Stack), 힙(Heap), 데이터(Data) 영역) C언어의 메모리 구조 프로그램을 실행시키면 운영체제 는 우리가 실행시킨 프로그램을 위해 메모리 공간을 할당 해준다. 할당되는 메모리 공간은 크게 스택(Stack), 힙(Heap), 데이터(Data)영역으로 나뉘어진다. 이러한 메모리 공간이 어떠한 용도에 언제, 어디서 할당되는지 알아보도록 하자 할당 시기 : 프로그램이 실행될 때마다 할당 장소 : 메인 메모리(RAM) 할당 용도 : 프로그램 실행 시 필요한 메모리 공간(지역변수, 전역변수 선언을 위해) 할당 데이터(Data) 영역 전역 변수와 static 변수가 할당되는 영역 프로그램의 시작과 동시에 할당되고, 프로그램이 종료되어야 메모리에서 소멸 됨 위와 같은 코드에서 int형 변수 a,b는 프로그램 실행시, main 함수가 호출되기 전에 데이터 영역에 할당된다. 그렇기 때문에 프로그램이 종료될 때까지 메모리 상에 존재한다. (전역변수가 프로그램이 종료될 때까지 존재하는 이유) 스택(Stack) 영역 함수 호출 시 생성 되는 지역 변수와 매개 변수 가 저장되는 영역 함수 호출이 완료되면 사라짐 스택 영역은 그 이름 그대로 스택의 성질을 띄고 있다. 힙(Heap) 영역 필요에 의해 동적으로 메모리를 할당 할 때 사용 지금까지 데이터영역과 스택영역을 알아보았는데, 저 두가지 영역만 있으면 코드를 문제없이 짤 수 있을것처럼 보인다. 그럼 힙 영역은 왜 필요한 것일까? 제일 첫번 째 그림을 보면 힙 영역은 프로그래머가 할당한다고 되어있다. 그럼 언제 할당을 할까? 배열을 예를 들어서 설명을 하겠다. 우리는 배열을 선언할 때 상수로 선언을 한다. 배열의 길이를 사용자가 입력한 숫자로 잡아주는 것은 비 정상적인 배열선언이다. 왜 비정상적일까? 메모리 구조에 대해서 잘 파악하고 있다면...

[자료구조] 그래프 탐색 그래프 탐색 그래프의 모든 정점을 방문하는 것을 그래프 탐색이라고 한다. 그래프 구조의 자료를 검색하고, 저장하고, 연산하는데 필요한 기본 알고리즘을 제공한다. 그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있다. 너비 우선 탐색(BFS : Breath First Search) 서울에서 부산까지 가는 길에 모든 도시를 하나도 빠짐없이 차례로 방문하는 방법이다. 큐 깊이 우선 탐색(DFS : Depth First Search) 서울에서 부산까지 가는 길에 방문할 수 있는 도시는 우선 방문하되 같은 지역에 있는 도시가 있다면 그 중 하나만 방문하고 간다. 되돌아오는 길에 나머지 도시들을 차례로 방문하는 방법이다. 스택 출처 https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

[자료 구조] 트리(Tree)란? 트리(Tree)의 개념 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(Node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(Cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수도 있고, 아닐수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다. 각 노드는 어떤 자료형으로도 표현 가능하다. 비선형 자료구조로 계층적 관계를 표현함  비선형 자료 구조 : 원소들을 순차적으로 나열하지 않은 것 ex) 디렉토리 구조, 조직도 그래프의 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 트리(Tree)와 관련된 용어 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐 단말 노드(leaf node) : 자식이 없는 노드, '말단 노드' or '잎 노드'라고도 부름 터미널 노드라고도 부름 내부(internal node) : 단말 노드가 아닌 노드 간선(edge) : 노드를 연결하는 선 (link, branch라고도 부름) 형제(sibling) : 같은 부모를 가지는 노드 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 Level0, Level1, Level2, Level3등등 그래프와 트리의 차이 출처 https://gmlwjd9...

[자료구조] 메시지 큐(Message Queue) 스택, 큐, 덱 관련 자료구조를 정리하다가 메시지 큐도 궁금해서 정리하게 됨 메시지 큐 : 윈도우를 생성하거나 키보드를 누르거나 마우스를 움직일 때 생성되는 메시지가 쌓이는 메모리 공간 시스템 메시지 큐 : 사용자 입력 값들이 차곡차곡 쌓이게 되고 OS가 판단해서 활성화된 원도우에 사용자 입력 값들을 전달하게 됨 쓰레드 메시지 큐 : 사용자가 직접 접근하는 공간 으로서 GetMessage, DispatchMessage함수 등에 의해서 접근 가능 먼저 키보드를 누르면 WM_KEYDOWN이라는 메시지가 생기고 OS 내부에 어떤 곳(메시지 큐) 에 이 메시지가 쌓임 GetMessage함수가 이 메시지를 가져옴 만약에 문자 키라면 TranslateMessage 함수가 WM_CHAR 메시지를 발생시키고 DispatchMessage함수에 의해서 윈도우 프로시저로 전달 하지만 모든 메시지가 큐에 저장되는건 아님 메시지가 발생되자마자 메시지 큐에 쌓이지 않고 바로 윈도우 프로시저로 가는 메시지가 있는데, 이 메시지를 비큐(Non Queued) 메시지라고함 프로세스에 적어도 한 개 이상의 스레드가 생성이 되는데, 이때 쓰레드에서 윈도우를 만들지 않으면 메시지 큐 또한 생기지 않게 되어서 메시지를 받을 수 없음 출처 https://m.blog.naver.com/PostView.nhn?blogId=kater102&logNo=122545087&proxyReferer=https%3A%2F%2Fwww.google.com%2F

[자료구조] 스택, 큐, 덱 자료구조에는 스택(stack), 큐(Queue), 덱(Deque)등이 있다. 메모리의 영역을 어떻게 처리하느냐의 기준으로 나눔 스택(Stack) 먼저 들어간 자료가 나중에 나옴 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 LIFO(Last In First Out) 구조 깊이 우선 탐색(DFS)에서 사용한다. 재귀적(Recursion) 함수를 호출 할 때 사용한다. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임 큐(Queue) 위의 자료 구조가 큐 스택과 반대로 먼저 들어간 자료가 먼저 나오는 구조 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 가장 먼저 큐에 들어온 첫번째 원소 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함 큐에 가장 늦게 들어온 마지막 원소 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴 일반적인 큐의 단점 큐에 빈 메모리가 남아 있어도 꽉 차있는것으로 판단할 수 있음(rear가 배열의 끝에 도달했을 경우) -> 개선된 원형 큐가 나옴 원형큐의 단점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점 -> 개선된 Linked list queue가 나옴 큐의 크기가 제한이 없고 삽입, 삭제가 편리함 덱(deque) D ouble E nded Q ueue 자료의 입력과 출력을 양 쪽 끝에서 가능하게 해서 스텍과 큐에 비해여 자유도가 높은  자료구조 스 크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱 셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱 그러나 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다. 보통 두가지 이유중 하나로...