수학 (3) 썸네일형 리스트형 [백준 2749][C++] 피보나치 수 3 문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 과정 [피사노 주기 문제] [행렬 풀이 코드 1] [행렬 풀이 코드 2] [피보나치의 행렬 멱법] 해당 문제를 직접 풀지 못하고 다른 사람들의 풀이를 찾아보게 되었다. 풀이는 크게 두 가지였다. 하나는 피사노 주기를 이용하는 방법과 다른 하나는 행렬을 이용하는 방법이었다. 필자는 위의 링크들을 참고하여 행렬을 이용한 풀이를 선택했다. 피사노 주기에 대한 풀이가 훨씬 간단했지만, 해당 조건보다 행렬을 이용해 문제를 풀이하는 방법이 더 보편적이고 다른 문제에도 적용할 수.. [백준 10830][C++] 행렬 제곱 문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 과정 분할 정복 알고리즘을 적용한다. 행렬 곱 함수를 작성한 뒤, 행렬의 제곱을 기록하며 결과를 이용하도록 구현한다. 예를 들어 A^9를 구한다고 가정했을 때, A^9 = A * (A^4) * (A^4) 형태로 곱이 이루어지며, O(logN)의 시간 복잡도를 가진다. 정답 배열을 초기화할 때는 곱을 해도 원래 형태가 나오도록 단위행렬 형태로 초기화해야 한다. 소스 코드 #include #include.. [백준 11401][C++] 이항 계수 3 문제 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 이 문제는 중요 포인트가 두 가지 있었다. (1) 분할 정복으로 연산 시간 감소 POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산.. 이전 1 다음
