mojo's Blog

Theorem 1 A 2-sat formula φ is satisfiable if and only if there is no variable x with paths from x ~> x' and x' ~> x in G(φ). Proof : If such a pair of paths exists, then φ is contradictory, and hence unsatisfiable. Suppose then that no such pair exists. Observe that a single one of these paths does not cause a contradiction. x ~> x', x' ~> x 에 대한 경로가 두 개 존재할 경우 즉, x에서 x'으로 가거나 x'에서 x으로 여러번 걸쳐 지..

0-1 Knapsack Example 2: n = 6, W = 10 알고리즘 별로 획득되는 이익이 다른것을 알 수 있다. 위 예제에서 그나마 좋은 알고리즘이 greedy 알고리즘인데 이 중에 최대 이익을 뽑아낼 수 있는 알고리즘을 활용하여 O(nlogn) 의 효율을 뽑아서 이익을 뽑도록 한다. The Greedy Methods A technique to follow the problem-solving heuristic of making the locally optimal choice at each stage. ※ Strategy - 매 순간마다 가장 최선인 것을 선택하는 방법이다. - 즉, locally optimal를 선택함으로써 globally optimal을 도달하려는 것이 궁극적인 목표이다. ※ ..

문제 링크 => 1937번: 욕심쟁이 판다 (acmicpc.net) 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 어떠한 지점 (x, y) 에서 존재하는 대나무를 먹고 다음 지점(nextX, nextY) 으로 이동할 때, 다음 지점(nextX, nextY) 에 존재하는 대나무의 갯수가 (x, y) 지점에 있던 대나무의 갯수보다 클 경우 다음 지점으로 이동하여 대나무를 먹는다. 이렇게 판다가 이동하면서 대나무를 야무지게 먹을 수 있는 최대 거리를 구해야 한다. 알 수 ..

문제 링크 => 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 무난한 DFS 문제이다. 해당 문제에 대한 접근법은 다음과 같다. ⓞ 시간을 1 증가시킨다. (count++) ① 빙산이 있는 지점(x, y)을 확인..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com 완전 탐색 + 구현 문제이다. 어제 서강대 학회분들과 함께 풀다가 뇌절을 한 문제이다. (9번 트라이 실패) 문자열 S의 [i, j] 범위의 서브문자열을 S(i, j) 라고 할 때 다음 세가지 조건을 만족해야 한다. ① 적어도 길이가 2여야 한다 => Len(S(i, j)) ≥ 2 ② 'a'의 갯수는 'b'의 갯수보다 커야 한다 => a_size(S(i, j)) > b_size(S(i, j)) ③ 'a'의 갯수는 'c'의 갯수보다 커야 한다 => a_size(S(i, j)) > c_size(S(i, j)) 문제 자체는 어렵지 않다. s[i] = 'a', s[j] = 'a' ..

LALR Parser Implementation 1. 파싱표를 구성하기가 쉽지만 파싱표의 크기가 커지는 LR(1)을 가지고 구성 ● 같은 코어를 가진 LR(1) item을 묶어서 하나의 state로 구성 2. 효율적으로 파싱표를 구성할 수 있는 LR(0)과 lookahead를 가지고 구성 ● LR(1) item의 lookahead를 합한 것으로 구성 Example : LALR parse table을 구해보도록 하자. P: S -> CC C -> cC C -> d I3, I6는 같은 코어이므로 lookahead 를 합친다. I36 = {[S → c•C, c/d/$], [C → •cC, c/d/$], [C → •c, c/d/$]} I4, I7는 같은 코어이므로 lookahead 를 합친다. I47 = {[C..