알고리즘/종만북19 선형 자료구조 c++의 vector를 떠올리면 된다. 내부적으론 모두 정적 배열로 구현돼 있다. append()를 할 때 이미 배열이 꽉 차있으면 동적 배열의 크기를 다시 할당해야 한다. 이는 현재 들어있는 원소수에 비례하는 시간이 필요하다. 이 부분을 최적화하지 않는다면 동적배열의 자료의 추가/제거 시간은 선형시간이다. 하지만 크기를 다시 할당할때 현재 있는 원소수*2로 할당한다면 평균 O(1)에 가능하다. 일반적인 양방향리스트의 구현 struct listNode{ int element; listNode * next, prev; } 삭제와 undo - knuth의 dancing link, 조합탐색, UI의 되돌리기에서 쓰임 void deleteNode(listNode* node){ node->prev->next = .. 2020. 2. 7. 비트마스크 1은 부호있는 32비트 상수취급이므로 (1 2020. 2. 5. MATCHORDER - 출전 순서 정하기 (그리디) https://algospot.com/judge/problem/read/MATCHORDER 쉬운 문제지만 정당성 증명하는 부분을 유념하기 위한 기록 https://suuntree.tistory.com/103 정당성증명 상대팀의 출전순서가 주어진다. 선수의 능력은 rating 점수로 표현된다. 우리팀 선수들을 적절히 잘 배치해서 최대승수를 구해라 상대선수 rating > n; for (int i = 0; i > ru[i]; for (int i = 0, u; i > u; ko.insert(u); } int ans = 0; for (int i = 0; i < n; i++) { int t = ru[i]; auto it = ko.lower_bound(t);.. 2020. 2. 3. QUANTIZE - Quantization (dp, 전처리, 수학) https://algospot.com/judge/problem/read/QUANTIZE 최대 100개의 숫자 배열이 주어진다. 최대 10개의 대표 정수를 정해서(배열에 없는 값 허용) 오차 제곱의 합의 최소치를 구하는 문제. 오차 제곱의 합이 최소가 되도록 하려면 대표값을 각 집합의 평균으로 정해야 한다. (식을 미분하면 알 수 있다) 입력받은 배열을 오름차순 정렬하면, 인접한 두 숫자는 같은 대표값을 갖거나 다른 대표값을 갖는 집합의 경계이다. f(k,e,t) : k이후, 이번 집합의 처음 인덱스 e, 여태까지 분류한 집합의 수 t에 대해 오차 제곱의 합의 최소를 반환 배열의 각 숫자마다 두개의 선택지가 있다. 새로 집합만들어 그 집합의 첫번째 원소가 되거나 기존 집합에 포함되거나. cost(l,r) .. 2020. 2. 3. 이전 1 2 3 4 5 다음
