박트리

컴퓨팅적 사고력 문제 추천 별찍기, SWEA , 디버깅 시간, 본인이 자주 한 구현 실수 정리 대략적인 순서도를 그리고, 템플릿화 하는 것 연습. 코드길이가 줄어들어야 실수할 확률이 줄어듬. 비형 공부 상당한 난이도 갭이 있음. 100*에이형 비형 시험 STL 사용불가능. STL 구현법. 암기까지 할 필요없고 동작 과정을 이해하고 응용하는 법을 많이 공부하는 것이 좋음 해싱 : 비형보는데 해싱을 모르고 응용할 줄 모르고 응용할 줄 모르면 바로 혀 깨물어야 됨 링크드리스트 : 문제 많이 나옴 트리 구현 : 자식 수가 안 정해진 트리 구현하는 법 메모이제이션 : 한 번 계산한 값을 다시 계산안하는 개념이 있어야 함 비트마스킹 : 변수를 쪼개서 공간복잡도 아끼면서 저장, 다양한 비트 연산을 이용해서 코드를 최적화 하는 방법 이분탐색 : 기본 개념 분할 정복 : 가끔 출제됨 Sort : 소팅 알고리즘 퀵소트는 필수, 여유 머지, 계수, 기수까지 공부 Heap : 힙도 막상 필요할 때 있음. 스케쥴링 문제. Queue, Stack : 큐, 스택 사용, STL 쓸 수 있는 것. 그리고 짤 수 있는 것도 알아야 함 트라이 : 문자열 해싱 정도 트라이에 해싱을 끼얹음 LCA(Lowest Common Ancestror) : 디렉토리 구조 가계도 이런 유형 등장 BST(Binary Search Tree) : 힙으로 커버 가능 Segment Tree : 알아두면 쓸일. Sqrt Decomposition : 개념 쉽고 유용함 B형 유형 파악 배경지식 블록 부품 맞추기 문제 검색해봄 주어진 문제 함수를 1개 이상 만드는 것 문제 목표. 메인함수으 임의로 수정 3만개의 블록 절약비용의 합을 최대화하도록 2개씩 매칭 시키는 문제 3만개의 블록들 절약비용의 합 최대화 2개씩 매칭 오(엔)복잡도를 오(로그엔) 혹은 오(1)로 쵲거화하는 과정이 필요함. 대다수의 문제들이 상당한 구현력을 요구하고 있음 4시간 안에 풀이조차 생각하지 못햇따면 자료구조에 대한 응용력 혹은 문제 접근하는 방법 자체가 많이 부족함. 이 부분에 초점을 맞춰 우선 공부하고 만약 대략적인 구조는 설계했으나 구현을 완벽 노. 구현력을 충분히 연습하는게 좋음 풀어볼 만한 문제들 탄탄한 구현력 기반 다양한 접근법 시도.  구현력 조지는 문제. 시간을 정하고 딱 풀어야 함 9개의 문제가 있음 실전 비형 프로 팁 30분 이해 및 설계 30분 코딩 30분 디버깅 해서 3시간 2문제 1시간 문제 이해 및 설계. 2시간 구현. 디버깅 정확한 아웃풋 출력. 1시간 최적화임 최대한 naive한 방법으로 접ㄱ느해보기 가능한 복잡도까지 생각하기보다 쉽게 가능한 복잡도를 생각. 여기서 더 최적화할 방법이 존재하는지 1시간 정도 까지 충분히 고민해봄 문제 난독증 잘 못 일긍ㄹ 수 있음 1시간쯤 지나면 기분전환 화장실 ㅋㅋ 충분한 시간동안 구현 후 문제에서 요구하는 아웃풋 정확함 충분한 시간 가지고 최적화를 시도해봄 블록 부품 맞추기를 할 때. 전처리 한다거나 정렬을 해서 이분탐색을 한다거나 해싱을 해서 어떤 것을 좀 더 빨리 찾고 빨리 접근한다는 식 전처리, 메모이제이션, 이분탐색 ,해싱에서 다 끝남. 가끔 트라이 LCA, 세그먼트 트리가 나옴 이렇게 naive 한 구현과 최적화 부분을 나누어 코딩하게 되면 디버깅 하는 시간도 그만큼 줄어들게 됨 구현부분에서 이미 정확한 아웃풋이 나왔음이 보장되기 떄문에 최적화 부분에서 뭘 바꿨는데 이제 안나오는건지 집중해서 디버깅 가능. 로컬에서 먼저 stl을 사용해서 구현을 완료하고 아웃풋이 보장되면 그 때 남은 sTL들을 구현하는 방식으로 코딩하는 것이 디버깅하기 쉬움. 아웃풋이 나왔따고 그냥 제출하고 바로 퇴실하는 경우도 있음.  차원 압축 : 모든 데이터는 해당하는 데이터를 표현하는데 필요한 총 비트 수 사이트오프, 사이트오프 롱롱으로 압축 가능함.  2차원 그리드에서 2바2 영역을 1바1 크기로 압축 ,길이가 10인 1차원 배열을 길이1로 압축함 좌표 압축 : 데이터의 범위가 너무 크다면 등장하는 데이터들을 범위로 다시 넘버링 할 수 있음 랜덤 엑서스 링크드 리스트 : 링크드 리스트의 단점 랜덤 엑세스가 불가능하다는 것임 해당 노드 특정할 수 있음 아이라던지 밸류가 distinct 하다던지 그 값이 충분히 작다면 링크드 리스트에 존재하는 모드 노드에 대해 해당하는 키를 전역변수로 노드포인터를 저장하여 오(1)로 해당하는 노드에 접근 가능. 이분탐색 + 휴리스틱 : 데이터가 유니폼하게 분포되어 있는 상황에 정확한 이분탐색이 가장 효율적임. 데이터를 분석했을 떄 유니폼하지 않고 특정값에 몰려있다면 확률적으로 핻아부분을 포함하게 적절히 쪼개는 것이 좀 더 효율적임을 알 수 있음 http://baactree.tistory.com/53 http://koosaga.com/221?category=554434 피에스 대회나가서 수상하는 것이 목표?! 주기적 대회가 올라옴 전세계 사람들과 경쟁하고 레이팅 매겨줌 대략적인 난이도. 어느정도 수준 기준을 사용함 2000점 쯤 보라돌이 오렌지 와리가리. 국내 대학생 큰 대회 수상권

코드포스 러시아 운영 국제 프로그래밍 대회 사이트 세계 각국 프로그래머 1주일에 한번씩 2시간동안 5문제를 푸는 콘테스트가 열림.  이전의 콘테스트에서 출제되었떤 문제들을 프로블럼셋 카테고리에서 풀어볼 수 있음

sw test 샘플문제 블록 부품 맞추기 10개 C++ 20초 블록 부품 만드는 회사 준홍 불량 블록 부품 발견함 블록 부품 만드는 회사 불량 블록 부품 발견함 정상 블록 부품 크기 4곱4 블록 기둥 높이 한 곳 높이 다르면 불량 처리 서로 다른 불량 블록 서로 맞대어 육면체 오나성품을 만들어 재활용하고자 함 두 부품 기둥 면 마주 조립, 완벽히 일치함 높이는 8이 됨. 절약되는 비용은 육면체의 높이 8만큼임 밑면의 가로 세로 넓이가 각각 4바이4 블록 부품 30000개 주어질 때, 절약되는 완성품 총 합이 최대가 되도록 함 절약되는 완성품들의 총 합의 최대값을 반환하는 makeBlock() 의 함수 함수의 실행시간이 적을수록 높은 순위를 부여함 전체 실행 시간 20초임 해당하는 모양끼리 가장 긴 모양부터 서로 매칭시켜주면 됨 주어진 블록을 길이 내림 차순으로 정렬하고 해당하는 i번쨰 블록에 대해 2가지 테스크를 해결해야 함 주어진 블록을 길이 내림차순 정렬 아이번쨰 블록 이 2가지 테스크를 해결해야 함 대응되는 상대편 블록무양 찾기. 베이스를 뺴면 0,2 값을 가지는 4바4 행렬로 바뀜 플립한 다음 90도씩 4번 로테이션 한 모양 틀 2차원 배열 플립과 rotate 하는 방법 대응 되는 블록모양 중 가장 긴 길이의 블록을 구하기 naive 하는 방법 블록들을 전 부 순회 엔제곱 * 4 * 4*4  가장 먼저 접근 할 만한 쵲거화 4바4 2차원 배열 변수 하나로 치환 해당 배열 0,2 값을 가지는 16개의 1차원 배열 생각 3진수로 접근 3^16 가지의 수를 표현 하는 것이므로 10진수로 0,3^16에 해당하는 값으로 2차원 배열을 치환 가능 2개의 모양이 같은지 확인할 떄 단순히 변수의 동등비교로 해결가능함 블록모양을 변수 하나로 해싱이 가능하다면 대응되는 모양찾기를 더 빠르게 할 접근법이 많아짐 첫번쨰 접근법 또 다른 1차원 배열에 블록모양, 최대 기둥 높이, 인덱스 투플로 저장해두고 소팅하면 이후 같은 블록 모양 구간  엘알을 이분탐색으로 쉽게 찾을 수 있음 그 중 가장 긴 기둥을 포함하는 블록모양부터 매칭시켜주면 됨 두번째 접근법 vector<int> vec[3^16] 2차원 동적배열 오(1)에 해당 벡터에 접근해 가장 긴 기둥 포함 블록 모양 매칭 푸쉬 할때 작은 블록 맨 뒤 가장 긴 블록 맨 뒤부터 pop 해주면 됨. vector 아닌 list 나 stack 을 사용해도 무방함 맵 구현이 까다로움 그래서 간단한 방법 좌표압축 웰노운 데이터의 개수 앤이고 데이터의 범위가 주어진 데이터를 다시 넘버링 하면 최악. 해시앻서 충분히 전역변수로 선언할 만한 크기를 만들고, 같은 방식으로 구현하면 해당하는 위치를 찾는데 평균1에 찾을 수 있음 문제 해결 가능함

#pragma GCC optimize("O3") template <class T> class _vector { public: int _size; int capacity; T *arr; _vector() { _size = 0; capacity = 32; arr = new T[capacity]; } _vector(int k) { _size = k; capacity = k; arr = new T[capacity]; } ~_vector() { delete[] arr; } void clear() { delete[] arr; _size = 0; capacity = 32; arr = new T[capacity]; } void resize(int k) { T *temp; temp = new T[k]; for (int i = 0; i < _size; i++) temp[i] = arr[i]; delete[] arr; arr = temp; _size = capacity = k; } int size() const { return _size; } bool empty()const { return _size == 0; } T back()const { return arr[_size - 1]; } T* begin() const { return &arr[0]; } T* end() const { return &arr[0] + _size; } void push_back(T val) { if (_size == capacity) { resize(_size * 2); _size /= 2; } arr[_size++] = val; } void pop_back() { _size--; } T& operator [](int idx) { return arr[idx]; } T operator [](int idx)const { return arr[idx]; } }; ////////////////////////////////////////////////////////////// // sort stl template <typename It> void swap(It &a, It &b) { It c(a); a = b; b = c; } template <typename It> void sort(It begin, It end) { if (begin == end) return; swap(*begin, *((end - begin) / 2 + begin)); It pi = begin; It le = begin + 1; It ri = end - 1; while (le <= ri) { while (le <= ri && !(*pi < *le)) le++; while (le <= ri && !(*ri < *pi)) ri--; if (le <= ri) swap(*le, *ri); } swap(*pi, *ri); sort(begin, ri); sort(ri + 1, end); } template <typename A, typename B> struct pair { A first; B second; pair(A a, B b) :first(a), second(b) {} pair() {} bool operator < (const pair<int, int> &rhs)const { if (rhs.first == first)return second < rhs.second; return first < rhs.first; } }; /////////////////////////////////////////////////////////////// #define MAX 30000 int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int base[MAX], diff[MAX], sum[MAX], ss[MAX]; bool chk[MAX]; _vector<int> mp[MAX]; pair<int, int> vec[MAX]; int get_idx(int x) { int it = MAX; int le = 0, ri = MAX - 1, mid; while (le <= ri) { mid = (le + ri) / 2; if (ss[mid] >= x) { it = mid; ri = mid - 1; } else le = mid + 1; } if (it == MAX || ss[it] != x)return -1; return it; } void flip(int mat[4][4]) { for (int i = 0; i < 4; i++) { swap(mat[i][0], mat[i][3]); swap(mat[i][1], mat[i][2]); } } void rotate(int mat[4][4]) { int temp[4][4]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { temp[j][3 - i] = mat[i][j]; } } for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { mat[i][j] = temp[i][j]; } } } int makeBlock(int module[][4][4]) { for (int i = 0; i < MAX; i++)mp[i].clear(); for (int i = 0; i < MAX; i++) { chk[i] = false; base[i] = 10; for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; k++) { base[i] = min(base[i], module[i][j][k]); } } diff[i] = 0; sum[i] = 0; for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; k++) { int now = module[i][j][k] - base[i]; sum[i] = sum[i] * 3 + now; diff[i] = max(diff[i], module[i][j][k] - base[i]); } } vec[i] = { base[i] + diff[i],i }; ss[i] = sum[i]; } sort(vec, vec + MAX); sort(ss, ss + MAX); for (int i = 0; i < MAX; i++) { int idx = vec[i].second; mp[get_idx(sum[idx])].push_back(idx); } int ret = 0; for (int i = MAX - 1; i >= 0; i--) { int idx = vec[i].second; if (chk[idx])continue; mp[get_idx(sum[idx])].pop_back(); chk[idx] = true; int temp[4][4]; for (int j = 0; j < 4; j++)for (int k = 0; k < 4; k++)temp[j][k] = module[idx][j][k]; flip(temp); bool flag = false; for (int j = 0; j < 4; j++) { if (j)rotate(temp); int tsum = 0; for (int x = 0; x < 4; x++)for (int y = 0; y < 4; y++) { int now = diff[idx] - (temp[x][y] - base[idx]); tsum = tsum * 3 + now; } tsum = get_idx(tsum); if (tsum == -1 || mp[tsum].empty())continue; int it = mp[tsum].back(); chk[it] = true; ret += base[idx] + base[it] + diff[it]; mp[tsum].pop_back(); flag = true; break; } } return ret; }