Divide & Conquer
![[java] 프로그래머스 (쿼드압축 후 개수 세기) Level 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fben9tw%2FbtqS29jAnv4%2Fjvg7nrI0cNSgmdTXED6v8K%2Fimg.png)
[java] 프로그래머스 (쿼드압축 후 개수 세기) Level 2
Problem : 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 Approach 일단 이 문제는 백준 1992번 쿼드트리와 유사한 문제이다. 백준 문제의 내 풀이는 다음 링크로 가면 된다. java 백준 1992 (쿼드트..
![[java] 백준 2749 (피보나치 수 3) Gold 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FHps8f%2FbtqRnMY0JLv%2FjKoF4EZwLBkSCZHMqx3RK1%2Fimg.png)
[java] 백준 2749 (피보나치 수 3) Gold 2
Problem : https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach 유명한 피보나치 수열의 n번째 수를 구하는 문제이다. 하지만 n이 1,000,000,000,000,000,000 이하의 숫자이므로 오랜시간이 걸릴 것이다. 따라서 아래와 같이 피보나치의 행렬적 규칙을 이용하여 계산하여야 한다. (long 자료형을 사용하여) 아래 규칙만 알고 있다면 O(log n)의 행렬제곱 문제와 똑같다. [ Fn ] = [ 1 1 ] * [ Fn-1 ] = [ 1 1 ] * [ 1 1 ] * [ Fn-2 ] [ Fn-1 ] ..