CafeM0ca

많은 사람들이 문제 풀다가 리모컨을 부셔버리고 싶다는 그 문제.. 실생활 문제이다. 기본 채널이 100번 채널이다. 최소 채널은 0번 채널이고 최대 채널은 무제한이다. n번 채널로 이동하고 싶은데, 리모컨의 숫자부분이 몇 개 부셔서 있다. 채널은 위아래로 조작할 수 있다.(위아래는 부서지지 않음) 최소한 리모컨을 써서 n번째 채널로 이동할 때, 몇 번 동작하는가? 깊게 생각해보기 9번이 고장나고 99번 채널로 이동할 때 리모컨을 조작하는 프로세스는 아래 3가지다. 채널을 한칸 내린다. (1번 동작) 99번을 기준으로 위로 가장 가까운 채널을 찾는다.(100번 채널 -> '1' '0' '0' 3번 동작) 아래로 한칸 내린다. (1번 동작, 총 4번) 99번을 기준으로 아래로 가장 가까운 채널을 찾는다. (..

문제 해결 과정 자료구조 힙을 구현하여 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만 3천원이 있길레 다 응시료로 썼다.(넘 비쌌다..) 입금하려고 은행을 찾았는데 마침 딱 내가 사용하는 은행의 ATM이 있었다. 입금완료 후 며칠뒤, 외주도 껴있고 동아리 프젝도 저퀄이라 대회갈 시간이 없어서 환불하려 했는데 거절당했다.. 어쩔수 없이 갔다. 성결대학교를. 늦을뻔했지만 안늦었다. 문제는 3문제였는데 1. 숫자 5개 입력받고 순서상관없이 이어붙일때 중복제거한게 가장 짧을때 출력 2. 전시회에 전시를 가장 오래할 수 있는 날짜 3...

vector로 find해서 찾으려 했는데 뇌과부하 와서 배열로 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include using namespace std; int main(){ int n; int cnt = 0; char voca[101]; //cout n; for(int i=0;i

삽입 정렬 로직1.데이터가 있다. 데이터는 두 개 이상이다.2.두번째 요소부터 마지막 요소까지 돈다.3.n번째 요소는 n부터 1까지 돈다.4.만약 n번째 요소가 n-1번째 요소보다 크면 그만 돈다.5.삽입으로 인해 요소들이 밀린다. O(n^2)의 성능을 보인다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include using namespace std; inline void ShowArray(int arr[],int); void InsertSort(int arr[],int len){ for(int i=1;i0;j--) //j는 i-1번째 원소 { if(arr[j-1]