매일 조금씩

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 밑이 같은 두 거듭제곱의 곱은 밑은 그대로 쓰고 지수만 더해준다는 지수법칙을 활용한다. 예를 들어 2의 10제곱은 2^10 = 2^5 * 2^5 로 분할 할 수 있다. 그러면 2를 10번 곱하는게 아닌 2를 5번 곱한 값을 가져와서 제곱을 하면 된다. 2^5 또한 아래와 같이 분할 할 수 있다. 2^5 = 2^2 * 2^2 * 2 이렇게 지수의 거듭제곱을 절반 씩 분할 하면서 제곱 계산의 수를 현저히..

문제 https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 풀이 대표적인 분할 정복 문제로, 재귀 함수를 사용하여 작게 쪼개면서 푼다. 아래와 백준 문제와 풀이가 동일하다. 2021.11.16 - [Problem Solving/..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 아래와 같이 짜면 시간/메모리 초과가 발생한다. public static long recur(long a, long b, long c){ if(a==1 || b==1) return a; return a * recur(a, b-1, c) % c; } recur(a*a, b/2, c)로 호출하여 함수 호출 횟수를 줄이는게 핵심이다. overflow가 발생하지 않도록 여러 곳에 c로 mod연산을 해야한다. b가 1인 조건일 때 mod연산을 누락해서 한참 헤..

문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 아래 문제와 달리 해당 문제는 분할을 9개로 한다. (내부에서 좌표를 갱신하여 재귀함수를 9번 호출) 이 외에 풀이는 아래 문제와 유사하다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java) 문제 https://www.acmicpc.net/problem/2630 263..

문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할정복으로 푼다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 사분면 순으로 재귀함수를 호출하면서 모든 숫자가 1이면 1 출력, 0이면 0 출력. 이외의 케이스는 좌표와 크기를 갱신하여 다시 재귀를 돌려주면 된다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할 정복 문제, 재귀용법을 이용하여 푼다. 소스코드 package dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2630 { public static int oneCnt, zeroCnt; pub..