devbelly

문제 https://www.acmicpc.net/problem/16915 알고리즘 2-SAT 풀이 풀면서 이 문제와 굉장히 유사하다고 느꼈습니다. 각 방마다 스위치가 두 개가 있고, 방의 상태에 따라 다음과 같은 선택을 할 수 있습니다. 각 방마다 연결되어있는 스위치를 A, B라고 하겠습니다. 1. 만약 방의 초기상태가 켜져 있다면, A와 B 둘 다 눌러서 켜진 상태를 유지하거나 A와 B둘다 누르지 않습니다. 2. 방의 초기상태가 꺼진 상태라면, A를 눌렀을 땐 B를 누르지 않고 B를 눌렀을 땐 A를 누르지 않아 켜지도록 합니다. 위 두 문장은 And or And 관계로 표현가능하며 2-CNF형태를 만족시키도록 전개해주면 문제를 풀 수 있습니다. 코드 #include #define rep(i,n) for..

문제 https://www.acmicpc.net/problem/15675 알고리즘 2-SAT 풀이 강산이가 보석을 훔치기 위해선 행 또는 열에 한 번만 입장을 해야 합니다. 관장 택희가 보석이 도난당할 시, 즉시 경비원을 출동시키기 때문에 두 번 다시 입장이 불가능하기 때문입니다. 훔치는 과정에서 위치추적기를 얻을 시에는 언젠가는 다시 한번 방문을 해서 위치추적기를 떼어 놓아야만 합니다. 즉 박물관 좌표 $y$행,$x$열에 대하여 보석이 위치한 곳에는 $(T(y)\cap F(x))\cup (F(y)\cap T(x))$ 를 만족하며 추적기가 위치한 곳에 대해서는 $(T(y)\cap T(x))\cup (F(y)\cap F(x))$ 를 만족합니다. $T()$는 해당 행 또는 열을 방문한다는 의미이며 $F()$..

문제 https://www.acmicpc.net/problem/3648 알고리즘 2-SAT 풀이 문제에서 2-SAT의 느낌을 물씬 풍기는 문장이 몇 있습니다. '적어도 하나'라는 문장은 OR을 연상케 하고 OR은 2-CNF에서 하나의 절을 구성합니다. 그리고 한 참가자에 대해 두 가지 선택을 할 수 있다는 점도 True와 False로 연관 지을 수 있으니 2-SAT으로 문제를 접근합시다. 심사위원의 의심 없이 다음라운드를 구성할 수 있다면 하나의 참가자에 대해 모순이 되는 경우가 없다는 의미와 같습니다. 즉, 각 정점의 True와 False의 $sccid$가 일치해서는 안됩니다. 상근이가 진출하는 경우는 그래프상에서 상근이의 False 정점이 True 정점보다 위상정렬상 빠른지 확인하면 됩니다. 이전 문..

문제 https://www.acmicpc.net/problem/11281 알고리즘 2-SAT 풀이 이 문제에서 실제 해까지 찾아서 출력하는 문제입니다. SCC 이후 하나의 간선을 구성하는 두 정점을 살펴봅시다. 앞서 살펴본 바와 같이 u->v를 만족하기 위해선 not u 일 땐 v가 무엇이 와도 상관이 없으나 True u 일 땐 2-CNF에서의 절을 만족하기 위해 v가 True임이 강제됩니다. 즉 우리는 위상 정렬상 빠른 쪽에 위치한 정점을 False로 평가하는 것이 True로 평가하는 것에 비해 항상 이득임을 알 수 있습니다. 코드 #include #define rep(i,n) for(int i=0;i u >> v; OR(u, v); } discovered = sccid = vector(N

문제 https://www.acmicpc.net/problem/11280 알고리즘 2-SAT 풀이 SCC알고리즘을 활용하여 2-SAT을 모델링하는 문제입니다. True나 False를 판단해야 하는 하나의 변수에 대해 이미 True나 False를 정해주고 모순이 생기는지만 확인하는 문제입니다. 각 절에 대해 두 개의 or 관계가 주어지면 우리가 얻을 수 있는 정보는 다음과 같습니다. A or B가 주어졌을 때 False A 라면 True B 여야 하고, False B 라면 True A 여야만 합니다. 두 개의 정보에 대해 우리는 간선으로 표현할 수 있으며, 만약 하나의 정점 C에 대해 False C와 True C가 동일한 컴포넌트로 묶인다면 이는 모순임을 나타냅니다. 변수는 1부터 시작하므로 크기를 할당할..

문제 https://www.acmicpc.net/problem/15483 알고리즘 DP 풀이 유명한 DP 문제입니다. $cache$를 다음과 같이 정의합시다 $cache[i][j]$ = $A$문자열의 1~$i$번째 부분 문자열과 $B$문자열의 1~$j$번째 부분 문자열이 일치하기 위한 최소 편집 거리 위 상태는 총 3가지 상태에서부터 갱신됨을 알 수 있습니다. $cache[i-1][j]$ 에서 $A[i]$ 문자를 삭제. $cache[i][j-1]$ 에서 $A$에 문자를 추가. $cache[i-1][j-1]$ 에서 $A[i]$문자를 수정. 이를 통해 우리는 2차원 배열을 사용해 메모이제이션을 하지만, 모든 상태 공간$O(MN)$을 필요로 하지 않음을 알 수 있습니다. 시간 복잡도는 $O(MN)$입니다. 코..

문제 https://www.acmicpc.net/problem/1108 알고리즘 SCC 풀이 점수가 무한대로 늘어나는 것을 방지하기 위해 두 정점에 대해 직간접적 연결이 없을 때에만 점수를 더해준다고 합니다. 직간접 연결을 확인하려면 그래프에서 사이클을 확인해야 하고 사이클을 확인하는 알고리즘인 SCC를 떠올릴 수 있습니다. SCC알고리즘 사용 이후, 모든 간선을 검사하며 두 정점의 $sccid$가 다르다면 $sccadj$에 실제 간선을 추가해줍시다. 이 이유는 하나의 SCC로 묶인 정점들끼리도 점수가 다를 수 있기 때문입니다. 단, $cache$를 갱신하는 과정은 위상정렬상 앞에 있는 순서부터 뒤에 있는 순서로 갱신해나가야 하므로, vector형태를 사용한 것에 주목합시다. 예를 들어 scc_adj[a..

문제 https://www.acmicpc.net/problem/11097 알고리즘 SCC 풀이 처음에 문제만 읽어서는 SCC라는 것을 알아채기가 힘들었던 문제입니다. 감이 잡히지 않으므로 2번 예제를 직접 그려보도록 합시다. 그림을 그려본다면 답에 해당하는 간선이 두 가지 종류임을 알 수 있습니다. 첫 번째는 하나의 SCC에서 다른 SCC를 잇는 외부 간선입니다. 두 번째는 각각의 SCC내부를 잇는 내부간선입니다. 이제 각각의 처리방법에 대해 생각해봅시다. SCC알고리즘의 작동방식을 생각해본다면 하나의 컴포넌트로 묶을 때 스택에서 차례대로 하나씩 꺼낸 후 묶는 것을 알 수 있습니다. 즉 스택에서 연속된 값은 서로를 잇는 내부 간선들임을 알 수 있습니다. 즉 스택에서 꺼내며 $sccid$를 부여 할 때 내..