한다 공부

2108번: 통계학 (acmicpc.net) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 산술평균의 경우 반올림값을 유의한다 2. 중간값의 경우, 입력 갯수가 홀수이므로 어렵지 않다 3. 최빈값의 경우, pair에 넣어서 빈도수를 비교하고 재정렬한다 4. 범위의 경우 차의 절댓값을 이용한다 최빈값이 까다롭지만 pair를 이용한다면 비교하기 수월하다. 이 문제는 함수를 많이 만드는 바람에 return을 자꾸 깜빡해서 런타임 에러가 많이 났었다 ㅠ #include #include #include #include #in..

정답은 map으로 저장하고 학생의 답은 vector로 저장했다. 정답을 o[a]=0 o[b]=1 o[c]=2 으로 저장하고 학생의 답을 x[0]=a, x[1]=c, x[2]=b 로 저장을 했으니 정답의 맵의 key에 vector의 요소를 넣어주고 value의 크기를 비교해주면 된다. #include #include #include using namespace std; int main() { map o; vector x; int n, temp; cin >> n; temp = n; //정답 map으로 저장 string s; while (temp--) { cin >> s; o[s] = n - temp; } //학생의 답 vector로 저장 temp = n; while (temp--) { cin >> s; x...

1. 테두리가 성립하는 모든 경우의 수를 구한다. 2. 해당 테두리로 사각형을 만들었을 때, 입력한 안쪽 벽돌의 갯수가, 만들어진 사각형의 내부 갯수와 같은지 확인한다. 테두리를 구하는 방법은, 가로길이 * 2 + 세로길이 *2 를 한 다음 겹치는 모서리 4개를 빼줘도 된다. 나는 가로길이 *2 + (세로길이-2) * 2 를 했다. i = 가로 j = 세로 인데, 가로의 범위와 세로의 범위는 주석에 적어뒀다. #include using namespace std; int main() { int r, b; cin >> r >> b; int l, w; //i의 범위 // 세로 길이가 가장 짧은게 3이다. // 이 경우 가로와 겹치지 않은 세로 벽돌은 2개 뿐임. //따라서 2개를 빼주고 위와 아래 2개가 있으..

브루트 포스란 무엇인가? 모든 경우의 수를 다 해보는 것이다. 이런 단순한 방법이 때로는 가장 합리적인 방법일 수도 있다. #include #include using namespace std; vector num; //삼각수를 벡터에 push_back void calc() { int sum = 0; int k = 1; while (sum < 1000) { sum += k; num.push_back(sum); k++; } } //세 삼각수의 합이 입력한 수이면 true 리턴 bool check(int n) { bool c = false; for (int i = 0; i < num.size(); i++) { for (int j = 0; j < num.size(); j++) { for (int k = 0; k..

에라토스테네스의 체란 무엇일까? 소수를 판단할 때 유용하게 쓰인다. 소수란 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..