CafeM0ca

정의 레드블랙트리는 다음 조건을 만족하는 이진탐색트리다. 조건 각 노드는 red 혹은 black이다. 루트 노드는 black이다. 모든 Leaf 노드(NIL 노드)는 black 노드다.(NIL노드: 트리의 각 leaf들이 공통적으로 가리키는 추상적인 노드. root의 부모도 NIL 노드) red 노드의 자식들은 전부 black이다.(red 노드가 연속되어 등장하지 않는다) 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다. 레드블랙트리의 높이 루트노드로부터 NIL 노드를 만날 때까지의 높이를 측정한다. 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 정점의 개수이다. 노드 x의 블랙-높이 bh(x)는 x로부터 리..

많은 사람들이 문제 풀다가 리모컨을 부셔버리고 싶다는 그 문제.. 실생활 문제이다. 기본 채널이 100번 채널이다. 최소 채널은 0번 채널이고 최대 채널은 무제한이다. n번 채널로 이동하고 싶은데, 리모컨의 숫자부분이 몇 개 부셔서 있다. 채널은 위아래로 조작할 수 있다.(위아래는 부서지지 않음) 최소한 리모컨을 써서 n번째 채널로 이동할 때, 몇 번 동작하는가? 깊게 생각해보기 9번이 고장나고 99번 채널로 이동할 때 리모컨을 조작하는 프로세스는 아래 3가지다. 채널을 한칸 내린다. (1번 동작) 99번을 기준으로 위로 가장 가까운 채널을 찾는다.(100번 채널 -> '1' '0' '0' 3번 동작) 아래로 한칸 내린다. (1번 동작, 총 4번) 99번을 기준으로 아래로 가장 가까운 채널을 찾는다. (..

문제인식 문제링크 생활속에서 이러한 유형을 자주 접할 수 있다. 최저가를 찾는 문제다. (0) 가장 싼 패키지와 가장 싼 낱개의 가격을 찾는다. 낱개 6개 == 패키지 1개이므로, (1) 가격이 낱개 6개가 = 6이고, 패키지 > n >..

heap의 응용 '우선순위 큐는 힙을 응용하여 구현한다' 라는 오류를 갖지 않도록 조심하자. 스택을 배열이나 링크드 리스트로 구현하듯이 우선순위 큐를 heap으로 구현하는 것은 여러 구현체 중 한가지일 뿐이다. 힙과 마찬가지로 (1)최대 우선순위 큐 와 (2)최소 우선순위 큐 2종류가 있다. 우선순위 큐에서는 2가지 연산을 지원한다. insert(x): 새로운 원소 x를 삽입 O(log n) extract_max(): 최대(또는 최소)값을 삭제 O(log n) 이거 한번 해본 것 같은데? 최대 힙 이 문제를 풀면서 heap을 작살나게 정복했다. 구현 template class max_priority_queue{ public: max_priority_queue() { data[0] = 0; }; void ..

std::vector는 많은 C++ 프로그래머들에게 사랑받는 컨테이너다.배열은 정적이라 컴파일타임에 이미 메모리 공간에 자리잡고 있어서 인덱스 범위 안에만 있다면 접근이 가능하지만벡터는 동적이라 컴파일타임에 메모리가 자리잡고 있지 않다. 간간히 2차원 벡터가 필요할 경우가 있다.이 글에서는 간단하게 설명하고자 한다. 벡터의 기본 선언은 다음과 같다. std::vector v; std::vector도 하나의 클래스로써 자료형으로 취급된다. 따라서 다음과 같은 선언이 허용된다. std::vector dv; 위 선언을 통해 간단하게 2차원 벡터를 만들었다. 그러나 여기서 끝나면 포스팅 안했다. 서론에서 말했듯이 벡터는 동적이므로 위와같이 선언한 후 인덱스에 접근하면 out_of_range 에러 메시지를 볼 수..

이 규칙들은 C++에서 지켜야하는 것들이다. https://en.cppreference.com/w/cpp/language/rule_of_three Rule of Three소멸자, 이동 생성자, 이동 복사 연산자를 정의해두자. Rule of Five소멸자, 이동 생성자, 복사 생성자, 이동 대입 연산자, 복사 대입 연산자 다섯 가지 특수 멤버 함수들을 구현해놓자. Rule of Zero소멸자, 이동 생성자, 복사 생성자, 이동 대입 연산자, 복사 대입 연산자 다섯 가지 특수 멤버 함수들을 필요로 하지 않도록 디자인 하는 것이다.기본적인 방법으로는 구식 스타일의 메모리 할당을 피하는 것이다.A클래스를 2차원 배열로 동적할당 하기 위해 A**으로 선언하지 말고 vector 이런식으로 사용하자. vector는 ..

유니폼 초기화는 narrowing(축소변환)을 방지할때 사용한다. class A{ int num; public:A(int i) : num(i) {}A() : A{1} // 생성자 유니폼초기화}; int main() { A a{3.14}; // 컴파일 경고! A aa{3}; // 정상 int * arr = new int[4]{1,2,3,4}; // 동적할당에서 활용가능}

후배가 추천해줘서 JUCE 연습용으로 만들었다. https://github.com/jinykim0x80/Tic-Tac-Toe 게임이 종료되면 재시작이나 나머지 버튼 클릭 비활성화 처리는 안되어있는데 나중에 처리해야겠다.

구현한거 맞겠지 O(n^2) 123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std; void printVector(vector& v) { for(auto& i : v) cout

판정이랑 콤보만 띄우면 무한모드는 완성