PS 일지

정의방향 그래프에서, 모든 정점들이 서로 도달 가능한 최대 부분 그래프⇒ SCC 내 임의의 정점 $u,v$에 대해, $u \rightarrow v$경로와 $v \rightarrow u$경로가 모두 존재특성모든 방향 그래프는 하나 이상의 SCC로 분해될 수 있음SCC들은 서로 겹치지 않음 (SCC 정의가 최대 부분 그래프이기 때문)모든 정점은 정확히 하나의 SCC에 속함방향 그래프의 SCC들을 하나의 정점으로 압축하면 DAG가 됨.SCC 찾기코사라주 알고리즘각 정점에 DFS Finishing Time을 기록Finishing Time ⇒ 오일러 경로 테크닉에서 out time의 개념과 동일함모든 간선의 방향을 뒤집은 전치 그래프에서, 탐색 종료의 역순으로 정점을 방문하여 생긴 DFS 트리가 하나의 SCC가 ..

문제https://www.acmicpc.net/problem/9328여러 요소들로 이루어진 2차원 격자가 주어진다. 존재하는 요소는 벽$($*$)$, 빈 공간$($.$)$, 문서$($$\$)$, 문$($알파벳 대문자$)$와 각 알파벳에 대응하는 열쇠$($알파벳 소문자$)$들이 있다.상하좌우로 인접한 칸으로만 이동할 수 있고, 경계에 존재하는 빈 공간으로 격자 안과 밖을 오갈 수 있을 때, 얻을 수 있는 문서 개수의 최댓값을 구하는 문제이다. 풀이갈 수 있는 곳들에서 열쇠를 새로 먹어주고, 먹은 열쇠로 열 수 있는 문을 찾아 갈 수 있는 곳을 확장시켜주는 작업을 계속 반복한다.더이상 변화가 생기지 않을 때까지 이를 반복하고, 그 때까지 모은 문서의 수를 출력해주면 된다. import java.util.*;..

문제https://www.acmicpc.net/problem/28060, 1로만 이루어진 길이 $N$인 1-based index 수열 $S$에, $1 \le i \le N$을 골라서 아래 두 가지 연산을 할 수 있다.1. $S[i] = S[i] \oplus 1$2. $S[1] = S[1] \oplus 1, \cdots, S[i] = S[i] \oplus 1$$ \oplus $는 exclusive or를 의미한다.모든 원소를 $0$으로 만드는 데 필요한 최소 연산 횟수를 구하는 문제이다.풀이$1$인 원소를 $0$으로 만드는 방법에는 아래 것들이 존재한다.1. 모든 원소 $1$에 대해, 1번 연산 수행하기2. 특정 구간 $[l,r]$의 원소가 모두 $1$일 때, 2번 연산을 각각 $i = l-1, i=r$로..

문제https://www.acmicpc.net/problem/147160과 1로만 이루어진 2차원 격자가 주어진다.1이 격자 상에서 인접한 8방향으로 연결되어있다면 연결 요소 전체를 한 글자로 볼 때,총 연결 요소의 수를 구하는 문제이다. 풀이격자를 순회하며 1을 만날 때마다 BFS로 연결 요소를 모두 방문처리한 후 글자 수를 올려주었다. import java.util.*;import java.io.*;class Node{ int x; int y; Node(int x, int y){ this.x = x; this.y = y; }}public class Main { static StringTokenizer st; static int nextInt()..

문제https://www.acmicpc.net/problem/17471정점이 $N$개이고, 정점에 양의 정수 가중치가 있는 그래프가 주어진다. 이 그래프의 정점들을 서로 겹치지 않게 두 집합으로 분할하여 각 집합 내의 정점들끼리 연결되도록 하였을 때, 두 집합의 가중치 합 차이의 최솟값을 구해야 한다. 풀이재귀 + 비트마스킹을 이용해 가능한 두 집합을 완탐으로 구해주었다.두 집합이 정해지면, 분리 집합으로 집합 내의 연결 여부를 확인하고 답을 구해주었다. #include #include #include #include using namespace std;int r[10]{}, s[10]{}, N;int f(int x) { return x == r[x] ? x : r[x] = f(r[x]); }int an..

문제https://www.acmicpc.net/problem/12928정수 $N$과 $S$가 주어지면, 정점의 개수가 $N$개이며 길이가 $2$인 단순 경로의 수가 $S$개인 트리를 만들 수 있는지 판별하는 문제다. 두 경로가 서로 방향만 다르고 지나는 점이 동일하면 같은 경로이다. 풀이정점의 개수가 $n$개이고 길이가 $2$인 단순 경로의 수가 $s$개인 트리가 있다고 가정하자.이 트리에서 차수가 $k$인 정점에 새 정점을 이어붙이면, 단순 경로의 수는 $s+k$가 된다.구체적으로, 정점의 수가 $n$이고 길이가 $2$인 단순 경로의 수가 $s$이며, 차수가 $k$인 정점이 존재하는지 여부는 배낭으로 쉽게 알 수 있다. 위 정의대로 $d[n][k][s]$를 정의하면, $d[n][k][s] = 1$일 때..

문제https://www.acmicpc.net/problem/23594정점이 $N$개인 그래프를 구성하려 한다.그래프 상에서 서로 이동 가능해서는 안되는 정점 쌍이 $K$개 주어지고, 그래프에 사용할 후보 간선이 $M$개 주어진다.후보 간선들을 주어진 순서대로 하나씩 보면서, 그래프 상에 존재해도 되는 간선이면 사용하고 그렇지 않다면 그냥 넘어간다.이 때, 사용되는 간선들을 모두 구해야 한다.풀이각 정점별로, 해당 정점에서 갈 수 있는 정점들의 목록 $V$와, 해당 정점으로부터 도달해서는 안되는 정점의 목록 $S$를 정의하고 관리해보자. 후보 간선들 중, 현재 보고있는 간선을 $(a,b)$라고 하자.정점 $a$와 $b$가 그래프 상에서 이미 서로에게 도달 가능한 상태이면, 해당 간선은 당연히 사용 가능하..

문제https://www.acmicpc.net/problem/13215길이가 $N$인 수열 $A$와 정수 $K$가 주어지면, $1 \le l \le r \le N$이면서 $\sum \limits_{i=l}^{r} {A[i]} \ge K$인 $(l,r)$ 쌍의 수를 구하는 문제이다. 풀이$l = 1$인 쌍의 수를 어떻게 구할 지부터 생각해보자.$S[i] = S[i-1] + A[i]$ $(i > 1)$ 라고 정의하면, $S[i] >= K$인 $i$의 개수가 된다. 그럼, $l = 2$인 쌍의 수는 어떻게 구할까?기존의 배열 $S$에서 $S[1]$을 삭제하고, 모든 원소에 $A[1]$씩 뺀 후 $K$ 이상인지 검사하면 된다.거꾸로 생각하면, 기존의 배열 $S$에서 $S[1]$을 삭제하고, $K + A[1..

문제https://www.acmicpc.net/problem/20127 길이가 $N$인 수열 $A$가 주어지면,앞의 $K$개 원소를 맨 뒤로 옮겨서 단조수열을 만들 수 있는지 판단하고 가능하다면 $K$의 최솟값을 찾아야 한다.풀이증가하는 횟수를 누적한 배열 $P$와, 감소하는 횟수를 누적한 배열 $Q$를 생각해보자. $P[i] = P[i-1] + \begin{cases} 1 & A[i] - A[i-1] \geq 0 \\ 0 & \text{otherwise} \end{cases}$ $Q[i] = Q[i-1] + \begin{cases} 1 & A[i] - A[i-1] \leq 0 \\ 0 & \text{otherwise} \end{cases}$ 우선, $P[N]$ 혹은 $Q[N]$이 $N$과 같다면 답은 ..

문제https://www.acmicpc.net/problem/13244 그래프가 주어지면, 트리인지 아닌지 판별하는 문제다.multiedge가 주어질 수 있다는 점에 유의해야 한다.풀이트리인지 판별하는 가장 간단하고 쉬운 방법은 분리 집합을 이용하는 것이라 생각한다.union 연산이 정확히 N-1번 발생함과 동시에 간선의 개수가 N-1개라면, 주어진 그래프는 트리이다. #include #include #include using namespace std;int main() { cin.tie(0)->sync_with_stdio(0); int T, N, M, a, b, r[1001]{}; function f = [&](int x) -> int { return x == r[x] ? x : r[x..