백준[13511] 트리와 쿼리 2
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] !..
백준[11438] LCA 2
2021. 7. 24. 18:42
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/11438 풀이 LCA 기본 문제이다. 선행 문제인 이 문제는 시간 복잡도가 쿼리당 O(N)으로 풀 수 있었지만 이 문제는 시간 초과가 발생한다. 그렇기 때문에 이 문제는 sparse table을 이용하여 조금 더 최적화를 해야 한다. sparse table은 2^k = 2^(k-1) + 2^(k-1)인 것을 이용하여 모든 정점에서 2^k 만큼 움직이면 어떤 점으로 이용동하는지 dp와 비슷하게 구해놓는다. 이 전처리는 O(NlogN)에 할 수 있다. dp[k][i] : i번째 노드에서 2^k 움직이면 도착하는 노드 // sparse table 코드 for (int k = 1; k 1씩 움직여 O(logN)의 시간 복잡도에 level을 맞..
백준[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
[C++] Structured binding
2021. 7. 21. 11:27
C++
https://en.cppreference.com/w/cpp/language/structured_binding Structured binding declaration (since C++17) - cppreference.com Binds the specified names to subobjects or elements of the initializer. Like a reference, a structured binding is an alias to an existing object. Unlike a reference, a structured binding does not have to be of a reference type. attr(optional) cv-auto ref-q en.cppreference..
백준[1005] ACM Craft
2021. 7. 21. 11:14
Algorithm/BOJ
문제 링크 https://www.acmicpc.net/problem/1005 풀이 위상 정렬과 dp를 이용하여 풀이할 수 있다. 위상 정렬을 이용하여 순서를 찾는 과정에서 dp[nxt] = max(dp[nxt], dp[cur] + dp[nxt])로 특정 노드를 짓기 위한 최소 시간을 구할 수 있다. 코드 #include #include #include #include #include using namespace std; int cnt[1003], dp[1003], cost[1003]; void solve() { memset(cnt, 0, sizeof cnt); memset(dp, 0, sizeof dp); memset(cost, 0, sizeof cost); int n, k; scanf("%d %d", ..
[C++] vector 특정 원소 지우기
2021. 7. 20. 22:50
C++
vector에서 원소 하나를 삭제하는 시간복잡도는 O(N)이다. 값으로 삭제 vector v; 라고 선언된 벡터에서 특정한 원소를 지울 때 아래와 같이 할 수 있습니다. v.erase(remove(v.begin(), v.end(), 지우고 싶은 원소), v.end()); remove는 특정 값을 찾아서 완전히 지우는 것이 아닌, 벡터의 뒤로 보내기 때문에 추가로 erase를 해줘야 한다. #include #include #include using namespace std; int main() { vector v = {1, 2, 3, 5, 10}; cout
2021 SCPC Round 1 후기
2021. 7. 19. 00:33
후기
제주도 스쿠버 일정과 scpc일정과 겹쳐서 4시간 정도밖에 풀지 못했다. 2번까지 풀고 뒷 문제들이 크게 어려워 보이지 않았는데 다음 일정 때문에 못 풀어서 너무 아쉬웠다. 1. 친구들 N명의 사람이 있고, 각 사람은 d를 가지고 있는데 i번째 사람은 i + Di와 친구이다. i + Di > N이면 무시한다. A와 B가 친구라면 B와 A도 친구다. union find를 집합의 개수를 세면 풀 수 있다. 매우 쉬웠고 10분 정도만에 풀 수 있었다. #include #include using namespace std; int Answer; int par[100005], lev[100005]; int find(int x) { if (x == par[x]) return x; return par[x] = find..
백준[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 = ..