CS

[C#] 힙 (Heap)

1. 힙이란? : 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림) * 힙의 특징 - 중복 값을 허용 - 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문) - 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터) 2. 이진 탐색 트리와 힙의 차이 * 공통점 : 둘 다 이진 트리. * 차이점 - 힙은 이진 탐색 트리와 달리 중복 값을 허용. - 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음. - 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조..

메모리 (RAM) 구조

RAM과 ROM RAM은 자유롭게 읽고 쓸 수 있는 기억장치로, RWM(Read Write Memory)라고 부르기도 한다. 또한 RAM에는 현재 사용 중인 프로그램이나 데이터가 저장되어 있다. 시스템의 전원이 꺼지면 기억된 내용이 모두 사라지는 휘발성 메모리의 특징을 가진다. 일반적으로 주기억장치 또는 메모리라고 불린다. ROM은 기억된 내용을 읽을 수만 있는 기억장치로서 일반적으로 쓰기가 불가능하다. 또한 시스템의 전원이 꺼져도 기억된 내용이 지워지지 않는 비휘발성 메모리다. 실제로 ROM은 주기억장치로 사용되기보단 주로 변경 가능성이 없는 시스템 소프트웨어를 기억시키는데 이용된다. (ex. 기본 입출력 시스템, 자가 진단 시스템) 프로그램 실행 순서 프로그램이 실행되는 과정을 도식화하면 다음과 같다..

Virtual Memory - 가상 메모리 ( 필요한 이유 )

간단하게 말해서 프로세스의 논리 메모리와 물리 메모리를 분리하기 위해 생긴 개념이다. 왜 분리를 해야 하냐면, 물리 메모리의 한계를 극복하기 위해서이다. 무슨 말이냐면 여러 프로그램을 돌리면 메모리 부족의 문제가 생긴다. 이는 메모리 침범의 문제로 이어지기 때문에 이를 해결하고자 한 방법이다. 이런 이유 때문에 가상 메모리와 물리 메모리를 분리한다는 의미다. 논리 메모리가 가상 메모리다. 왜 가상 주소가 필요한지 예를 들어보자, 3개의 프로그램을 일정 시간에 따라 반복적(time에 따라)으로 돌리고 메인 메모리의 크기는 64KB라고 가정해보자. 그러면 먼저 taks1 (32KB), task2(16KB), task3(48KB)의 정보는 Hard disk에 다 들어있을 것이다. 그러다가 task1이 실행되면..

Memory Allocation (논리 메모리, 물리 메모리, Dynamic Loading, Paging이 나온 이유 )

memory를 나눌 때 어떻게 눌지 정해야 한다. 모든 프로세스는 메모리에 올라와서 실행되는데 각각의 프로세스는 자신만의 할당 메모리가 있다. 이때 하나의 프로세스가 다른 프로세스 메모리에 침범하면 문제가 생긴다. 이런 이유 때문에 메모리의 구분이 필수적이다. 예방하는 방법으로 가장 단순하게는 시작 주소와 끝 주소를 지정하는 것이다. base 주소로부터 limit 주소를 하나의 프로세스에게 할당한다. (+아래서 보이지만, 운영체제 또한 메모리 상에 존재한다.) 어떤 프로세스를 할당할 때, base 주소보다 크고 base + limit 주소보다 작은 공간이 비어 있다면 할당하는 순서를 가질 수 있다. 메모리 주소 메모리에는 Logical address와 Physical address가 존재한다. 이 차이를..

Swapping 스와핑 ( page in, page out )

여러 프로그램을 메모리상에서 돌리다 보면 메모리가 부족할 수밖에 없다. 이런 메모리 부족을 해결하기 위해서 나온 방법이 Swapping이다. 더 많은 프로세스가 메모리에 존재할 수 있도록 하는 것이다. swapping을 사용하면 프로세스를 다시 실행할 때 처음부터 메모리에 올리는 것이 아니라 더 빨리 할 수 있기 때문이다. Swapped은 backing store를 만들어서 프로세스 단위로 swap in, swap out을 동작한다. ( backing store는 임시저장소로 하드디스크나 NVM처럼 여러 하드웨어가 될 수 있다. 즉 Secondary Storage다.) 프로그램이 실행되면 Bakcing store에 있는 필요한 page 정보를 메모리에 올린다. 이렇게 프로세스 단위로 왔다 갔다 하는 걸,..

모듈 Module

1. 일반적으로, 모듈이란? 보다 작고 이해할 수 있는 단위로 나뉘어진 것 본체(本體)에서 분리되어, - 작은 부분으로 유기적으로(기능별로) 구성되어 있다가, - 필요할 때 마다, 본체에 합류하여 그 기능을 수행할 수 있는 것 통상, 그 자체로 하나의 완전한 기능을 수행할 수 있는 독립된 실체로 봄 - 例) 각기 다른 여러 모듈 단위로 조립하여 전체를 완성 (모듈 조립) - 例) 표준화된 부품 (조립식 부품) 2. 문제를 다룰 때 모듈화 하는 이유는? 모듈화는, 거대한 문제를 작은 조각의 문제로 나누어 다루기 쉽도록 하는 과정 - 여기서, 작게 나누어진 각 부분을 모듈이라고 함 각 모듈은 논리적 또는 기능적으로 분리되어 격리되고 독립적인 일을 수행 모듈화 과정의 잇점 - 기본적인 것을 엮어서 복잡한 형상..

컴포넌트 Component

1. 컴포넌트는 독립적인 소프트웨어 모듈이다. 컴포넌트를 한마디로 표현하자면 소프트웨어 시스템에서 독립적인 업무 또는 독립적인 기능을 수행하는 ‘모듈’로서 이후 시스템을 유지보수 하는데 있어 교체 가능한 부품이다. 소프트웨어 컴포넌트는 하드웨어의 그래픽카드와 같은 개념으로 독립적인 기능을 수행하는 소프트웨어 모듈이라고 설명할 수 있으며 소프트웨어 컴포넌트는 컴포넌트란 말로 대체되어 사용되고 있다. 2. 컴포넌트는 구현, 명세화, 패키지화, 그리고 배포 될 수 있어야 한다. 컴포넌트의 정의나 형태는 관점에 따라 다양하게 존재하지만, 재사용 부품으로서의 컴포넌트가 되기 위해서는 아래의 내용을 만족해야만 한다. 소스코드(source code)가 아닌 실행코드(execute code) 기반으로 재사용할 수 있도..

비헤이비어 트리 (Behavior Tree)

1. 비헤이비어 트리 소개 ​​비헤이비어 트리는 게임 AI같은 거를 빠르고 쉽게, 그리고 가독성도 좋고 재활용성도 좋게 만드는데 특화되어있다. FSM, HFSM이 상태가 많아지면 유지보수, 가독성 등을 잃게 되는 단점을 보완했다고 볼 수 있다. (FSM과 BT의 차이를 대략적으로 보여줌) 비헤이비어 트리는 HFSM과 마찬가지로 계층적인 특성을 띄고 있는데, (HFSM이랑 약간 유사한데, BT가 더 조직화 됐다고 보면됨.) 다만 HFSM처럼 각 상태에서 조건을 체크하고, 직접 상태를 이전시키는 것이 아닌, 각 노드는 True, False, (Running) 값을 조건에 따라서 결과값을 반환 하지만, 전이 자체는 다른 노드가 처리한다. FSM의 경우에는 A에서 B로 전이를 하려면, 해당 상태 내부에서 Set..

[C++] 싱글톤 패턴, Singleton Pattern

오직 한 개의 클래스 인스턴스만을 갖도록 보장하고, 이에 대한 전역적인 접근점을 제공합니다. (GoF의 디자인 패턴 181쪽) 오직 한 개의 인스턴스만을 갖도록 보장 인스턴스가 여러 개면 제대로 작동하지 않는 상황이 종종 있다. 외부 시스템과 상호작용하면서 전역 상태를 관리하는 클래스 같은 게 그렇다. ex) 파일 시스템 API 파일 시스템 클래스로 들어온 호출이 이전 작업 전체에 대해서 접근할 수 있어야 한다. 아무 데서나 파일 시스템 클래스 인스턴스를 만들 수 있다면 다른 인스턴스에서 어떤 작업을 진행중인지를 알 수 없다. 이를 싱글턴으로 만들면 클래스가 인스턴스를 하나만 가지도록 컴파일 단계에서 강제할 수 있다. 전역적인 접근점을 제공 로깅, 콘텐츠 로딩, 게임 저장 등 여러 내부 시스템에서 파일 ..

C++ 프림(Prim) 알고리즘으로 MST 찾기

1. 프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘이다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것이다. 하늘색으로 표시한 경로가 최소신장트리이다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적이다. 2. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요하다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한다. (보통 Min Heap을 이용해서 구현한다.) 가장 먼저, 그래프에서 아무 노드나 선택하므로 가장 번호가 ..