CafeM0ca

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

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 ..

문제 해결 과정 자료구조 힙을 구현하여 insert와 remove 함수를 작성하여 해결한다. 문제의 제한시간은 1초이다. 따라서 insert 함수와 remove 함수를 O(log N) 시간으로 해결할 수 있도록 구현해야 한다. 시간이 빡빡한 문제이므로 cin.tie와 cin.sync_with_stdio를 꼭 해주자. 그리고 endl 대신 '\n' 으로 개행하자. 구현 #include #include using namespace std; template class max_heap{ public: max_heap(); void insert(type); void remove(int ); void print(); void heapify(int); type operator[](const int); ..

자료구조 heap 특징 merge sort처럼 추가 배열이 필요 없음 complete binary tree에 기반함으로 O(nlogn)의 성능을 보임 heap property max heap property: 부모는 자식보다 크거나 같음 min heap property: 부모는 자식보다 작거나 같음 논리적으로는 배열로 구현가능함 루트 노드: A[1] A[i]의 부모 = A[i/2] A[i]의 왼쪽 자식 = A[i*2] A[i]의 오른쪽 자식 = A[i*2+1] 소스코드 heap.hpp #include #include template class max_heap{ public: max_heap(); void insert(type); void remove(type); int find(type); void so..

학교 과제로 C로 단일연결리스트 짰다.C++로 구현하면 제네릭 프로그래밍이 가능한데 C는 ... 무안하다. nullptr도 없고 소멸자도없고; 아무튼 링크드리스트의 크기를 명시해주면 삽입,삭제가 수월하다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301..

친구에게 도움을 많이 받았다. 3일걸렸는데 1일차에는 링크드리스트 직접구현해서 써먹을려다 실패. 2일차에는 std list 사용법 익히다가 erase부분에서 조건 몰라서 실패 3일차에 erase부분 도움받았다. 123456789101112131415161718192021222324252627282930313233343536373839#include#include#includeusing namespace std;int main(void){ int L; //줄 수 string s; cin >> L; while(L>0){ list keyloger; //keyloger 리스트 생성 list::iterator insert_pos = keyloger.begin(); //insert_pos라는 리스트의 iterato..

간단한 자료구조라서 짜는데 별로 오래 안걸릴 줄 알았지만 최소 12시간 붙잡고 구현했다.모든 자료형에 대해 처리 해주고 싶었는데 C++은 정적언어라 불가능했다. 템플릿을 쓰던, auto를 쓰던 입력값에 대해 자료형을 알아내는 문법은 없더라..(이것땜에 하루 새벽 보내버렸고)일단 포기하고 int형만 받도록 했다. 아마 모든 자료형에 대해 처리하려면 오버로딩이나 자료형 테이블을 만들어서 테이블을 통해 연결리스트의 노드들을 이어줘야 할 듯 하다. (파이썬 쓰는게 답이다)컴파일 환경: g++ -std=c++11 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061..

링크드리스트를 2일째 구현중인데 머리가 아프다.모든 자료형에 대하여 처리 해주려 했는데 C++은 정적언어라 불가능하다..어떻게든 하려고 이곳 저곳(stackoverflow 라던가)에 질문 던젔는데 돌아오는 답변은 "그렇게 디자인 하지 마세요."였다. 차라리 python으로 처리 하는게 더 편할 듯.. C++로는 일단 단일 자료형에 대하여 처리 해야겠다.

30분만에 구현했다. 다른 사람이 어떻게 짯는지 관심 없어서 스택이랑 비슷하게 짜봤다.선형 큐 말고 환영 큐(원형 큐)로 짰다. 테스트 케이스를 안넣어봐서 잘 모르겠는데 뇌파일러로 굴려보면 제대로 짠거같다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include typedef struct queue { int index; int head; int qsize; int arr[10000];}Queue; void Push(Queue * q) { int v; scanf("%d", &v); if (q->qsize == 10000) p..

구현하는데 있어서 별 어려움은 없다. 모카는 C++하던 습관 때문에 구조체 메소드로 만들려 했는데 C표준에서 거부하는거 같다. 유감.. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include typedef struct stack { int snum; int arr[10000];}Stack; int Empty(Stack * s) { if (s->snum == 0) //비어 있으면 0 return 0; else return 1; //차 있으면 1} int Top(Stack * s) { if (s->snum == 0) //최상단이 없으면 -1 return -1; ..