문제 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$를 부여 할 때 내..
문제 https://www.acmicpc.net/problem/4013 알고리즘 SCC 풀이 여행 계획 세우기 문제와 거의 비슷합니다. 방문한 도시를 또 방문할 수 있다는 점에서 사이클이 존재함을 알 수 있고, 하나의 사이클안에 있는 ATM은 전부 얻을 수 있는 돈이므로 SCC를 통해 하나의 큰 정점으로 표현 가능합니다. DAG위에서 위상정렬 순서상 빠른 정점부터 얻을 수 있는 최대 금액을 갱신해나가면 됩니다. 이는 $SC$값을 역으로 순회하면 해결 가능합니다. 단, 위 문제와는 다른 점이 있다면 도착 정점이 여러 개라는 점입니다. 사용하는 변수가 많으므로 추가적인 변수들은 아래에 정리해두니, 코드를 보실 때 참고하시면 좋습니다. $isres[i]$= $i$교차로에 레스토랑이 있을 때, True $mon..
- Total
- Today
- Yesterday
- hld
- 펜윅트리
- DP
- 이분매칭
- 세그먼트트리
- dijkstra
- dfs
- greedy
- sweeping
- 동적계획법
- 이분탐색
- 스위핑
- 트라이
- spring boot
- string
- spring
- SCC
- Fenwick
- 정렬
- Segment tree
- kmp
- union find
- knapsack
- Oracle
- 좌표압축
- sorting
- bfs
- implementation
- 2-SAT
- Suffix Array
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |