15829. Hashing - C++
https://www.acmicpc.net/problem/15829
내 풀이 - 성공
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#define MAXN 105
#define M 1234567891
#define r 31
using namespace std;
int L;
string str;
long long ans;
int main()
{
//freopen("sample_input.txt", "r", stdin);
cin >> L;
cin >> str;
ans = 0;
long long rr = 1;
for (int i = 0; i < L; i++) {
ans = (ans + (str[i] - 'a' + 1) * rr) % M;
rr = (rr * r) % M;
}
cout << ans;
return 0;
}
여기서 중요한 것은 MOD 이다.
1 <= L <= 5 의 범위인 SMALL(50점) 까지는 크게 신경 쓰지 않아도 통과 가능하지만
1 <= L <= 50 의 범위인 Large(50점) 까지는 MOD 를 주의해야한다.
a * r 을 더할 때마다 MOD 를 해줘야하며
31 의 배수도 급격히 커지기 때문에 MOD 가 필요하다.
이 때, 둘 다 기존의 ans 값과 rr 값을 포함해서 MOD 해야한다.
포함하지 않는 경우
ans += ((str[i] - 'a' + 1) * rr) % M;
rr *= r % Mod;=> X
비둘기집의 원리
n 개의 비둘기집과 n+1 마리의 비둘기가 있다고 가정한다.만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면,
전체 비둘기집에는 많아야 n 마리의 비둘기가 존재한다.그런데 비둘기는 모두 n+1 마리이므로, 이것은 모순이다.
따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.
- 해시 충돌
: 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다.
11723. 집합 - C++
https://www.acmicpc.net/problem/11723
내 풀이 - 성공
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#define MAXM 3000005
using namespace std;
int M, x;
string str;
long long X;
long long maxX;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("sample_input.txt", "r", stdin);
maxX = ~(1 << 21);
cin >> M;
for (int i = 0; i < M; i++) {
cin >> str;
if (str == "add") {
cin >> x;
X = X | (1 << x);
}
else if (str == "remove") {
cin >> x;
X = X & ~(1 << x);
}
else if (str == "check") {
cin >> x;
if (X & (1 << x)) cout << 1 << "\n";
else cout << 0 << "\n";
}
else if (str == "toggle") {
cin >> x;
if (X & (1 << x)) X = X & ~(1 << x);
else X = X | (1 << x);
}
else if (str == "all") {
X = ~(X << 21);
}
else {
X = 0;
}
}
return 0;
}비트마스킹 이용
X 라는 숫자에 x 번째 값이 있으면 1, 없으면 0 으로 설정
추가: X | (1 << x)
삭제: X & ~(1 << x)
확인: X & (1 << x)
cin, cout 사용 시, 시간초과가 될 수 있는데
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);코드를 필수로 넣어주면 통과된다
내 풀이 2 - 성공
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#define MAXM 3000005
using namespace std;
int M, x;
char a[10];
long long X;
long long maxX;
int main()
{
//freopen("sample_input.txt", "r", stdin);
maxX = ~(1 << 21);
scanf("%d", &M);
for (int i = 0; i < M; i++) {
scanf("%s", a);
string str = a;
if (str == "add") {
scanf("%d", &x);
X = X | (1 << x);
}
else if (str == "remove") {
scanf("%d", &x);
X = X & ~(1 << x);
}
else if (str == "check") {
scanf("%d", &x);
if (X & (1 << x)) printf("1\n");
else printf("0\n");
}
else if (str == "toggle") {
scanf("%d", &x);
if (X & (1 << x)) X = X & ~(1 << x);
else X = X | (1 << x);
}
else if (str == "all") {
X = ~(X << 21);
}
else {
X = 0;
}
}
return 0;
}같은 비트마스킹이지만
cin, cout 대신 scanf, printf 를 사용
내 풀이 3 - 성공
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#define MAXM 3000005
using namespace std;
int M, x;
string str;
bool X[21];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("sample_input.txt", "r", stdin);
cin >> M;
for (int i = 0; i < M; i++) {
cin >> str;
if (str == "add") {
cin >> x;
X[x] = 1;
}
else if (str == "remove") {
cin >> x;
X[x] = 0;
}
else if (str == "check") {
cin >> x;
if (X[x]) cout << 1 << "\n";
else cout << 0 << "\n";
}
else if (str == "toggle") {
cin >> x;
if (X[x]) X[x] = 0;
else X[x] = 1;
}
else if (str == "all") {
memset(X, 1, sizeof(X));
}
else {
memset(X, 0, sizeof(X));
}
}
return 0;
}숫자는 1 ~ 20 으로 제한되어 있으므로 21 크기의 배열을 만들어서 사용
값이 1 이면 존재, 0 이면 존재X
all 이나 empty 는 memset 으로 한번에 초기화 해줬다
비트마스킹보다 느리다
Hello, World!