Divide&Conquer

Algorithm/Baekjoon Online Judge
[Java] 백준 1891 (사분면) Gold 4
Problem : https://www.acmicpc.net/problem/1891 1891번: 사분면 첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1≤d≤50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y|≤2 www.acmicpc.net Approach 분할 정복(Divide & Conquer)을 구현한 문제이다. 아래와 같이 두 가지 기능을 구현하여야 한다. 그리고 순서대로 수행하면서 답을 도출한다. 주어진 사분면 숫자의 위치 (x, y)를 찾는다. 그리고 그 위치에 주어진 이동 횟수를 더한 위치를 찾는다. 구한 위치의 사분면 숫자를 구한다. 1번 기능의 경우, 주어진 사분면 숫자를 앞에서부터 한..
→2021.06.01
Algorithm/Baekjoon Online Judge
[java] 백준 11444 (피보나치 수 6) Gold 3
Problem : https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach 유명한 피보나치 수열의 n번째 수를 구하는 문제이다. 이 문제는 백준 2749 피보나치 수 3 문제와 나머지 연산 부분만 다르고 아예 똑같은 문제이다. 문제풀이 개수 늘리기 좋다. 하지만 n이 1,000,000,000,000,000,000 이하의 숫자이므로 오랜시간이 걸릴 것이다. 따라서 아래와 같이 피보나치의 행렬적 규칙을 이용하여 계산하여야 한다. (long 자료형을 사용하여) 아래 규칙만 알고 있다면 O(log n)의 행렬제곱 문제와 ..
→2021.01.08
Algorithm/Baekjoon Online Judge
[java] 백준 1629 (곱셈) Silver 1
Problem : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Approach 수학적 지식이 있어야 하는 분할정복(Divide & Conquer)문제이다. A^4 % C = ((A^2 % C) * (A^2 % C)) % C A^5 % C = ((((A^2 % C) * (A^2 % C)) % C) * A) % C 위의 규칙을 이용하여 구현하면 된다. Code import java.io.*; /** * no.1629 : 곱셈 * hint : A^2 % C = ((A % C) * (A % C)) % C */ p..
→2021.01.08
Algorithm/Baekjoon Online Judge
[java] 백준 1992 (쿼드트리) Silver 1
Problem : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net Approach 전형적인 분할정복(Divide & Conquer)문제이다. 다음과 같은 과정을 반복하면 답을 도출할 수 있다. 현재 영역의 제일 좌상 요소를 기억한 후, 모든 영역을 검사한다. 기억한 요소와 모든 영역이 같다면, 기억한 요소를 반환한다. 다르다면, 정확히 4등분한다. (나누기 전 괄호로 감싼다.) 나눠진 영역의 크기가 1x1이 될 때까지 1번 전체를 ..
→2021.01.08

• 이전
• 1
• 다음