'백준' 태그의 글 목록 (7 Page)

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개가 있다고 하면, ..

백준[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)에 처리할..

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

백준[1517] 버블 소트

2021. 8. 11. 01:53 Algorithm/BOJ

문제 링크 http://icpc.me/1517 풀이 세그먼트 트리를 이용하여 풀이 할 수 있다. i > j이면서 arr[i] j를 만족하는 것의 개수만 카운트 하면 된다. 코드 #include #include using namespace std; using ll = long long; pair arr[500005]; ll tree[2000006], ans; ll query(int cur, int s, int e, int qs, int qe) { if (e < qs || qe < s) return 0; if (qs 1; ll left..

백준[16991] 외판원 순회 3

2021. 8. 10. 15:33 Algorithm/BOJ

문제링크 http://icpc.me/16991 풀이 비트마스크를 이용한 dp문제이며 외판원 순회와 다를 게 없다. 코드 #include #include #include using namespace std; using pii = pair; pii arr[17]; double dp[17][1

백준[3648] 아이돌

2021. 8. 6. 10:16 Algorithm/BOJ

문제 링크 http://icpc.me/3648 풀이 SCC를 응용한 2-SAT으로 문제를 해결할 수 있다. 2-SAT을 모른다면 BOJ 2-SAT - 3를 참고해라. 코드 #include #include #include #include using namespace std; vector v, rev; stack s; bool visited[2003]; int scc[2003], idx, n, m; inline int T(int x) { return x

백준[5557] 1학년

2021. 8. 4. 23:32 Algorithm/BOJ

문제 링크 http://icpc.me/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 dp를 이용하여 해결할 수 있다. dp[i][j] : j번째 숫자까지 봤을 때 숫자 i를 만들 수 있는 최댓값으로 정의할 수 있다. 코드 #include using ll = long long; ll dp[22][102], arr[102], n; ll dpf(ll cur, ll idx) { if (cur 20) return 0; ll &ret = dp[cur][idx]; if (re..

백준[2225] 합분해

2021. 8. 4. 22:49 Algorithm/BOJ

문제 링크 http://icpc.me/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp [남은 수][뺄 수 있는 횟수]로 정의할 수 있다. 코드 #include using ll = long long; ll dp[202][202], N, K; const ll mod = 1e9; ll dpf(ll n, ll k) { ll &ret = dp[k][n]; if (ret) return ret; // 남은 수와 뺄 수 있는 횟수가 0일때 1리턴 if (!n && !k) return 1; // 뺄 수 있는 횟수는 끝났는데 수가 남아있을 때 0리턴 if (n && !k) return 0; for (..

백준[1915] 가장 큰 정사각형

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

문제 링크 http://icpc.me/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 dp로 해결할 수 있다. dp 점화식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]), (i, j는 배열 인덱스)로 정의할 수 있다. 위의 그림과 같은 예제가 있을 때 (2, 2) 인덱스에서 한 변의 길이가 2인 정사각형이 만들어지기 위해서는 왼쪽, 위, 왼쪽 위 가 모두 1이어야 한다. 이 말을 바꿔 말하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 1 이어야 한다. (5, 5)에서 한 ..

백준[2602] 돌다리 건너기

2021. 8. 3. 13:13 Algorithm/BOJ

문제 링크 http://icpc.me/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp는 dp[악마다리 or 천사다리][몇 번째 패턴 문자까지 발견][몇 번째 돌다리까지 갔나]로 정의할 수 있다. 코드 #include #include using namespace std; int dp[2][22][100]; string pat, a, b; int dpf(int up_down, int pat_num, int cur_num) { int &ret = dp[up_down][pa..

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

백준[4013] ATM

2021. 7. 30. 16:28 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/4013 풀이 SCC, 유니온 파인드, 위상 정렬, dp를 이용하여 풀이하였다. 다 푼 후에 다른 사람의 코드를 보고 깨달았지만, 유니온 파인드는 굳이 사용하지 않아도 된다. 출발지점부터 순회하며 dp를 돌리면 될 것 같지만 사이클이 존재하기 때문에 그럴 수 없다. 그렇기 때문에 사이클이 없는 방향 그래프로 바꿔줘야 한다. 사이클을 제거하기 위해 SCC를 사용한다. 아래 코드는 코사라주 알고리즘을 이용하였다. 구해진 SCC를 이용하여 사이클을 하나의 큰 노드로 합친다. 나는 이때 유니온 파인드를 사용하였다. 하지만 이미 SCC들을 모두 구했기 때문에 이미 합쳐져 있는 상태여서 유니온 파인드를 사용하지 않아도 된다. scc vector의 ..

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

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

티스토리툴바