devbelly

문제 https://www.acmicpc.net/problem/4196 알고리즘 SCC 풀이 손으로 넘어뜨려야 한다는 것은 자신을 밀어주는 도미노가 없다는 뜻이죠. 그래프로 나타낸다면 자신을 가리키는 간선이 없습니다. 즉, 차수가 0인 컴포넌트의 개수가 정답입니다. SCC를 사용해 그래프를 DAG로 만든 후 모든 간선들을 검사하며 양쪽 정점의 $sccid$가 다르다면 한쪽 정점의 차수를 카운트 해줍니다. 이후 $ind$ 를 순회하며 값이 0이라면 $ans$를 증가시켜주면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i TC; while (TC--) { cin >> N >> M; VC = SC = 0; adj.clear(); sccid.clear(); discovere..

문제 https://www.acmicpc.net/problem/2152 알고리즘 SCC 풀이 SCC는 그래프를 DAG로 바꾸며 각 컴포넌트의 크기를 최대로 묶어줍니다. 최대 도시를 구한다는 점과 시작 도시와 도착 도시가 있다는 점은 SCC와 잘 어울리죠. DAG로 그래프를 바꾼 후에는 DAG상에서 차수가 낮은 컴포넌트부터 차수가 높은 컴포넌트를 갱신해줍니다. 즉 위상정렬 순서로 갱신해줍니다. 유의할 점 중 하나는 SCC알고리즘을 사용하게 되면 $sccid$의 역순이 위상 정렬 순서와 동일합니다. 다시 말해 $sccid$ 의 값이 작다면 위상정렬 순서상 뒤에 있고, $sccid$값이 크다면 위상 정렬순서상 앞에 있음을 의미합니다. 굳이 위상 정렬 알고리즘을 사용해서 순서를 배치할 필요가 없습니다. dfs ..

문제 https://www.acmicpc.net/problem/11378 알고리즘 이분매칭 풀이 열혈강호 3과 달라진 점은 한 사람당 최대 두 가지의 일을 할 수 있었던 3번 문제에 반해, 열혈강호 4는 벌점에 따라 한 사람당 최대할 수 있는 일의 수가 달라진다는 점입니다. 비슷하므로 비슷하게 풀어봅시다. 마찬가지로 $N$까지 루프를 한번 돌려 한 사람당 한 가지 일을 매칭해주도록 합시다. 열혈강호 3에선 추가적으로 루프를 한 번만 더 돌려서 한 사람당 최대 두 가지 일을 할 수 있다 라는 점을 구현하였는데, 이 문제에선 추가 매칭이 이루어지지 않을 때까지 루프를 돌립니다. 즉 $K$를 다 사용하거나, 아직 $K$가 남아있지만 더 이상 사람이 일을 할 수 없을 때를 뜻합니다. 시간 복잡도는 $O(K*VE..

문제 https://www.acmicpc.net/problem/11377 알고리즘 이분매칭 풀이 열혈강호 시리즈 세 번째 문제입니다. 열혈강호 2와 같이 한 사람당 최대 두 개의 일을 한다는 점은 같지만 추가 매칭이 최대 K번 가능한 점이 다릅니다. 비슷한 문제이므로, 비슷하게 풀 수 있습니다. $bipartite matching()$에서 $N$까지 루프를 한번 돌려서 한 사람당 한가지 일을 하도록 매칭을 한 후, 다시 루프를 돌며 추가매칭이 K번 이하 이루어졌다면 계속해서 매칭을 해주면 됩니다. 역시 시간 복잡도는 $O(VE)$입니다. 코드 #include #include #define rep(i,n) for(int i=0;i N >> M >> K; adj.resize(N + 1); REP(i, N) ..

문제 https://www.acmicpc.net/problem/11376 알고리즘 이분매칭 풀이 두 가지의 풀이가 있습니다. 1번 풀이는 정점분할입니다. 사람정점 $i$번에 대해 $T(i)$,$F(i)$ 이와 같이 두가지의 정점으로 나눈후 열혈강호 1과 동일하게 풀면 됩니다. 2번 풀이는 사람정점 $i$번에 대해 dfs를 두 번 수행하는 것입니다. 그럼 한 사람당 최대 두가지 일에 매칭이 되어 문제를 해결할 수 있습니다. 코드1 #include #define rep(i,n) for(int i=0;i> v; adj[T(i)].emplace_back(v); adj[F(i)].emplace_back(v); } } cout > M; adj.resize(N + 1); REP(i, N) { cin >> cnt; w..

문제 https://www.acmicpc.net/problem/10747 알고리즘 KMP 풀이 KMP를 통해서 제거할 문자열의 위치를 찾아내는 접근까지는 쉽습니다. 검열할 문자를 없앤 후, 우리는 이전의 상태로 돌아가야 하는데, 이를 위해 $matchCnt$배열을 사용합니다. $matchCnt [i]$ = 문자열 S의 $i$까지 봤을 때, 문자열 T와 일치하는 길이 벡터에 지금까지 확인한 S글자들을 담으며, 제거할 문자열을 찾았다면 벡터에서 T의 길이만큼 제거합니다. 그 후 이전의 상태, 즉 제거한 문자열의 첫 문자가 들어오기 직전의 상태로 돌아가야 합니다. KMP에서 $j$의 의미는 지금까지 매칭된 길이와도 동일하므로(구현에 따라 차이가 날 수 있음, 이 코드에선 매칭된 길이 -1입니다) $j$값을 $..

문제 https://www.acmicpc.net/problem/11375 알고리즘 이분매칭 풀이 존재하는 정점을 두 가지 그룹으로 나누었을 때, 간선의 양 끝점 정점이 서로 다른 그룹에 속해있는 그래프를 이분 그래프라고 하고, 이분 그래프상에서 최대 매칭을 구하는 문제를 이분 매칭이라고 합니다. 기본적인 이분매칭 문제로, 전체적인 구현은 프로그래밍 콘테스트 챌린징의 이분매칭 구현을 참고하였습니다. 핵심인 $dfs$ 함수는 현재 정점(사람)의 간선을 검사하는데 만약 반대 정점(일)이 매칭이 되지 않았거나, 매칭 되었더라도 해당 매칭을 옮길 수 있으면 true를 리턴하게 됩니다. 이로써 최대 매칭에 성공하게 되는 것이죠. 각 정점에 대해 $dfs$를 수행하므로 시간 복잡도는 $O(VE)$입니다. 코드 #in..

문제 https://www.acmicpc.net/problem/5446 알고리즘 트라이 풀이 제거해야 하는 문자열과 남겨야 하는 문자열이 주어지고, "문자열"+"*"을 통해 "문자열"로 시작하는 모든 문자열을 제거할 수 있다고 합니다. 접두사를 이용한다는 점에서 트라이를 착안해봅시다. 각 노드마다 $yes$,$no$,$finish$ 를 만들어서 해당 노드를 제거해야하는지(yes), 제거해서는 안되는지(no), 제거해야 하는 문자가 끝나는지(finish)를 구분합니다. 만약 노드의 $yes$와 $no$가 둘 다 True 면 해당 노드를 제거해서는 안됩니다. (노드를 제거한다는 것은 와일드 카드를 사용해서 이후 노드를 보지 않겠다는 의미입니다) 이때 유의해야할 것은, 제거해서는 안 되는 노드에 $finish..