'알고리즘' 태그의 글 목록 (2 Page)

2021. 7. 25. 19:02 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/13511 풀이 LCA를 이용하여 풀이할 수 있다. 백준 LCA2를 이해했다고 가정하고 설명하겠다. 1번 출력은 간단하다. dist[i]를 루트로부터 거리라고 할 때 dist[u] + dist[v] - 2*dist[LCA(u, v)]를 구하면 된다. 그림을 그려본다면 쉽게 이해할 수 있을 거다. 2번 출력은 u와 LCA사이에 있는 정점인지 v와 LCA사이에 있는 정점인지 판별한 후 부모 노드로 이동하면 된다. 코드 #include #include using namespace std; using ll = long long; using pll = pair; vector v[100005]; ll par[22][100005], lev[10000..

백준[3176] 도로 네트워크

2021. 7. 25. 16:56 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/3176 풀이 이 문제는 LCA를 이용한 문제이다. 쿼리당 O(logN)에 LCA를 처리하는 방법을 모른다면 LCA2부터 공부하는 것이 좋다. 이 글은 LCA2를 모두 이해했다고 가정하고 설명하겠다. 이 문제는 LCA를 구하는 과정에서 부분 최댓값과 최솟값을 O(1)에 구할 수 있어야 한다. 그러기 위해서는 sparse table을 이용하여 전처리를 해줘야 한다. 나는 여기와 여기를 보고 공부했다. 부분 최댓값과 최솟값을 구하는 전처리 코드는 아래와 같고 O(NlogN)에 처리할 수 있다. for (int j = 1; j = 0; i--) { if (lev[y] - lev[x] >= (1 = 0; i--) { if (par[x][i] !..

백준[17435] 합성함수와 쿼리

2021. 7. 23. 17:32 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 풀이 sparse table이라는 자료구조를 이용하여 풀이할 수 있다. sparse table은 https://namnamseo.tistory.com/entry/Sparse-Table 이 자료를 보고 공부했다. sparse table을 이용하여 2^k..

백준[3584] 가장 가까운 최소 공통 조상

2021. 7. 23. 16:32 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/3584 풀이 LCA(Lowest Common Ancestor) 기본 문제다. 최소 공통 조상은 트리에서 어떤 두 정점이 같은 가장 가까운 조상을 의미한다. 최소 공통 조상을 구하기 위해서 각 노드의 깊이를 저장해 놓는다. 그 후 a, b의 공통 조상을 찾는다고 한다면 a와 b의 깊이를 동일하게 맞춘 후 둘 다 한 칸씩 조상으로 이동하며 서로 같은지 확인하면 조상이 일치한 지 확인할 수 있다. 시간 복잡도는 O(depth)이다. cf) 이 문제는 단방향 그래프이므로 루트 노드를 따로 찾아줘야 한다. 코드 #include #include #include using namespace std; vector v[10004]; int par[10..

백준[1766] 문제집

2021. 7. 22. 11:58 Algorithm/BOJ

풀이 위상 정렬을 이용하여 풀이할 수 있다. 위상 정렬을 이용하는 과정에서 더 쉬운 문제는 더 빨리 뽑기 위해 우선순위 큐를 이용하여 값이 작은 것을 우선으로 뽑아준다. 코드 #include #include #include using namespace std; int cnt[32003]; vector v[32003]; priority_queue q; // 작은 것부터 뽑음 int main() { int N, M; scanf("%d %d", &N, &M); while (M--) { int a, b; scanf("%d %d", &a, &b); v[a].push_back(b); cnt[b]++; } for (int i = 1; i

백준[5670] 휴대폰 자판

2021. 7. 13. 15:35 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/5670 풀이 트라이를 이용하여 풀이할 수 있다. 어느 지점까지 입력하였을 때 나올 수 있는 경우의 수가 1인 경우 자동으로 입력을 해줘야 한다. 그러기 위해서 자식 노드의 수가 1개인 경우에 자동 입력을 해야 한다. 또한 hello hell와 같이 문자열의 앞부분이 동일한 경우에 hello를 입력하기 위해서는 hell을 입력하고 o를 한번 더 입력해야 한다. 이 경우는 자식 노드가 1개이며 문자열이 끝나는 경우 한번 더 입력하게 한다. Trie 구조체의 멤버로 Trie *nxt[26]으로 한번 구현하고 최적화를 위해 map으로 한번 더 구현했다. 코드 최적화x #include #include struct Trie { bool finis..

백준[14425] 문자열 집합

2021. 7. 13. 02:40 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이 stl의 set을 이용하여 아주 간단하게 풀이할 수 있는 문제다. 하지만 trie를 공부하기 좋은 문제이므로 trie를 이용한 풀이도 해봤다. 코드 트라이 #include #include #include using namespace std; struct Trie { bool finish; Trie *child[26]; Trie() : finish(f..

백준 [14725] 개미굴

2021. 7. 12. 22:42 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 풀이 trie를 이용하여 풀이할 수 있다. trie를 구현할때 string을 인덱스로 하고 값은 Node구조체로 하기 위해 map을 이용한다. 코드 #include #include #include #include using namespace std; struct Node { map child; }; void insert(Node &node, vector &arr, int ..

백준[10266] 시계 사진들

2021. 7. 12. 14:04 Algorithm/BOJ

풀이 z알고리즘을 이용하여 풀이할 수 있다. 정수의 범위로 배열을 만들고 입력받는 숫자를 인덱스로 하여 그 부분을 1로 만들고 첫 번째 배열에서 두 번째 배열이 있는지 확인하는 문제다. 이때 시계가 원형이기 때문에 a를 2번 이어 붙인 배열의 부분 배열에 b배열이 있는지 찾는다. cf) 배열을 이어 붙일 때 편의를 위해 배열을 string으로 만들어 + 연산자를 사용했다. 코드 #include #include using namespace std; const int MAX = 360000; string a, b; int Z[3 * MAX + 5]; void getZ(const string &str) { int L = 0, R = 0; int N = str.size(); for (int i = 1; i < ..

백준[13506] 카멜레온 부분 문자열

2021. 7. 11. 22:27 Algorithm/BOJ

풀이 z알고리즘을 이용하여 풀이했습니다. prefix이면서 suffix이고 그 위치가 아닌 곳에서 한번 더 나와야 합니다. 이 조건을 만족하려면 Z[N-i] = i 이면 prefix이면서 suffix이고 중간 위치에 한번 더 나오기 위해서 Z[j] >= i (0 > s; int N = s.size(); int L = ..

백준[2252] 줄 세우기

2021. 7. 10. 20:13 Algorithm/BOJ

풀이 위상 정렬을 이용하여 풀이할 수 있다. 코드 #include #include #include using namespace std; int cnt[32003]; int main() { int N, M; scanf("%d %d", &N, &M); vector v(N + 1); while (M--) { int a, b; scanf("%d %d", &a, &b); v[a].push_back(b); cnt[b]++; } queue q; for (int i = 1; i

백준[1305] 광고

2021. 7. 10. 19:42 Algorithm/BOJ

풀이 kmp의 실패 함수를 이용하여 풀이할 수 있다. 전체 문자열 길이를 L, 실패함수 배열을 pi (pi는 0 인덱스부터 시작)라 하면 L - pi[L-1]로 문제의 정답을 구할 수 있다. abcdab라는 문자열이 있을 때 pi[L-1]은 2이고 이 수는 반복되는 패턴 문자열인 abcd가 끝나고, 패턴 문자열 앞부분 ab 2 글자가 패턴 문자열에 붙은 거라고 볼 수 있다. 코드 #include char s[1000006]; int pi[1000006], L; int main() { scanf("%d %s", &L, s); int j = 0; for (int i = 1; i 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]..

백준[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 ..

티스토리툴바