1. Java 구현 (1) 모든 경우의 수를 적용 - 시간초과 (시간복잡도 O(n^3)) → 실패 import java.io.*; import java.util.*; public class Solution { public static void solution1() throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); int[] arr = new..
1. Java 구현 package recursive; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { /* 1. 입력 받기! */ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); char[][] arr = new char[n][n]; for (int i =..
1. Java 구현 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long a = sc.nextLong(); long b = sc.nextLong(); System.out.println(getResult(getGCD(a, b))); sc.close(); } public static long getGCD(long a, long b) { long max = Math.max(a, b); long min = Math.min(a, b); if (max % min == 0) return min; else return getGCD(max % min, mi..
유클리드 호제법 1. 유클리드 호제법 정의유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. [위키백과] 예) GCD(30, 12) = GCD(30 % 12, 12) = GCD(6, 12) = 6 예) GCD(72, 45) = GCD(72 % 45, 45) = GCD(27, 45) = GCD(45 % 27, 27) = GCD(18, 27) = GCD(27 % 18, 18) = GCD(..