한다 공부

에라토스테네스의 체란 무엇일까? 소수를 판단할 때 유용하게 쓰인다. 소수란 1과 자기자신으로만 나누어지는 수이다. 2 3 5 7... 등이 있다. 2부터 생각을 해보자. 2는 소수이다. 2*n배는 소수가 아니다. 그렇다면 2*2, 2*3, 2*4.... 2*(n) 은 모두 소수가 아니므로 제거한다. (코드에서는 bool형 배열을 false함으로써 제거) 그리고 3도 같은 방법으로 3의 배수들을 false한다. 4의 경우 이미 2*2에서 false되었으므로 5를 확인한다. 이런식으로 계산을하면 소수 2 3 5 7..은 남아있고, 소수가 아닌 어떤 수들의 배수들인 4 5 8 9 10... 은 false처리되며 제거된다. 이 방법으로 소수 판정을 하면 O(nlog(log n))만에 가능하다. false로 바꿔..

GCD(Greatest Common Divisor) GCD란 최대공약수를 의미한다. 최대공약수를 구할 땐 유클리드 호제법을 이용하는게 편하다. 유클리드 호제법이란, a b의 최대공약수가 a%b(나머지) b의 최대공약수가 같다는 것을 이용하는 것이다. 예를 들어 15와 10이 있다고 해보자. a=15, b=10이라고 하면 a%b=5, b=10이 된다. 이 a%b값을 a에 대입하자. x%y를 할 때에는 x>y여야하므로 둘의 자리를 바꿔줘야한다 그러면 a=10, b=5가 된다. 나머지가 0이 될 때까지 해보자. a%b=5, b=5가 된다. a%b를 a에 대입하면 a=5, b=5가 되고 a%b = 0이 된다. 0이 되면 작은 값인 b를 리턴한다. 그러면 최대공약수가 b값, 즉 5가 된다 예를 들어 7과 3이 있..

수학시간에 하던 combination, 조합을 구하면 된다. 재귀함수 등 풀이법은 많은 것 같지만 나는 while문과 for문을 썼다. 어렵지 않게 풀었다. #include using namespace std; int main() { int n, k, temp;; cin >> n >> k; temp = k; int a = 1; while (temp--) { a = a * n; n--; } int b = 1; for (; k > 0; k--) { b = b * k; } cout

다른 사람들이 신청한 마일리지를 temp라는 최소 힙으로 담았다. 만약 3명만 수강신청 가능할 때, 5명이 신청을 했다고 해보자 마일리지를 5 10 15 20 25를 담았다고 치면 이를 최소 힙 temp 에 담아서 정렬한다. 그리고 내가 신청을 하기 위해, 오버된 만큼을 힙에서 pop 시킨다. 5-3, 즉 2만큼 pop해보자 15, 20, 25 만 남았다! 같은 마일리지를 할당해도 내가 우선시 되므로 15, 20, 25 할당된 수업에서 내가 수강신청하려면 15만 할당해도 된다. [결론] 1. 인원이 널널하면 마일리지를 1만 할당, 최소힙 q에 1을 담는다. 2. 5명 신청가능한데 5명이 신청한 경우, 최소힙temp에 5명의 마일리지를 넣어서, 최소 마일리지 넣은 애를 구하고, 최소 만큼만 내가 할당한다...

이 문제를 풀기 위해 음수 힙과 양수 힙, 두개를 선언했다. 최소 힙 두개를 만들었는데, priority_queue p; 를 이용하면 최소 힙으로 만들 수 있다. 이 때 vector 는 include 하지 않아도 되고, push와 pop 같은 연산은 priority_queue p; (최대 힙) 을 이용할 때 처럼 p.pop(); 등 으로 해주면 된다. #include #include using namespace std; int main() { //p에는 양수인 것들을 최소 힙으로 저장 //m에는 음수인 것들의 절댓값을 최소 힙으로 저장 priority_queue p; priority_queue m; int n; cin >> n; int q; int k; while (n--) { cin >> q; if (..

문제가 많이 긴데 결론은 문자열을 자바스타일에서 c++스타일로, 혹은 그 반대로 변환하면 되는 문제다 c++ 스타일의 문자열은 소문자와 언더바로 구성되는데 이 언더바가 오류를 많이 발생시킨다. _c도 에러 (시작이 언더바) c_도 에러 (마지막도 언더바) c__c도 에러다. (언더바가 두 번 나와도 에러) #include using namespace std; string ctoj(string name) { string j; for (int i = 0; i < name.length(); i++) { if (name[i] == '_') { j += name[i + 1] - 32; i++; } else j += name[i]; } return j; } string jtoc(string name) { strin..

알고리즘 분류를 보니 비트마스킹이라고 되어있었다 하지만 비트마스킹이 익숙하지 않아서 set을 이용했다 아니나 다를까 나타나는 시간초과 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 를 이용해서 cin과 cout의 시간을 단축시키자 그리고 all 명령어를 받으면 기존 set 내용을 지우고 set에 1~20값을 새로 넣어야한다 이때 for문 쓰면 시간초과 뜬다 직접 값을 넣기로 하자... #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); set s; int n; cin >> n; string str;..

스택의 대표적인 예제 후위표기식 문제이다. 처음에는 문자열 받는 스택 따로, num 받는 스택 따로 받으려고 했다 그러면 미지수 나올 때 마다 num[i++]시켜서 다음 숫자 꺼내오면 된다고 생각함 그런데 알파벳이 두 번 연속으로 나올 수 있다 그럴 땐 i++하면 낭패.... 인덱스와 알파벳을 연결해줘야한다. 어차피 알파벳은 A->B->C .... 순서대로 나오므로 엇갈일 일은 없다 첫번째 받는 변수를 (인덱스0) A라고 생각하고 두번째 받는 변수는 (인덱스1) B라고 생각... 이렇게 진행하면 된다. 그럼 인덱스 찾기도 쉽다 A의 인덱스는 0이다. B의 인덱스는 'B'-'A'=1이다. 즉 원하는 인덱스는 str[i]-'A'이다. str[C]=123 (예시) 이런식으로 값이 있는 것임 인덱스만 알면 값은..

20920번 문제 영단어 암기는 괴로워 괴롭다 정말 이 문제는 시간제한이 매우 짧다. 처음에는 pair만을 이용해서 전체를 비교하고 정렬했었는데 시간초과가 떴었다... 이를 해결하려면 map을 이용해야한다. map은 트리구조에다가... 자동으로 정렬이 되기 때문에 내가 원하는대로 정렬시키기가 매우 힘들다 다른 사람들은 어떻게 풀었나 찾아본 결과 1. map을 전역변수로 선언해서 정렬 2. map 내용을 pair에 복사해서 정렬 크게 이렇게 두 가지 방법이 있었다. 나는 2번으로 풀었었다 이 방법 저 방법 다 해보느라 시간 참,,, 많이 쓴 문제.. #include #include #include //sort #include #include //pair using namespace std; //문제에 주어..

덱은 자료구조 정리 카테고리에 정리를 해뒀다. [C] 큐 : 선형큐, 원형큐, 덱 c++ STL 함수를 정리하기 좋은 문제 #include #include using namespace std; int main() { deque d; string str; int n, num; cin >> n; while (n--) { cin >> str; if (str == "push_front") { cin >> num; d.push_front(num); } else if (str == "push_back") { cin >> num; d.push_back(num); } else if (str == "pop_front") { if (d.empty()) cout