복습용

문제 문제는 요약하면 다음과 같다. 8x8 체스판이 존재할 때 8개의 Queen을 서로 공격할 수 없는 위치에 배치하는 모든 경우의 수를 출력하라. 체스판 채우기 문제다. 완전탐색 문제라서 쉽다고 생각할 수 있지만, Search space를 줄이는게 관건인 테마인 만큼, 쓸데없는 search를 안 하기위해 신경써야한다. ※참고: Queen의 공격 범위는 십자와 대각선상 모든 점 Input: Test case의 개수 TC와 Queen을 반드시 배치해야 하는 (행,렬) 좌표 Output: 양식이 까다로우니 밑의 그림 참고 지금 완전탐색이라는 카테고리를 보고 있는데 이 문제는 그 중에서도 재귀적 퇴각 검색이라는 문제 카테고리에 속한다. 일단 코드부터 보자. 코드는 내가 다 짠 게 아니라 Halim, Steve..

문제 문제는 간단하게. t개의 case가 주어졌을 때 각 case별로 p개의 정수로 된 list가 주어진다. 이 때 list의 부분집합 중 그 합이 n이 되는 경우가 존재하는가? 이 문제를 부분집합 합(subset sum)이라 부르는 경우도 있는데, 기본적으로 all possible subset을 보는 것이 optimal한 문제라고 한다. 이 때 모든 subset을 봐야하는데, 이것을 bit계산으로 매우 빠르게 할 수 있어서 그 방법을 소개한다. #include using namespace std; int main() { int n,t,p, sum,possible; int list[1000];//n> t;//number of test case while (t--) { possible = false;//p..

문제 문제는 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; ..