'Algorithm/BOJ' 카테고리의 글 목록 (8 Page)

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 (..

백준[9084] 동전

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

문제 링크 http://icpc.me/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 dp로 풀이할 수 있다. dp정의는 dp[남은 돈][몇 번째 동전까지 썼는지]로 정의할 수 있다. 코드 #include #include int dp[10004][22], arr[10004], n; int dpf(int money, int coin_idx) { int &ret = dp[money][coin_idx]; if (ret) return ret; if (!money) return 1; fo..

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

백준[3977] 축구 전술

2021. 7. 29. 00:26 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/3977 풀이 이 문제는 코사라주 알고리즘을 이용하여 SCC를 구해서 풀 수 있다. 백준 4196 도미노 와 매우 비슷하다. 도미노 문제와 동일하게 dfs를 돌리며 방문할 노드가 없을 때 스택에 추가하면 stack의 top에는 가장 많은 곳을 갈 수 있는 노드가 위치하게 된다. 그렇기 때문에 stack의 top에 있는 노드를 시작으로 다시 dfs를 돌려 모든 노드를 방문할 수 있는지 판별하고, 만약 모두 방문할 수 있다면 top에 있는 노드의 SCC를 출력하고 그렇지 않다면 Confused를 출력한다. 코드 #include #include #include #include #include using namespace std; 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..

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

티스토리툴바