너T야? 나 T(story)야….

이러한 행렬의 곱은 공학수학이나 이산수학에서 충분히 배웠다. 이때 Aik, b kj로 k가 왼쪽 식에는 오른쪽에, 오른쪽은 왼쪽에 적혀 있는건 두개가 같을 경우에 연산이 되기 때문이다. 분할 정복의 아이디어로는 다음과 같다. // r 배열은 행렬들의 행과 열의 수를 저장// i부터 j까지의 행렬을 곱할 때 최소 곱셈 횟수를 반환하는 함수public static int matMult_DC(int[] r, int i, int j) { // 기저 조건: 행렬이 하나일 경우 곱셈이 필요하지 않음 if (i == j) return 0; int minVal = Integer.MAX_VALUE; // 최소 곱셈 횟수를 무한대 값으로 초기화 // i부터 j-1까지의 k를 기준으로 분할하여 최소 곱..

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위한 알고리즘 기법으로, 문제를 작은 하위 문제들로 나누고, 각 하위 문제의 해를 저장하여 필요할 때 다시 사용함으로써 전체 문제를 효율적으로 해결하는 방법이다. DP는 특히 중복되는 하위 문제(subproblems)를 가진 문제에서 매우 유용하다. 즉 앞에서 설명한 분할 계획을 조금 더 효율적으로 할 수 있는 것이다.  동적 계획법의 핵심 개념최적 부분 구조: 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.예를 들어, 최단 경로 문제에서는 전체 경로의 최단 거리는 경로의 부분 문제에서도 항상 최단 거리로 구성될 수 있다.중복되는 하위 문제: 동일한 하위 문제가 여러 번 반복해서 계산되는 경우가 있어야 ..

분할 정복(Divide and Conquer)이란?큰 문제를 해결하기 어려울 때 작은 하위 문제들로 나누어서 해결하는 문제 해결 전략이다.이 방식은 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해답을 구한다. 분할 정복의 세 단계분할(Divide): 문제를 여러 개의 하위 문제로 나눈다. 이때, 하위 문제들은 원래 문제와 동일하거나 유사한 형태를 가져야 한다.정복(Conquer): 각 하위 문제를 재귀적으로 해결한다. 이 단계에서 하위 문제들이 충분히 작아지면 직접 해결할 수 있다.병합(Combine): 하위 문제의 해답을 모아서 원래 문제를 해결한다.분할 정복의 특징재귀적 접근: 문제를 계속해서 더 작은 문제로 나누고, 각 문제를 재귀적으로 해결한다.효율적 탐색: 분할을 통해 문제의..

import java.util.Scanner;public class BJ1476 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int E = sc.nextInt(); // 지구를 나타내는 수 int S = sc.nextInt(); // 태양을 나타내는 수 int M = sc.nextInt(); // 달을 나타내는 수 int year = 1; // 우리가 알고 있는 연도, 1부터 시작 int e = 1, s = 1, m = 1; // 각각의 수를 1로 초기화 while (true) { // E, S,..