복습용

문제 문제는 0부터 9까지 모든 수를 한 번씩 사용해서 다섯자리 정수 2개를 만들때, (0이 앞에오는 4자리수도 O.K.) N으로 나눈 관계에 있는 두 수를 찾으라는 문제이다. 그냥 읽어보면 된다. 반복적 완전 탐색으로 풀 수밖에 없으나 어차피 100000번 이내 for문을 돌리기 때문에 괜찮을 것 같다. 그리고 각 숫자가 다 한번씩 나왔나 체크할 때 bit를 OR하는 기법을 사용했는데 꽤 유명한 기법인 것 같으니까 그것을 기억해두자. 기법의 설명은 주석에 있다. 다음은 코드다. #include int main() { int N,temp,used,c=0; while (scanf("%d",&N) && N != 0) { //if N is defined, range of fghij can be calculat..

문제 덧셈의 minimal cost구하기 문제 Greedy하게 풀린다. 왜 Greedy하게 풀리는지 마지막 step부터 생각해보자. 마지막 step을 생각해보면 두개의 계산된 덩어리를 더할거고 그럼 cost가 발생할거다. 근데 차피 생기는 cost는 덩어리를 어떻게 나누든 동일하다.(주어진 수들의 최종 sum이 되니까) 따라서 두 개의 덩어리는 각각이 optimal cost를 가져야한다. 따라서 각 덩어리에서 max인 계산은 무조건 나중에 돼야한다. 따라서 min인 계산부터 해나가야 하니까 그 때 그 때 보이는 minimum계산부터 해나가면 된다. 이건 비단 마지막 step에만 해당되는게 아니라 어떤 덩어리를 만들었을 때도 동일할거다. 라고 생각했는데 솔직히 왜 Greedy하게 풀리는지 잘 안 와닿는다...

우선 문제를 푸는데 사용한 자료구조인 PQ에 대해 알아보자. PQ는 최소한 다음 작업들이 지원되어야 하는 자료구조를 말한다. 우리는 뭘 해주는지만 알면 된다. 가장 높은 우선순위를 갖는 원소(최대 원소)를 Queue에서 꺼내는 작업 : ExtractMax() 새로운 원소 v를 Queue에 추가하는 작업: Insert(v) 또한, 이런 작업들은 Heap을 이용하여 구현할 시 lgN시간 안에 수행할 수 있다. C++ STL에서 priority_queue라는 이름으로 지원하고 있다. (PQ는 Heap이 아니다. PQ를 Heap을 이용해 구현할 수 있는 개념) STL priority_queue에서 지원하는 작업은 다음과 같다. (0) 정의: priority_queue ex) priority_queue PQ; 구..

문제 중복 원소 개수 세는 문제 input이 ascending order로 되어있어서 set의 find에 걸리는 logN시간이 낭비같아서 N개의 input 배열에 대해서 index 두개 두고 하려니 상당히 overhead가 많다(물론 const겠지만) 그리고 솔직히 귀찮다. 코드는 다음과 같다. #include #include using namespace std; int main() { //N+MlgN solution int N, M,temp,sum; while (cin >> N >> M) { if (N == 0 && M == 0) break; sum = 0; set catalogs; for (int i = 0; i > temp; catalogs.insert(temp); }..

문제 문제는 쉬운데 마지막에 sum을 계산하는 걸 int로 하면 overflow error남 이런 경우는 처음이라 앞으로는 조심해야할듯 #include #include using namespace std; int main() { int N, cases, temp; unsigned long long int sum; while (cin >> N) { if (N == 0) break;//terminal case sum = 0; multiset urn; while (N--) { cin >> cases; for (int i = 0; i > temp; urn.insert(temp); } sum = sum + *(--urn.end()) - *urn.begin(); urn.eras..

문제 영어 별로 안 어려우니까 읽자. 이 문제를 풀 때는 multiset자료구조를 이용하였는데 다음 두가지 이유 때문이다. 1. 매번 싸움마다 원소의 값이 가장 큰 놈을 알아야 한다. (& 그 놈만 알면 된다.) 2. 중복 원소를 허용해야 한다. set은 1에 맞지만 2가 안 되기 때문에 중복 원소 허용의 multiset을 썼다. 주의할 점은 multiset의 erase함수를 value기반으로 사용하면 해당 value를 가진 모든 원소가 지워져버린다. 따라서 key를 기반으로 이 함수를 사용해야 의도한 결과를 낼 수 있다. (의도: 원소 하나만 삭제) 코드는 다음과 같다. #include #include using namespace std; int main() { int N, SG, SB,B,temp; ..

문제 별 잡다한 얘기를 다 붙여놨는데, 주어지는 integer sequence중에서 중복 원소를 포함하지 않는 longest subsequence의 최대 길이를 구하라는 문제다. (nlgn)안에 풀 수 있는 문제다. max_length를 갱신해가는 logic으로 풀었는데 일단 코드는 다음과 같다. #include #include using namespace std; /*Given a sequence of integers, find the length of the longest contiguous subsequence containing no repeated elements. */ int main() { int N; cin >> N; while (N--) { int test,max_length=0,leng..

문제 문제는 N이 주어지고 N명의 학생이 듣는 5개의 수업이 주어진다. 이 때 한 명의 학생은 한 가지의 '수업 조합'을 갖게 된다. ex) 100 101 102 103 488을 듣는 학생은 {100,101,102,103,488}의 '수업 조합'을 갖게 된다. (문제에서 수업의 듣는 순서는 중요하지 않다.) 이 때 어떤 하나의 '수업 조합'이 몇 명의 학생에게서 나오는가를 popularity라 정의하자. 예를 들어 문제의 첫 sample input에서 {100,101,102,103,488}의 popularity는 2이다. 이 때 most popular, 즉 popularity가 가장 큰 수업을 듣는 학생의 수를 구하시오. 풀이) 나는 그냥 어떤 수업의 조합별로 그 수업이 나온 빈도를 체크한다음에 최대인 ..