Algorithms 검색 결과

해당 글 123건

[BOJ 11444] 피보나치 수 6

피보나치 수 6 (Gold 3) 문제 전체 문제 보기 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근법 피보나치 수는 아래의 점화식을 따릅니다. \[f(n) = f(n-1) + f(n-2) \] 그런데 이번 문제에서 n의 크기는 매우 큽니다. 그래서 Brute Force로는 해결할 수 없고 행렬의 제곱으로 문제를 해결해야 합니다. 위 점화식을 행렬로 표현하면 아래와 같이 나타낼 수 있습니다. \[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatr..
Algorithms/Math 2021. 10. 9. 11:01

[BOJ 10830] 행렬 제곱(C++)

행렬 제곱(Gold 4) 문제 전체 문제 보기 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근법 이번 문제는 행렬의 거듭제곱을 최적화하는 문제입니다. 우선 행렬 간의 곱셈은 다음과 같이 3중 for문을 통해서 계산할 수 있습니다. using Matrix = vector; Matrix operator*(const Matrix& lhs, const Matrix& rhs) { int N = static_cast(lhs.size()); Matrix ret(N); for (int i = 0; i < N; ++i) { ret[i]..
Algorithms/Math 2021. 10. 8. 14:49

[BOJ 14891] 톱니바퀴(C++)

톱니바퀴(Gold 5) 문제 전체 문제 보기 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 접근법 이번 문제는 문제에서 주어진 톱니바퀴의 로직을 구현하는 문제입니다. 톱니바퀴의 회전은 deque을 활용하여 구현할 수 있습니다. 시계방향으로 톱니가 회전하는 것은 deque의 가장 끝 원소를 deque의 가장 앞으로 옮기는 것과 같고, 반 시계방향으로 회전하는 것은 반대로 deque의 가장 앞의 원소를 deque의 가장 끝에 옮기는 것과 같기 때문입니다. 4개의 톱니바퀴가 필요하기 때문에 4개의 deque를..
Algorithms/Implementation 2021. 10. 6. 09:24

[BOJ 14888] 연산자 끼워넣기(C++)

연산자 끼워넣기(Silver 1) 문제 전체 문제 보기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근법 이번 문제는 연산자가 삽입될 수 있는 모든 위치를 완전탐색하여 풀 수 있습니다. 연산자는 수와 수 사이에만 삽입될 수 있기 때문에 연산자가 삽입될 수 있는 위치는 N - 1 개이며 N은 최대 11입니다. 그리고 각 연산자는 사용할 수 있는 개수가 한정적입니다. 그래서 모든 경우의 수를 계산하더라도 \(4^{10} = 1,048,576\) 보다 훨씬..
Algorithms/Backtracking 2021. 10. 2. 14:02