문제 풀이/백준 (BOJ)

[백준/BOJ] 10830번: 행렬 제곱 ( 분할 정복법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/10830 풀이크기가 N x N인 행렬 A의 B제곱을 구하는 문제입니다. 문제를 보면 B의 크기가 심상치 않습니다.실제로 이 문제를 풀면서, 당연히 int 범위의 숫자라고 생각했다가 한동안 헤맸었습니다. 그렇지만, 풀이 방식은 숫자의 거듭제곱을  풀었던 방식을 적용할 수 있습니다.단지, A가 숫자가 아니라 행렬이라는 것이 다를 뿐입니다. 그 문제에 관심 있으신 분은 여기에서 보실 수 있습니다. [백준/BOJ] 1629번: 곱셈 ( 분할 정복법 ) - C++ 문제 풀이문제 설명 문제 링크: https://www.acmicpc.net/problem/1629 풀이자연수 A를 B번 곱한 수를 구하는 문제입니다. 당연히, A, B에 ..

2024. 5. 29.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1140번: 이항 계수 3 ( 페르마의 소정리 ) - C++ 문제 풀이

내용 설명 문제 링크: https://www.acmicpc.net/problem/11401 풀이주어진 자연수 N과 정수 K에 대한 이항 계수를 정해진 수( p = 1,000,000,007 )로 나눈 나머지를 구하는 문제입니다. 이항계수란 n개의 원소 집합에서 k 개수의 원소를 순서 없이 뽑는 방법의 개수를 말합니다.여기서 이항이란 한 개의 아이템에 대해서 뽑거나 뽑지 않거나 두 가지의 선택이 있기 때문에 붙은 단어입니다.이를 공식으로 나타내면 아래와 같습니다.  이 문제도 역시 주어진 공식대로 계산하면 시간제한에 걸립니다. 우선 생각할 수 있는 방법은 동적 계획법이 있습니다.이항 계수의 성질 중에 더 작은 수의 이항 계수로부터 문제의 값을 구할 수 있는 방법이 있습니다.  이 재귀 공식을 동적 계획법에 ..

2024. 5. 27.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1629번: 곱셈 ( 분할 정복법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1629 풀이자연수 A를 B번 곱한 수를 구하는 문제입니다. 당연히, A, B에 큰 수가 입력됐을 때 글자 그대로 A^B ( A * A * A * A *... )의 계산을 하면 시간제한에 걸립니다. 이런 경우에 분할 정복법을 쓰게 되면 계산 시간을 상당히 줄일 수 있습니다. 분할 정복법은 재귀적으로 자신을 호출하면서 조건에 맞을 때까지 그 연산의 단위를 조금씩 줄어가는 방식입니다. 큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식이라고 할 수도 있습니다. 예를 들어, 2^10 = 2^5 * 2^5로 분할할 수 있고, 이제 2^5의 계산만 하면 2^10의 값을 알 수 있습니다.분할..

2024. 5. 24.