mojo's Blog

문제 링크 => 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 위와 같이 (i - 1, j - 1) 일때의 최대 넓이와 현재 (i, j) 로부터 왼쪽으로의 1의 최대 갯수와 윗쪽으로의 1의 최대 갯수를 활용하여 현재 (i, j) 의 원소가 0, 1인지를 구분하여서 접근하면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define INF 100000000 using namespace s..

문제 링크 => 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 최대 전깃줄이 되도록 하려면 B전봇대로 연결된 전깃줄 중에 오름차순으로 연결될 수 있는 경우 중에 최댓값을 구해줘야 한다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int dp[501]; bool compare(pair x, pair y) { return..

문제 링크 => 11051번: 이항 계수 2 (acmicpc.net) 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 다이나믹 프로그래밍 문제이다. C(N, K) 를 이항계수 N(N-1)...(N-K+1) / 1*2*...*K 라고 할 때 Optimal substructure는 다음과 같다. K = 0 => C(N, K) = 1 K != 0 => C(N, K) = C(N, K-1) * (N - K + 1) / K % 10007 이 때 나누기 연산이 좀 거슬려 보인다. 여기서 10007은 prime 임을 이용하여 fermat's theorem 을 이용해 보도록 하자. x^(m-1) ..

문제 링크 => 1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 연습 문제이다. 전부 c로 구현하면 좋겠지만 priority_queue는 귀찮아서 stl로 가져와서 써먹었다. 만약에 priority_queue를 구현한다면 알고리즘 시간에 배웠던 heap을 이용하여 조건을 더 추가하여 만들면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #..

Canonical collection LR(0) item set의 canonical collection C0 - C0 = {CLOSURE ({[S′ →•S])} ∪ {GOTO (I, X) | I ∈ C0, X ∈ V} Example: LR(0) item set의 canonical collection을 구해보자. P: ① E → E ＋ T ② E → T ③ T → T ＊ F ④ T → F ⑤ F → (E) ⑥ F → id (1) Augmented grammar 를 추가한다. S' -> E (2) CLOSURE 를 구한다. I0 = CLOSURE([S' -> •E]) = {[S' -> •E], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)],..

The average memory access time(AMAT). AMAT = (P(hit) * T(M)) + (P(Miss) * T(D)) T(M)