codedoc

구글 블로그로 곧 이전합니다. http://codersbrunch.blogspot.kr/ 이유는 http://notice.tistory.com/235912/21에 백업 기능이 없어진다고 합니다.글이 많은 제 블로그의 특성상 타 사이트로의 이전이 힘들면 제 컨텐츠를 지키기 어려워집니다.따라서 비교적 복구 및 백업이 자유로운 구글 블로그로 이전합니다. 이동하는 대로 현 블로그의 글을 비공개 처리하고 있습니다.

괜찮은 공부루트를 설계해보고 있다. 작성중...... 1. 입출력iostream 사용 팁ios::sync_with_stdio(false); 이거쓰면 빨라짐endl은 '\n'보다 느리다 '\n' 사용추천getchar가 scanf보다 더 빠름… 1. 시간복잡도koi 트리분할 문제n*(1/n+2/n+...) -> nlgn2. 자주 쓰이는 증명 및 접근수학적 귀납법 - 2163번: 초콜릿 자르기 https://www.acmicpc.net/problem/2163 1. 자료구조Vector, Deque, Queue, Stack, Set, Map, Multiset, multimapStack - 1918번: 후위표기식 https://www.acmicpc.net/problem/1918List - 5397번: 키로거 htt..

https://kldp.org/node/72882 int *D = new int[T + 1](); printf("%*d ", s, a[i][j]);

네이버 블로그 활동을 거의 접으면서 기존의 블로그 내에 있던 게시글 일부를 옮기고 있습니다.워낙 예전에 작성했던 글들이라 오류, 증명x, 더러운 소스 등 문제가 많지만 일단 옮겨 놓고 차근차근 수정해나갈 계획입니다. 엑박 문제는 조금씩 해결해 나가고 있습니다.

deque- Random access iterator- 덱(deque) 시작과 끝에서의 삽입/삭제 모두(amortized) 상수 시간- 덱(deque)의 중간에서의 삽입/삭제는 덱의 크기에 선형 시간- Member functionn vector member function + push_front(), pop_front() Iteratorsbegin시작 주소 리턴end끝 주소 리턴 Capacitysize크기를 리턴resize크기 조절empty비어있는지 확인 Element accessfront첫 원소에 접근back끝 원소에 접근 Modifierspush_back끝 부분에 원소 추가push_front앞 부분에 원소 추가pop_back마지막 원소 제거pop_front처음 원소 제거insert원소 삽입erase원..

Vector- c 스타일의 배열과 유사한 동적 배열(dynamic array)- Random access iterator- 벡터(vector) 끝에서의 삽입/삭제 모두 (amortized) 상수 시간- 벡터(vector)의 시작이나 중간에서의 삽입/삭제는 선형 시간 Iteratorsbegin시작 주소 리턴end끝 주소 리턴 Capacitysize크기를 리턴resize크기 조절empty비어있는지 확인 Element accessfront첫 원소에 접근back끝 원소에 접근 Modifierspush_back끝 부분에 원소 추가pop_back마지막 원소 제거insert원소 삽입erase원소 삭제swap원소 위치 바꾸기clear비우기 예제push_back, pop_back 이용소스출력#include#include..

우선순위 큐는 일반 큐와는 다르게 현재 저장된 값들 중 최댓값 혹은 최솟값을 내놓습니다.하나 push 혹은 pop 할 때 시간복잡도는 O(logN) 입니다. +) class 이용http://gigi.nullneuron.net/comp/cpp-stl-priority-queue.php push(X) // 우선순위 큐에 새로운 값을 추가top() // 우선순위 큐의 루트 노드 리턴pop() // 우선순위 큐에서 루트 노드를 삭제size() // 우선순위 큐 내에 포함된 원소들의 수를 리턴empty() // 우선순위 큐가 empty이면 true를 리턴 우선순위 큐 중 최댓값을 내놓는 것을 Max 힙, 최솟값을 내놓는 것을 Min 힙이라고 부릅니다.Max 힙을 사용할 때는1. priority_queue< int,..

이건 프로그래밍 경시에 나간다면 절대 모르면 안된다. 컴퓨터 사양에 따라 다르겠지만보통 stl sort는 1초 안에 1,000,000개 데이터는 껌으로 정렬하고 5,000,000개는 조금 아슬하다.경우에 따라 사용해 보자. sort- sort(시작주소,끝주소+1)- sort(시작주소,끝주소+1,조건자)* [b,e) 구간 이란 b이상 e미만을 뜻한다.일반적인 정수형 배열방의 전체 오름차순 정렬 소스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include using namespace std; int main(){ int A[10]={72,96,15,26,25,43,56,50,30,64}; int B[10]={72,96,15,26,25,43,56,..

plane sweeping 사각형 넓이 구하기 알고리즘문제링크 : https://www.acmicpc.net/problem/3392 작성중... 아래 처럼 직사각형이 겹쳐졌을 때 색칠된 부분의 넓이 합을 구하는 것이 목표입니다. 먼저 각 직사각형의 가로선을 포함하는 x축과 평행한 선으로 잘라 줍니다. 필요없는 좌표들을 버리고 나면 다음과 같이 트리를 구성할 수 있습니다.각 트리는 (y축 합, 카운트)데이터 묶음을 가지고 있고 앞으로 (sum, cnt)라고 부르겠습니다. 각 직사각형의 세로성분 데이터를 얻어오고 각 선들을 x축 기준으로 정렬시킵니다.이렇게 하면 왼쪽에서부터 sweep을 차례대로 할 수 있을 것입니다. sweep을 x축이 작은 세로선 부터 시작합니다.넓이을 어떻게 구하냐면, 각 과정마다 (직..

인터넷에 널려있는 n^2 해법은 생략하고 이분탐색을 이용한 nlogn 해법을 소개합니다.LIS는 부분수열이 되는 것 중 가장 긴 수열을 찾는 알고리즘 입니다.무슨 말이냐 하면,8 12 15 9 13 1 14 5이렇게 있으면 8 -> 9 -> 13 -> 14 가 가장 긴 수열이 되고 이를 찾는 알고리즘이라는 소리죠. n^2 해법에서 dp의 정의가 마지막 수가 x번째인 가장 긴 최장증가수열을 의미한다면다음에서 소개할 nlogn 해법에서 dp의 정의는 길이가 x인 최장증가수열의 마지막 수의 최소값를 의미합니다.두 알고리즘이 같은 역할을 할 것이라는 점은 뭔가 직관적으로 와닿는다고 생각합니다.익숙치 않다면 아래 그림을 보며 이해 해보시기 바랍니다. 앞서 말했지만 이분탐색을 이용하기 때문에 이분탐색을 모르시는 분..