백준[4354] 문자열 제곱
2021. 7. 9. 15:20
Algorithm/BOJ
풀이 해쉬를 이용하여 풀이할 수 있습니다. abababab라는 문자열이 있다면 이것을 ab/ab/ab/ab -> ABCD라고 표현하자. 만약 ABC와 BCD가 같다면 A = B, B = C, C = D라고 할 수 있고, 이때 A의 4 제곱이라고 할 수 있다. 이 ABC와 BCD가 같은지 확인할 때 해쉬를 이용한다. 이 해쉬코드 값을 빠르게 구하기 위해서는 미리 부분 해쉬 값을 구해 놓는다. phash[i]는 0~i까지의 해쉬값이다. 또한 부분 문자열이 될 수 있는 길이의 후보는 전체 문자열의 길이의 약수들이기 때문에 약수들만 확인한다. 코드 #include #include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 3..
백준[3033] 가장 긴 문자열
2021. 7. 8. 01:49
Algorithm/BOJ
풀이 라빈 카프 알고리즘을 이용하여 풀이할 수 있다. 라빈 카프를 이용하기 위해서는 패턴 문자열의 길이를 알아야 한다. 이것은 길이가 k인 문자열이 2번 반복된다면 항상 길이가 k보다 작은 문자열이 최소한 2번 이상 반복된다는 성질을 이용한다. ex) abcabc에서 abc가 2번 반복된다면 abc의 부분 문자열일 ab도 항상 2번 이상 반복된다. 이 성질을 이용하여 길이를 이분 탐색으로 결정을 한다. 코드 #include #include using namespace std; const int mod = 1e5 + 3; int Mod(long long n) { if (n >= 0) return n % mod; else return ((-n / mod + 1) * mod + n) % mod; } int m..
백준[1786] 찾기
2021. 7. 6. 18:13
Algorithm/BOJ
풀이 kmp알고리즘을 이용하여 풀 수 있다. kmp를 학교 자료구조 시간에 배웠는데 실패 함수 부분이 이해가 안 되어 포기했는데 다시 천천히 생각하니 이해할 수 있었다. 실패 함수도 kmp의 로직과 비슷하게 앞에서 비교한 것을 다시 비교하지 않고 재사용한다. 이해가 안된다면, abacabaac 이 예제로 실패 함수가 어떻게 돌아가는지 생각해보자. 코드 코드는 여기를 참고했다. #include #include #include #include using namespace std; vector getPi(string p) { int m = p.size(), j = 0; vector pi(m, 0); for (int i = 1; i 0 && p[i] != p[j]) j ..
백준[17404] RGB거리 2
2021. 7. 4. 22:23
Algorithm/BOJ
풀이 이 문제는 RGB거리와 똑같이 dp문제지만 이 문제는 마지막 집과 1번 집이 연결되어 있다. 그렇기 때문에 첫 번째 집을 고정시켜 n번째에 첫 번째 색과 같은 경우를 배제시켜야 한다. dp[i][j] = i - 1에서 현재 색이 아닌 경우의 최소 + arr[i][j] (i : 현재 위치, j : 현재 색) 코드 #include #include using namespace std; int arr[1002][3]; int dp[1002][3]; int main() { int n; scanf("%d", &n); for (int i = 1; i
백준[2162] 선분 그룹
2021. 6. 30. 20:19
Algorithm/BOJ
풀이 이 문제는 ccw와 union find를 이용하여 해결 할 수 있다. 두 직선이 교차되었는지 판별은 선분 교차2와 동일하다. 모든 선분들에 대해 서로 교차되었는지 판변하고 교차되었다면 union을 한다. ccw의 리턴값을 1 -1 0이 아닌 원래 값으로 리턴하여, check함수에서 두 값을 곱할 시 오버플로우가 발생할 것을 예상하지 못하고 맞왜틀을 외쳤다. 조심하도록 하자. 코드 #include #include #define x first #define y second using namespace std; using pii = pair; pii a[3003], b[3003]; int par[3003], member_size[3003]; int ccw(pii a, pii b, pii c) { int ..
백준[2533] 사회망 서비스(SNS)
2021. 6. 24. 13:26
Algorithm/BOJ
풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..
백준[1774] 우주신과의 교감
2021. 6. 22. 15:35
Algorithm/BOJ
풀이 방법 크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 코드 우선순위큐를 이용한 구현 #include #include #include #include #include using namespace std; using ll = long long; using pll = pair; using pdll = pair; pll arr[1003]; ll N, M, par[1003], cnt, lev[1003]; priority_queue pq; ll dist(pll a, pll b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (..
백준[4386] 별자리 만들기
2021. 6. 22. 00:39
Algorithm/BOJ
풀이 방법 최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다. 이 풀이는 prim 알고리즘을 이용했다. cf) prim 알고리즘을 모른다면 여기를 참고하세요 코드 #include #include #include using namespace std; using pdd = pair; using pdi = pair; pdd arr[102]; bool visited[102]; priority_queue pq; // 최소 힙 int N; double ans; //점과 점 사이의 거리 double dist(pdd a, pdd b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.secon..
백준[9372] 상근이의 여행
2021. 6. 21. 23:54
Algorithm/BOJ
풀이 방법 spanning tree의 간선의 개수를 구하는 간단한 dfs 문제다. spanning tree의 간선의 개수는 dfs 또는 bfs 탐색 중 사용하는 간선을 모으면 된다. 코드 #include #include #include using namespace std; bool visited[1003]; vector v; int ans; void dfs(int s) { visited[s] = true; ans++; for (auto i : v[s]) { if (!visited[i]) dfs(i); } } int main() { int T; scanf("%d", &T); while (T--) { int N, M; scanf("%d %d", &N, &M); v.clear(); v.resize(N + 1)..
백준[20040] 사이클게임
2021. 6. 21. 23:26
Algorithm/BOJ
풀이 방법 유니온 파인드라는 자료구조를 이용하여 풀이하였다. 입력받은 두개의 루트 노드가 같으면 사이클이 형성되었다고 판단하고, 다르다면 두개의 트리를 합친다. 코드 #include #include using namespace std; int par[500005], level[500005]; int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void merge(int x, int y) { int a = find(x), b = find(y); if (a == b) return; if (level[a] > level[b]) swap(a, b); if (level[a] == level[b]) level[b]++; par[a..