'자료구조' 태그의 글 목록

2021. 8. 19. 13:15 Algorithm/BOJ

문제 링크 http://icpc.me/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 k번째 수를 가져오는 문제이다. 세그먼트 트리를 만들 때 수의 범위가 아닌 수의 값으로 범위를 정해야 한다. 예를 들어, 5번째 수를 구할 때, 1 ~ N/2에 수가 6개 N/2 + 1 ~ N에 수가 3개가 있다고 한다면 왼쪽 노드로 이동하여 같은 작업을 반복해야 한다. 반면에 1 ~ N/2에 수가 2개 N/2 + 1 ~ N에 수가 5개가 있다고 하면, ..

백준[9345] 디지털 비디오 디스크(DVDs)

2021. 8. 15. 15:18 Algorithm/BOJ

문제 링크 http://icpc.me/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀이할 수 있다. a ~ b 사이에 a, a+1, ... , b 만 존재한다면 이때 최솟값은 a 최댓값은 b이다. 만약 저 구간에 다른 값이 들어간다면 최솟값, 최댓값은 a, b가 될 수 없다. 이 구간 최대, 최소값을 세그먼트 트리로 관리하면 쿼리당 O(logN)에 처리할 수 있다. 코드 #include #include using names..

백준 [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 간선을 만든다. 이것은 위의 설명을 그래프로 나타낸 것이다. 이때 한 ..

백준[4196] 도미노

2021. 7. 28. 18:27 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 풀이 이 문제는 SCC를 이용하여 풀 수 있다. 처음에 이 문제를 보고 아무 점에서나 dfs를 돌려서 dfs를 몇 번 돌리나 카운팅 하면 될 것이라고 생각했다. 하지만 1 -> 2 -> 3 -> 4가 있을 때 1번에서 dfs가 시작하면 문제가 없지만 2, 3, 4번에서 dfs가 시작하면 1번은 처리가 되지 않는다. 그렇기 때문에 SCC를 활용해야한다. 코사라주 알고리즘을 이용하면 stack의 최상단에는..

백준[2150] Strongly Connected Compoment

2021. 7. 28. 14:44 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/2150 풀이 이 문제는 SCC를 구하는 문제이다. 나는 코사라주 알고리즘(Kosaraju's algorithm)을 이용하여 SCC를 구했다. 코사라주 알고리즘은 우선 방향 그래프와 역방향 그래프를 dfs로 탐색하며 진행된다. 1. 방향 그래프를 dfs로 탐색하며 더 이상 갈 수 있는 곳이 없을 때 stack에 push 한다. -이 과정을 모든 정점에 대해 dfs를 진행할 때까지 반복한다. 2. 역방향 그래프를 stack의 top부터 순회하며 이때 만나는 노드들이 SCC다. -이때 top에 있는 정점이 이미 방문한 정점이라면 pop을 한다. https://stonejjun.tistory.com/113 증명은 이 글을 참고하자. 코드 #i..

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

티스토리툴바