CafeM0ca

문제인식 문제링크 생활속에서 이러한 유형을 자주 접할 수 있다. 최저가를 찾는 문제다. (0) 가장 싼 패키지와 가장 싼 낱개의 가격을 찾는다. 낱개 6개 == 패키지 1개이므로, (1) 가격이 낱개 6개가 = 6이고, 패키지 > n >..

LogCon 선린인터넷고등학교 정보보호과 서버 프로그래밍 동아리인 TeamLog에서 운영하는 서버 퀴즈 대회이다. 라때 처음 열렸는데 벌써 3회차다. 후배님들이 어떤 문제를 만들었는지 궁금하여 참가했다. 문제풀이 패킷트레이서같은 도구를 사용하는 문제는 풀지 않았다. HELLO, LOGCON!(50pts) 기본 체크 문제. 답: Teamlog{H3LLO_LOGCON!} 꼭꼭 숨어라 FLAG가 보인다(100pts) 파일 다운로드 들어가보면, google drive에 html 파일 하나가 보인다. P 태그에 FLAG 포멧과 함께 답이 보인다. 답: Teamlog{h0w_did_u_find_it} 네트워크 케이블(200pts) UTP케이블 CAT.6의 2번째 6번째 8번째 선과 대역폭이 정답인 것 같다. 위 이..

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

나는 자기 주장이 뚜렷하고 이기적이다. 지인들과 이야기 하다보면 '저 분은 왜 저렇게 생각할까? 답답하다' 라고 느낄 때가 있다. 하지만 지인들도 마찬가지로 나에게 답답함을 호소한다. 내가 이러한 성격을 갖게 된 것은 중학교 때 형성된 것 같다. 20살이 되어서야 역지사지의 입장으로 더 깊게 생각하고 말을 할 때 필터링을 하도록 노력하고 있다. 경청(조신영,박현찬 저)은 악기 회사에 재직중인 이토벤의 이야기를 다룬다. 이토벤은 이 과장과 베토벤의 합성어로 이 과장의 별명이다. 베토벤은 청각을 잃고 듣지 못하게 되었다. 이 과장 또한 팀원들의 말을 듣지 않아 이러한 별명이 생겼다. 회사가 기울어지는 마당에 이토벤은 병을 얻고 시한부 판정을 받는다. 이토벤은 발달장애가 있는 아들이 하나 있다. 아들은 발달장..

문제 해결 과정 자료구조 힙을 구현하여 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..

3줄 요약 떠나보내는 10대 올해 SW마에스트로를 통해 많은 것을 배우고 깨달음 이제 스무살. 10년 목표 세움. 철 들어야지 이제는 그만 헤어질 시간. 19.9살 초등학교 5학년 때부터 그토록 원했던 고등학교 합격자 명단에 내 이름 석자가 적혀있을 때의 감동은 생생하다. 그리고 그 간절함은 이후에 단 한번 밖에 오지 않았다. 고등학교에 입학하고 전공이 너무 좋은 나머지 학교 공부는 멀리했다. 여기에는 세 가지 이유가 있다. 초등학교때 부터 학원에 찌든 삶이 지겨웠다. 하고 싶은 일을 하며 살고 싶다는 고집이 있었다. 공부에 대해 사회에 작은 저항도 했었는데 지금 돌이켜보면 그게 사춘기였다. 1학년 1학기 중간고사 결과 석차가 50%였다. 모의고사는 4441(국영수한국사) 대학에 갈 필요성을 느끼지 못했..

시간복잡도 최선: NlogN (피벗이 중앙에 위치할 경우) 평균: NlogN 최악: N^2 (분할이 0:10으로 되는 경우) 소스코드 #include #include using namespace std; void generate(vector& v) { random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(1,30); for(int i = 0; i v[r]) { // 오름차순 j++; } else { i++; swap(v[..