전체 글

선 중 후 순회 트리

#include using namespace std; #define SAFE_DELETE(x) if(x != nullptr) delete x; // 트리 구조체 typedef struct s_tree_node { char data; s_tree_node* p_left; // 왼쪽 노드에 대한 포인터 s_tree_node* p_right; // 오른쪽 노드에 대한 포인터 public: // 전위 순회 함수 static void Pre_order(s_tree_node* _p_root_node) { if (_p_root_node) { printf("%3c", _p_root_node->data); Pre_order(_p_root_node->p_left); Pre_order(_p_root_node->p_right..

깊이 우선 탐색 BFS / 너비 우선 탐색 BFS 개념

깊이 우선 탐색 (DFS; Depth First Search) 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘을 의미한다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 하는 것이다. 빠르게 모든 경우의 수를 탐색하고자 할 때 사용한다. 스택 이나 재귀함수 로 구현한다. 너비 우선 탐색 (BFS; Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색 하는 알고리즘이다. 즉, 깊게 (deep) 탐색하기 전에 넓게 (wide) 탐색 하는 것이다. 두 ..

C++ RTTI 그리고 vtable(가상 함수 테이블)

RTTI 란? Run Time Type Information의 약자로 프로그램 실행 중에 개체의 형식이 결정될 수 있도록 하는 메커니즘이다. 다시 말하면 실행중 포인터가 가르키는 객체의 타입을 알 수 있게 해주는 하나의 방법이라고 보면 된다. 기본적으로 RTTI가 필요한 이유는 A 타입에서 B 타입으로 변경할 때 정보가 필요하기 때문이다. 컴파일시간에 타입 변환이 이루어진다면 굳이 RTTI가 필요없다. 컴파일 단계에서 충분히 알 수 있고 특정 타입으로 확정할 수 있기 때문이다. 일반적인 상속 관계에서 발생하는 타입 관계는 대부분 컴파일 시간에 해석되나, virtual 클래스로 상속받는 경우에는 컴파일 시간에 추적이 불가능하다. virtual 클래스로부터 상속이 하나라도 존재하면 RTTI를 사용하고 있다고..

C++ 출력(std::format)과 for-range loop 꿀팁

C++20에서 아주 재미난 기능이 새로 생겼다, 그것은 C#에서도 봤던(String.Format)과 매우 유사한 메커니즘을 가지고 있는 기능이다 헤더파일 을 필히 추가. #include #include #include #include #include #include using namespace std; int main() { map test_map; int size; cout > size; // 맵에 삽입 for (int i = 0; i > tmp_pair.first.first >> tmp_pair.first.second >> tmp_pair.second; test_map.insert(tmp_pair); } cout

C++ RVO NRVO 반환값 최적화 / Copy Elision(복사 생략)

Copy Elision Copy Elision(복사 제거)란 C++11에서 공식화된 기능으로 cppreference의 설명을 참고하면 Omits copy and move constructor, resulting zero-copy pass-by-value semantics 즉 컴파일러가 복사 또는 이동 연산자를 회피 할 수 있으면 회피하는 것을 허용하는 방식 그래서 특정 조건을 만족하면 컴파일러가 임의로 최적화를 위해 복사 및 이동 연산을 생략함. 이게 생각보다 엄청 큰 효과를 가져온다고 하고 크게 두 가지 경우가 있는데 Return Value Optimization(반환값 최적화)인 경우와 class type의 template object(임시 개체)가 동일한 유형의 복사 될 때인 경우다. Return ..

C++ 가상함수 테이블 (Virtual Table)

#include using namespace std; class A { public: virtual void Func1() { cout

C# 제네릭 (C++ > 템플릿)

using System; public class Test where T : class { public T Get_val(T _val) { return _val; } } public class Another { public static void Main() { Test int_test = new Test(); Console.WriteLine(int_test.Get_val(10)); } } 첫째 클래스 선언 라인에 보면 where T : class라고 명시 되어있다, Main 함수 내에 선언하고 있는건 int형이다, 따라서 아래와 같이 에러가 뜬다. C++와 가장 큰 차이점은 C#의 템플릿은 제약 사항이 많다는 것이다, SFINAE도 있겠지만 가장 큰 특징은 추상화를 할 수 없다는 점이다 따라서 아래는 에러..

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

프로세스 메모리 구조 프로세스의 메모리 구조는 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)으로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되는 대표적인 해시 알고리즘에는 ..