https://www.acmicpc.net/problem/7469 Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다. 실제로 구현해 본 건 처음이었는데 예전에 명우씨한테 잠깐 설명들었던게 도움이 됐다. (Persistent Segment Tree에 대한 설명은 요기에) vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N) 자세한 설명은 다음에... 테스트케이스 : (출처 : NEERC Subregional Contest) #include #include #include #include #define MAXN 262150#define INF 1987654321using name..

Red-Black Tree특징모든 node는 BLACK 또는 RED의 색을 가진다.root node는 항상 BLACK이다.leaf node도 항상 BLACK이다.RED가 연속되어 있을 수 없다. (부모-자식간)root node부터 leaf node사이의 BLACK의 개수는 동일하다.self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)동작색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.조회BST와 동일하게 수행삽입새로 삽입되는 노드는 항상 RED로 시작한다.부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)부..

출처 : https://kldp.org/node/19320 먼저1. 함수안에서 char *name = "KLDP"; char name[] = "KLDP"; 가 어떻게 다른지 ? 제가 이해하기로는name[] 은 KLDP를 위한 메모리가 할당되고 바로 그 주소를 가리키지만 return을 해도 그 메모리는 함수종료시 메모리 반환이 되므로 warning이고*name 은 메모리 어딘가에 "KLDP" 를 할당하고 그 시작점을 가리키는 포인터를 선언하고 그 주소를 넘겨주므로 (어딘가에 선언된 "KLDP"는 함수가 끝나도 유효) 함수가 종료하면서 *name이 반환되더라도 이미 return값으로 그 주소를 넘겼으므로 참조할수 있다인데 맞나요 ? 그렇다면 어딘가에 선언된 "KLDP"는 언제 메모리가 반환되나요 ? 프로그램..

글 본문에 대한 내 생각을 밝히는 것이 아니기 때문에 트랙백은 남기지 않았다. 다만 글 쓰신 Gony님이 인용하신 '조엘 온 소프트웨어'의 대목에 많은 오류가 있어서 이렇게 글을 적어본다. 물론 좁은 지면과 독자의 배경 지식을 감안해서 쉽고 간단하게 malloc() 동작 원리를 썼으리라 생각한다. 그러나 실제 방식은 이와 많이 다르다. 혹시나 오해를 가질까 해서 이 글을 쓴다.malloc이 어떻게 동작하는지 아십니까? malloc의 본질은 사용 가능한 메모리 블록을 연결 리스트linked list로 길게 연결한 자유 체인(free chain)입니다. malloc은 연결리스트를 따라가며, 요청 받은 메모리 양보다 큰 블록을 찾습니다. 이렇게 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하며, ..

void* realloc(void* memblock, size_t size) realloc은 기존 위치의 malloc으로 할당된 메모리 공간을 확장시키는 것이아니라 새로운 위치에 메모리를 할당 후 기존 데이터를 복사후, 기존 영역은 해제하는 방식이다. 따라서 realloc을 수행했다면 기존 위치를 가리키는 모든 포인터들의 위치를 새로운 위치로 변경해줘야 한다. 또한 새로 지정한 사이즈만큼의 공간을 할당할 수 없거나, 사이즈를 0으로 입력한경우(free와 같은 것으로 간주) NULL포인터를 리턴한다. realloc이라는 함수 이름때문에 현재 위치에서 extend한다고 생각하기 쉬운데 그렇지 않다.

http://codeforces.com/problemset/problem/913/D D. Too Easy Problemstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are preparing for an exam on scheduling theory. The exam will last for exactly T milliseconds and will consist of n problems. You can either solve problem i in exactly ti milliseconds or ignore it and spend no time. You don't..

http://codeforces.com/problemset/problem/909/D D. Colorful Pointstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one fro..

http://codeforces.com/problemset/problem/909/C C. Python Indentationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.We will consider an extremely simplified subset of Python with only two..

http://codeforces.com/problemset/problem/900/CC. Remove Extra Onetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every inte..

삼포적금과 별개로 대한항공 마일리지를 모으는 다른 방법들 2018년 2월 크로스마일 카드가 공지도 없이 갑작스럽게 발급을 중단했고, 심지어 유효기간이 만료되어가는 카드는 연장도 불가하다. 대체할 만한 카드가 아직은 마땅히 없으나, "삼성 & 마일리지"카드가 그나마 효율이 좋은 것 같다. . 하나 크로스마일se 카드(연회비 10) : 국내 결제시 1500원당 1.8마일리지 적립 (1000원당 1.2마일리지 비율) - 마일리지 적립비율이 '가장' 높은 것은 아니나 연간 1500만원 이상 사용할시 주어지는 보너스마일과 크로스마일save를 이용할 경우 효율이 제일 좋은 카드로 알려져있다. 자세한 카드 정보는 링크 클릭 1. 크로스마일 save(15:1) : 1년 최대 30만원을 2만 마일리지로 구매 가능 - 단..