'PS' 태그의 글 목록

2021. 8. 19. 18:01 Algorithm/BOJ

문제 링크 http://icpc.me/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 풀이 이 문제를 응용하여 풀 수 있는 문제다. x = k라 할 때 처음엔 x번째 수를 제거하고 그다음은, x + k-1번째 수를 제거하고 다음은 x + 2*(k-1) 번째를 제거는 과정을 계속해서 반복한다. 이때 x + i(k - 1)이 남은 수의 개수보다 크다면 x + i(k-1) % (남은 수의 개수)를 취한다. 하지만 그 값이 0이 되면 안 되기 때문에 남은 수의 개수로 나누어 떨어질 때는 x = (남은 수의 개수)로 만든다. cf) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출..

백준[16975] 수열과 쿼리 21

2021. 8. 16. 17:35 Algorithm/BOJ

문제 링크 http://icpc.me/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 1 세그먼트 트리의 구간 업데이트를 하는 lazy propagation을 이용하여 풀이할 수 있다. lazy propagation에 대한 자세한 설명은 여기와 여기를 참고해라. 풀이 2 lazy propogation을 사용하지 않고, 세그먼트 트리만을 이용하여 풀이할 수도 있다. 아래 그림과 같이 업데이트하는 방식과 쿼리를 리턴하는 방식을 기존과 반대로 하면 구간 업데이트에 대해 O(logN)에 처리할..

백준 [11280] 2-SAT - 3

2021. 8. 2. 22:38 Algorithm/BOJ

문제 링크 http://icpc.me/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 풀이 이 문제는 SCC를 구하기 위해 코사라주 알고리즘을 이용한다. (xi V xj)가 항상 참이기 위해서는 xi 가 거짓이라면 xj는 항상 참이어야 한다. 또한 반대로 xj 가 거짓이라면 xi는 항상 참이어야 한다. 그렇기 때문에 not(xi) -> xj와 not(xj) -> xi 간선을 만든다. 이것은 위의 설명을 그래프로 나타낸 것이다. 이때 한 ..

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

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

티스토리툴바