본문 바로가기

분류 전체보기327

BOJ 11444 - 피보나치 수 6 (행렬곱, 점화식 이용) https://www.acmicpc.net/problem/11444 MOD가 10의 거듭제곱꼴이 아니므로 피사노 주기를 사용할수 없다. 따라서 행렬곱을 이용해야 한다. https://www.acmicpc.net/blog/view/28 설명은 이곳 참고 #include #include using namespace std; typedef long long ll; typedef vector matrix; const ll MOD = 1000000007LL; matrix operator * (const matrix& a, const matrix& b) { int n = a.size(); matrix c(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j.. 2019. 9. 27.
행렬의 표현 클래스나 구조체를 사용하는 법도 있겠지만 길이가 유동적인 정사각행렬에 대해서는 이 코드가 유용할 듯 하다. #include #include using namespace std; typedef long long ll; typedef vector matrix; matrix operator * (const matrix& a, const matrix& b){ int n = a.size(); matrix c(n, vector(n)); //n*n행렬이 0으로채워진 c 행렬이 생성된다. for(int i=0; i 2019. 9. 27.
BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) https://www.acmicpc.net/problem/2749 피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함) 그중 특히 MOD = 10^k (k>2) 인 경우 PRD = 15*10^(k-1)이다. fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다. 피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다. #include #include using namespace std; typedef long long ll; const int MOD = 1e6; const int PRD = 15e5; ll dp[PRD]; ll fibo(int k) { if (k > n; fill(dp, dp + PRD, -1); cout 2019. 9. 27.
KMP 문자열 매칭 알고리즘. O(N+M) string parent, pattern; KMP(parent,pattern) : pattern의 위치를 반환하는 함수 parent 문자열의 idx i, pattern 문자열의 idx j에 대해 i를 0부터 1씩 증가시키며 pattern을 찾는 상황에서 현재 i에서 pattern 찾는 것에 실패했을 때, i를 한 칸 옮기고 j를 fail[j]칸 옮기며 문자열을 찾는 알고리즘이다. 실패함수를 이용해서 푸는 문제가 많다. 실패함수를 만드는 로직과 kmp에서 pattern의 위치를 뽑는 로직이 같은 점을 눈여겨 보자. #include #include #include using namespace std; vector makeTable(string pattern) { int p.. 2019. 9. 18.

티스토리툴바