전체 글 (117) 썸네일형 리스트형 PS에서 쓰는 Matrix multiplication의 구현과 최적화 1. Introduction Problem Solving을 위해 C/C++ 을 쓰는 사람들에게 matrix multiplication의 구현은 귀찮은 일입니다. 당연히 많은 사람들이 이를 템플릿에 박아놓고 그대로 씁니다. 하지만, 문제의 제한에 따라 다양한 최적화의 여지가 있으며 일부는 탁월한 효과를 보입니다. 이 글에서는 가장 naive한 구현에서부터 특수한 맥락에서만 쓸 수 있는 코드까지 소개해보고자 합니다. 대부분의 코드는 제 경험으로부터 비롯하였으며, 따라서 C++의 reference type이나 STL(특히, , 등)을 쓰거나, class로 wrapping하는 코드는 다루지 않습니다. 2. 기본적인 구현 우선, matrix multiplication의 가장 일반적인 형태는 다음과 같습니다. $m.. 백준 9556번: 수학 숙제 https://www.acmicpc.net/problem/9556 9556번: 수학 숙제 각 테스트 케이스마다 조건을 만족하는 N자리 정수의 개수를 1,000,000,007로 나눈 값을 출력한다. www.acmicpc.net 처음엔 포함 배제로 풀려고 했다가, 제가 포함 배제에 익숙하지 못해서 구현을 포기하고 다른 방법으로 풀게 됐습니다. 이 문제의 첫 번째 포인트는 $N$자리 수는 한 개 이상의 0으로 시작할 수 있다는 것입니다. 즉 우리가 체크해야 할 수의 범위는 0부터 $10^{N}-1$까지입니다. 두 번째 포인트는 이 문제의 나눠 떨어진다는 표현은 나머지가 0이라는 것입니다. 그래서 0은 모든 양의 정수로 나누어 떨어지는 수라고 합니다. 이 문제는 물론 포함 배제로도 풀 수 있겠지만, 더 쉬운 관.. 백준 16201번: 발코니 공사 https://www.acmicpc.net/problem/16201 16201번: 발코니 공사 첫째 줄에 별장 발코니의 크기 R, C와 부서지지 않은 칸의 개수 K가 주어진다. (1 ≤ R ≤ 1,000,000,000, 2 ≤ C ≤ 1,000,000,000, 0 ≤ K ≤ 1,000) 둘째 줄부터 K개의 줄에는 부서지지 않은 칸의 위치가 공백 www.acmicpc.net 도미노의 모양새에 대한 조건이 너무 강력해서 티어가 낮아진 문제입니다. 이 문제는 colorless한 $1 \times 2$ 도미노의 타일링을 다루고 있고 특별한 조건으로 "가로로만 놓을 수 있음"이 있습니다. 또 하나의 조건은 도미노를 최대한 많이 써야만 한다는 것입니다. 그래서 각 row에 대해 총 몇 개의 도미노를 놓을 수 있는지.. 백준 26132번: Fair Division https://www.acmicpc.net/problem/26132 26132번: Fair Division After sailing the Seven Seas and raiding many ships, Cap’n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap’n Red starts by www.acmicpc.net 비록 해당 대회에서 제일 약한 급의 문제이긴 하지만 ICPC World Finals 2021 문제입니다! 풀이는 약간의 수학.. 백준 16214: N과 M https://www.acmicpc.net/problem/16214 16214번: N과 M 임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있 www.acmicpc.net 일반적인 power tower 유형에서 모든 지수에 $N$을 넣어준 것이므로 난이도가 어떤 면에선 더 쉬워졌다고 볼 수 있습니다. 본문은 매우 훌륭한 자료인 https://rkm0959.tistory.com/181 을 인용했습니다. 위 글에 따르면 다음이 성립합니다. (Notation은 위 링크를 참조해주시기 바랍니다.) $$ [N,N,N, \cdo.. 백준 17315번: Matrix Game (integer interpretation) https://www.acmicpc.net/problem/17315 17315번: Matrix Game The input will contain the six integers n, m, a, b, c, and d. www.acmicpc.net National Olympiad in Informatics, China, 2013, Day2에 Problem1로 출제된 문제라고 합니다. 행렬 거듭제곱 풀이에 대해 궁금하신 분은 이쪽 링크를 이용하시면 됩니다:Matrix Game (matrix interpretation) 정수 거듭제곱 풀이는 주어진 규칙대로 끝까지 전개하여 다음 식에서 $f$와 $g$를 구하는 것이 목표입니다. $$ F[n][m] = f(a,b,c,d) \times F[1][1] + g(a,b,c.. 백준 14553번: The Way https://www.acmicpc.net/problem/14553 14553번: The Way 여우와 토끼는 사이가 좋았다. 하지만 어느 날 토끼가 여우에게 갓겜 "히어로즈 오브 더 스톰"을 추천했고, 여우는 게임을 해보고 너무 화가나서 토끼를 쫓으러 갔다. 히어로즈 오브 더 스톰의 www.acmicpc.net 처음에 dp 식을 이상한 방향으로 접근해서 오랫동안 힘들었던 문제입니다. 우선 제가 AC 받은 접근은, $3 \times N$ 격자를 가장 왼쪽의 1열에서 2열로 넘어가는 모양새를 기준으로 subproblem을 나눕니다. 이게 무슨 뜻인지 경우의 수를 나누어 설명하겠습니다. 시작하는 칸에서 바로 오른쪽으로 이동 : 2열의 윗 칸에서 N열의 아랫 칸으로 가는 경우의 수 시작하는 칸에서 2열의 가운.. 백준 13380번: Found https://www.acmicpc.net/problem/13380 13380번: Found Alice and Bob live in a city with N intersections (numbered as intersection 1, intersection 2,..., intersection N). There are M roads. Each road is bidirectional and directly joins two intersections. Each pair of intersections is joined by at most one road www.acmicpc.net 문제 지문을 읽어보면, $N$개의 intersection이 있고 $M$개의 road가 있고 $T$ 만큼 지난 후에 둘이 만납니다. .. 이전 1 2 3 4 5 6 7 8 ··· 15 다음 목록 더보기