개발 공부 블로그

N-항 트리를 이용한 파일 시스템 구조

N-항 트리란 무엇인가? 이번 포스팅에서 살펴볼 N-항 트리(N-ary tree)는 각 노드가 N개의 자식을 가질 수 있다.N은 임의의 양수이므로 n개의 자식 노드는 벡터를 이용하여 저장할 수 있다.그러므로 N-항 트리는 다음과 같이 구현할 수 있다. struct nTree{ int data; std::vector children;}; 위 코드에서 각각의 노드는 임의 개수의 자식을 거느릴 수 있다.그러므로 전체 트리도 임의의 형태를 가지게 된다.평범한 이진 트리를 많이 사용하지 않는 것처럼 평범한 N-항 트리도 그다지 유용하지 않다.그러나 응용 프로그램의 요구 사항에 맞는 형태의 트리를 만들어 사용해야 한다. N항 트리의 예시와 컴퓨터 분야에서의 쓰임회사의 조직도와 같은 경우를 N-항 트리..

class SpinLock{public: void Lock() { // CAS (Compare-And-Swap) // 기대값 bool expected = false; // 설계된 값 bool desired = true; // CAS 의사 코드 //if (_locked == expected) { // expected = _locked; // _locked = desired; // return true; //} //else //{ // expected = _locked; // retur..

다음과 같은 join 코드의 내부 코드 보는 법 디버깅 돌려서 HelloThread() 함수에 중단점 찍기 중단점을 찍은 뒤 쓰레드를 주 스레드로 변경하면내부코드 볼 수 있다. 뿐만 아니라스레드 설정을 바꿔가며 다른 스레드들은 뭘 하고 있는지 왔다갔다하며체크할 수 있다. Thread 클래스 5가지 함수 사실 Thread 클래스와 관련된 내용들은 사실 복잡하지 않다.Thread 클래스에서 5가지 핵심 함수를 알면,그 외에는 크게 신경 쓸 일은 없다.int main(){ // HelloThread(); std::thread t(HelloThread); cout std::thread hardware_concurrency(); - CPU 코어 개수멀티 코어 환경에서 실질적으로 구동할 수 있는 코어 개수가..

멀티쓰레드가 필요한 경우는 그림판과 같은 간단한 프로그램의 실행의 이유보다는몇천명이 로그인하여 동시에 접속을 하고,패킷을 보내고 게임 로직도 실행하고데이터비트 저장도 하는 정말 할 일이 많은 이러한 경우가 이유가 될 것이다. 그림판과 같은 단순 프로그램은 단일 스레드가 맡는 것이 되려 적합할 수 있지만,아까 말했던 대규모 접속 게임과 같은 경우에는단일 스레드로만 처리하기에는 하나의 스레드가 너무 많은 일을 담당해야 한다.따라서 멀티 스레드라는 개념이 적합하다. 각각의 여러 개의 스레드가 각 로직을 담당하여 동시에 로직을 실행하는 것이다.그렇다고 해서 스레드를 여러 개 배치했다고 해서 항상 성능이 좋아지는 것은 아니다.앞서 말했다 싶이, 간단한 프로그램과 같은 경우에는오히려 스레드가 놀게 되어 성능이 저하..

보호되어 있는 글입니다.

IPv4 프레임의 데이터 필드에는 상위 계층에서 전달받거나상위 계층으로 전달해야 할 내용이 명시된다.따라서 IPv4 패킷은 프레임의 페이로드로 데이터 필드에 명시된다. IPv4 패킷은 다음과 같은 형식을 띈다. 1. 식별자 2. 플래그 3. 단편화 오프셋 4. TTL 5. 프로토콜 6. 송신지 IP 주소 7. 수신지 IP 주소 총 7개이다. 들어가기 앞서, 패킷이란?패킷(Packet)은 네트워크를 통해 전송되는 데이터의 형식화된 블록으로, 데이터 통신에서 사용되는 용어이다. 1. 식별자 식별자는 패킷에 할당된 번호이다.만일 메시지 전송 과정에서IPv4 패킷이 여러 조각으로 쪼개져서 전송되었다면,수신지에는 이들을 재조합해야 한다. 이때 잘게 쪼개져서 수신지에 도착한 IPv4 패킷들이 어떤 메시지에서쪼개졌..

그래프 구조를 이용해 문제를 해결하기 위해필요한 기본적이고 대표적인 그래프 알고리즘에서BFS,DFS를 빼놓고 논하기는 쉽지 않을 것이다.일단, 그래프 알고리즘을 말하기 전에 그래프에 대해서 말해보자. 그래프란? 그래프는 정점의 집합과 정점들을 서로 잇는 에지의 집합으로 구성된다.수학적으로 표현하면 그래프 G = 형태로 표현하고,여기서 V는 정점의 집합, E는 에지의 집합을 나타낸다. 그래프에는 크게 방향 그래프, 무방향 그래프, 가중 그래프, 비가중 그래프가 있다. 만약 에지가 특정 정점에서 다른 정점으로 향하는 방향있다면 방향 그래프라고 한다.특정 방향을 가리키지 않으면 무방향 그래프라고 한다.에지에 가중치가 있으면 가중 그래프,가중치가 없으면 비가중 그래프라고 한다. (추가적으로 그래프를 다룰 때 ..

DFS 구현 재귀 호출 코드#include #include using namespace std;const int MAX_N = 10;int N, E;int Graph[MAX_N][MAX_N];bool Visited[MAX_N];void dfs(int node) { Visited[node] = true; cout > N >> E; // 배열 초기화 memset(Visited, 0, sizeof(Visited)); memset(Graph, 0, sizeof(Graph)); for (int i = 0; i > u >> v; Graph[u][v] = Graph[v][u] = 1; } dfs(0); return 0;}  스택 코드#include #include #include using namespace st..

으래 컴퓨터를 어려서부터 접한 세대이고,초딩 때 크아나, 바람의 시대 혹은 롤에서 키보드 배틀 좀 떠봤다 싶은 독자들이라면,나보다 나이 좀 많아 보이는 형아들이 너 IP따서 디도스 공격한다.라는 으름장에 맘을 졸여본 적이 있을 것이다.그렇다. 사실 필자의 얘기다. 필자는 막연하게 IP가 뭐냐고 형제에게 물어봤다.필자의 형제는 간단하게 말해서IP란, 인터넷에서 사용하는 가상의 주소라고 답해줬다.우리집에도 주소가 있듯, 컴퓨터에도 주소가 있다는 개념을 그 때 처음 알았다. 초딩 때 나를 발발 떨게했던 IP주소 딴다의 말의IP의 풀네임을 수십년이 흐른 지금에야 알게 되었다.인터넷 프로토콜 (Internet Protocaol)이다. 인터넷 프로토콜 네트워크 계층의 가장 핵심적인 프로토콜 하나를 꼽자면 단연 인터..

비선형 자료구조는 선형 자료구조를 기반으로 만들어진다.비선형 자료구조는 경우에 따라어떠한 선형 자료구조로 구현하느냐에 따라성능과 메모리 공간 차지에 영향을 미친다.따라서 선형 자료구조의 이해는 아주 중요한 기반지식이다.배열은 연속된 메모리 구조를 가지고 크기가 정해져있다.리스트는 노드와 노드로 연결된 메모리 구조를 가지고크기가 가변적이다.배열의 대표적인 stl은 벡터이다.배열은 연속된 메모리 구조를 가지기 때문에,캐시 공간적 지역성을 만족하여 주변 접근이 빠르다.또한 인덱스를 이용한 임의접근이 가능하여,데이터 접근 속도는 O(1)의 속도를 가진다.벡터는 원소 삽입 삭제 시 사이즈를 넘어선 경우,중간에 삽입 삭제가 일어나는 경우삭제되고 재할당 된다.이는 성능에 영향을 끼친다.때문에 속도면에서 리스트에 비해..