AVL 트리란? 이번글은 https://cjbworld.tistory.com/25 의 코드에 기반을 두고 확장하여 작성한 버젼입니다. 기존의 이진 탐색트리에서 탐색의 경우 "로그 시간복잡도를 보장해준다"라고 알고있는데 예외가 존재합니다. 바로 BST애 데이터를 삽입할 때 데이터들을 오름차순으로 삽입할 경우 트리의 모양이 요런식으로 되어 버려 탐색시 로그 시간복잡도가 안나온다는 것입니다... 선형시간 복잡도가 나오겠지용 그래서 이러한 문제점을 해결해주는 도구들이 바로 AVL 트리, 2-3-4트리, B트리, 2-3트리, Red-Black트리 등등이 있습니다. 이중에서도 AVL트리에 대해서 다뤄볼 것인데요. 이 AVL트리에는 위의 그림판 그림처럼 "균형"이 안맞는 상황을 위해 몇가지 개념이 추가가 됩니다. 바..

DX물방울책을 읽으면서 간단하게 정리한 글입니다 :) Vector란? 크기와 방향을 모두 가진 수량을 가르키는 말입니다. 벡터는 힘이나 변위, 속도를 나타내는데 쓰입니다. 벡터에서 "상등"하다는 말은 두 벡터가 있을 때 오직 길이가 같고 같은 방향을 가리킬 때만 두 벡터는 상등하다고 말할 수 있습니다. DX물방울 책 P7을 보면은 "우리가 어떤 벡터를 좌표로 규정하거나 식별할 때 그 좌표는 항상 어떤 기준계에 상대적임을 뜻하기 때문이다" 해당 문장을 이해할려고 유튜브 강의나 여러 블로그를 보았습니다. 저는 위의 문장을 (2차원 평면이라 가정) "어떤 벡터공간의 기저는 유일하지 않다"는 말로 이해를 하였습니다. 여기서 "기저"라는 말이 등장하는데 기저는 "어떤 벡터공간 V의 벡터들이 선형독립이면서 벡터공간..

#include #include using namespace std; int sharedResouce = 0; void func() { for (int i = 0; i 읽어들인 잔액에 5만원을 더한다 => 더한 값을 저장한다. 이렇게 볼 수 있습니다. 그런데 프로세스A가 먼저 실행되어 10만원이 있는 계좌 잔액을 읽은다음에 읽어들인 잔액에 2만원을 더했습니다. 그리고 더한 값을 저장하면 되는데 저장하기 전 프로세스 B가 현재 계좌 잔액을 읽어버리고(프로세스A가 아직 더한값을 저장 하지 않았기 때문에) 나서 현재 10만원 + 5만원을 진행하였습니다. 그리고 프로세스 A는 12만원을 저장하고 프로세스 B는 자신이 한 일을 하기위해 15만원을 계좌에 저장했습니다. 그러면 원래는 17만원이 저장되어야 하지만 1..

저희가 아주 자주사용하기도 하고 사용하기 쉬운 라이브러리인 ios_base 라이브러리에 대해서 알아보도록 하겠습니다. #include #include using namespace std; int main() { string s; char c; std::cout > s; std::cout > c; return 0; } 위와 같은 코드가 있을 때 위와 같이 입력하면 입력을 받지 않고 바로 끝내버립니다. 마찬가지로 int main() { int n; char c; printf("정수입력 : "); scanf_s("%d", &n); printf("문자 입력 : "); scanf_s("%c", &c); return 0; } 위의 소스코드를 빌드한다음에 실행하고 1을 입력하고 문자를 입력하려는 순간 프로그램이 종료..

template void fucn(T&& param) { ... } "param의 형식은 오른값이지만 param자체는 왼값이다" 위의 코드와 문장을 보고 무슨말이신지 이해가 안 가신다면 https://cjbworld.tistory.com/27를 보고 와주시면 감사하겠습니다. 전달 참조란? auto, template 같은 "형식 연역"에서 type deduction 발생시 자주사용하는 개념입니다. (형식 연역 : 아직은 정해지지 않았지만 컴파일 타임에 때려 맞추겠다) 오른값 참조와 비슷하게 생긴 요녀석은 &&를 같이 사용합니다. 위 코드애서 p1는 lvalue입니다. 컴파일러 경고에 따르면 rvalue참조에다가 lvalue를 넣을 수 없다고 하는군요. 왜냐하면 mp의 형식은 오른값 참조이기 때문에 오른값을..

이번글은 오른값 참조와 전달(보편)참조에 대한 글입니다. (전달 참조는 보편참조로도 불립니다) 오른값의 개념이 Mordern C++ C++11부터 생겼으며 해당개념의 등장으로 C++속도의 엄청난 치아를 가져다 주었습니다. 먼저 오른값이 무엇인지 알아보기 전에 "왼값"이 무엇인지 개념부터 살펴보도록 하겠습니다. 왼값(lvalue, l-value)은 단일식을 넘어서 계속 유지되는 개체이며, 오른값(rvalue, r-value)는 "전체 개체에서 - 왼값" 인 개체입니다. 즉 임시객체나, 상수 등이 포함됩니다. 기존의 참조는 '&'하나만 사용하고 오른값 참조의 경우 '&&'두개를 사용합니다. template void fucn(T&& param) { ... } "param의 형식은 오른값이지만 param자체는 ..

먼저 컴퓨터의 4가지 핵심 부품인 CPU, 메모리, 보조기억장치, 입출력 장치는 메인보드에 연결되어 버스중에서 시스템버스를 통해서 필요한 데이터들을 주고 받습니다. 이중에서도 이번글은 CPU의 ALU, 제어장치(Control Unit)의 동작방식을 알아보고 핵심 레지스터들의 종류와 주소 지정방식의 큰개념들을 살펴보도록 하겠습니다. 먼저 메모리의 경우 현재 실행중인 프로그램의 명령어, 데이터를 저장합니다. “주소”단위로 나누어서 저장합니다. CPU의 경우 메모리에 저장된 명령어를 읽고 명령어를 해석하고 명령어를 실행하는 부품입니다. 이 부품은 ALU, 레지스터, 제어장치로 구성되어 있습니다. 이 세가지의 핵심역할은 ALU의 경우 계산, 레지스터는 임시 저장장치 역할, 제어장치는 제어신호를 보내고 → 명령어..

이번글은 이진 탐색 트리(Binary Search Tree)에 대해 알아보고 구현을 해보도록 하겠습니다. 이번글의 BST는 균형의 개념이 안 들어간 BST입니다. (다음글에 균형잡는 AVL 트리를 이어서 적도록 하겠습니다.) 먼저 이진탐색 트리의 개념부터 살펴보도록 하겠습니다. BST는 이진트리의 확장된 버전입니다. (힙도 이진트리의 일종이지만 힙은 "완전 이진 트리"입니다.) 이진트리는 자식노드를 두개를 가지는 자료구조입니다. 이진트리를 기반으로 구현되어 있고 데이터를 빠르게 찾는데에 최적화 되어 있습니다. O(Log 2)를 탐색하는데 가집니다. BST의 핵심은 "삽입", "탐색", "삭제"입니다. 삽입의 핵심로직을 살펴보면 Root보다 값이 작다면 왼쪽에 데이터를 삽입하고 Root보다 값이 크다면 오..