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

import java.util.Arrays;import java.util.Collections;import java.util.Scanner;public class BJ1026 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] A = new int[N]; Integer[] B = new Integer[N]; // 내림차순 정렬을 위해 Integer 사용 // A, B 입력 for (int i = 0; i

import java.util.Scanner;public class BJ12865 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int[] weight = new int[N + 1]; // 물건의 무게 배열 int[] value = new int[N + 1]; // 물건의 가치 배열 int[][] dp = new int[N + 1][K + 1]; for (int i = 1; i  전형적인 동적계획법 문제인 배낭 채우기 문제이다.

import java.io.*;public class BJ9655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //상근 승 :SK 창영 : CY if(N%2==1) { System.out.println("SK"); }else { System.out.println("CY"); } }} 서로 홀수만 입력하기 때문에 ..

import java.util.Scanner;public class BJ1305 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int length = sc.nextInt(); String input = sc.next(); sc.close(); System.out.println(length - getPrefixTable(input, length)); } private static int getPrefixTable(String input, int length) { int[] prefixTable = new int[lengt..

import java.util.Scanner;public class BJ1904 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(countBinarySequences(N)); } public static int countBinarySequences(int n) { final int MOD = 15746; if (n == 1) { return 1; } else if (n == 2) { return 2; ..

이러한 행렬의 곱은 공학수학이나 이산수학에서 충분히 배웠다. 이때 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,..

import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class BJ18111 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken..