BOJ 백준Divide & Conquer 검색 결과

해당 글 5건

백준 11444 - 피보나치 수 6

출처 : https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 고려사항 행렬곱을 이용하여 피보나치 수 구하기. (logN 속도를 띈다) 피보나치를 푸는 방법이 정말 다양한다...백준 블로그 참조 행렬곱을 Divide & Conquer 를 활용하여 구현하면, 엄청난 수의 행렬 제곱도 빠르게 구할 수 있다. 백준 02749번 풀이도 확인해 보자! #include using namespace std; void multi(long long m1[][2], long long m2[][2]){ long long tmp[2][2]; lon..
BOJ 백준/Divide & Conquer 4년 전

백준 01629 - 곱셈

출처 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 고려사항 10830번 행렬의 거듭제곱 구하기 처럼 분할정복을 이용하여 곱셈의 연산 수를 줄이는 방식 long long 의 거듭제곱을 위해 powl( ) 사용. 결과(ans), 지수(b) 와 현재 거듭제곱(tmp)이 있을 때, 1) 지수 % 2 == 1, 이라면 ans 에 tmp를 곱해준다. 2) 지수를 반토막 내준다. 3) tmp를 제곱해준다. #include #include using namespace std; int main() { int a, b,..
BOJ 백준/Divide & Conquer 4년 전

백준 01780 - 종이의 개수

출처 : https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 고려사항 색종이 만들기 문제의 분할 크기 차이만 있을 뿐 똑같은 문제. 분할 정복 기법 사용. -1, 0, 1 타입이 지정되어 있으니 len == 1 이었는데 isComplete 하지 못하다면 0 return 해주기 #include using namespace std; int paper[2187][2187]; int divide(int y, int x, int len, int ..
BOJ 백준/Divide & Conquer 4년 전

백준 01992 - 쿼드트리

출처 : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 고려사항 2630 번 문제와 유사 압축이 안되어서 4분할을 할 시에는 앞, 뒤에 ( ) 추가 2630 번 처럼 n == 1 인 상황 예외 처리 x 2630 은 비교 대상이 인자로 넘겨 받은 값이라 n이 1이어도 isComplete 아닐 수 있지만, 위 문제는 비교 대상이 n이 1이라면 그 원소 자체이기 때문에 무조건 isComplete 이다! #include #include ..
BOJ 백준/Divide & Conquer 4년 전

백준 02630 - 색종이 만들기

출처 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 고려사항 - 분할정복 기법 사용. - 통일되지 않은 n * n 색종이라면 시작점을 구분지어 n / 2 크기로 분할 후 재검사 ( 25 - 29 라인 ) - color 값을 넘겨 주어 일치여부 판별 - n == 1 일때, 조사중인 색상과 다르다면, 25 - 29 라인 진입 않고, return 0 #include using namespace std; int divi..
BOJ 백준/Divide & Conquer 4년 전