반응형 분할정복8 백준 16134번 조합 - C++ 풀이 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 조합 nCr의 정의대로 반복문을 통해 계산할 것이다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. (A*B) mod C = (A mod C) * (B mod C) mod C 임을 이용하여 곱셈을 계산하고, 나눗셈의 경우 1,000,000,007이 소수이므로 모듈러 곱셈 역원을 이용하여 계산한다. 모듈러 곱셈 역원은 분할정복을 이용한 거듭제곱을 사용해서 구하면 된다. #include using namespace std; typedef long long ll; const ll MOD = 1000000007; ll pow.. 2022. 8. 30. 백준 11778번 피보나치 수와 최대공약수 - C++ 풀이 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 위와 같은 피보나치의 성질을 이용해서 푸는 문제였다. 증명은 여기를 참고했다. https://math.hmc.edu/funfacts/fibonacci-gcds-please/ 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 먼저 m과 n의 최대 공약수를 구해야 한다. 유클리드 호제법을 사용하여 O(logN)에 구해준다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 피보나치 수열을 행렬의 거듭제곱으로 나타낸 .. 2022. 7. 22. 백준 2086번 피보나치 수의 합 - C++ 풀이 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 2. 점화식을 행렬 곱으로 나타낸다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 피보나치수열을 점화식으로 나타내면 f(n) = f(n-1) + f(n-2), f(1) ~ f(n)의 합을 g(n)이라고 하면, g(n) = g(n-1) + g(n-2) + 1이다. 2. 점화식을 행렬 곱으로 나타낸다. g에 대한 점화식을 다음과 같은 행렬 곱으로 나타낼 수 있다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 분할 정복을 이용하여 거듭제곱을 계산하여 시간 초과를 피한다. #.. 2022. 7. 19. 백준 4256번 트리 - C++ 풀이 1. root 노드는 preorder[0]이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 1. root 노드는 preorder[0]이다. 전위 순회 시 가장 먼저 방문하는 노드는 루트 노드이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 중위 순회 시 왼쪽 부트리 - 루트 - 오른쪽 부트리 순으로 방문한다. 전위 순회 결과에서 찾은 루트를 중위 순회 결과에서 찾는다. 그리고 루트보다 더 먼저 등장한 노드들로 왼쪽 부트리를 만들고, 루트보다 더 나중에 등장한 노드들로 오른쪽 부트리를 만드는 작업을 재귀적으로 반복해주면 원래 트리를 .. 2022. 7. 11. 백준 1030번 프렉탈 평면 - C++(cpp) 풀이 1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기 2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다. 3. N*N개 조각으로 나눈 뒤, fill을 재귀적으로 호출해 나머지 부분의 색칠을 완료한다. 1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기 프렉탈 무늬가 재귀적으로 생성되므로 분할정복을 이용할 수 있다. fill(sz, sr, sc)를 다음과 같이 정의하자. 2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다. fill에서는 현재 보드를 N*N개 조각.. 2022. 4. 12. 이전 1 2 다음 반응형
