Algorithm (13) 썸네일형 리스트형 Merge Sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 public class Main { public static int[] src; public static int[] tmp; public static void main(String[] args) { src = new int[] { 1, 8, 5, 4, 2, 3, 7, 6 }; tmp = new int[src.length]; printArray(src); mergeSort(0, src.length - 1); printArray(src); } public static void mergeSort(int sta.. ArrayList를 활용한 모든 경우의 수 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.util.*; class Solution { static Set set = new HashSet(); public void DFS(ArrayList list, ArrayList res, int i, int n) { // 마지막 배열을 입력했을 때 if (i == 0) { return; } // 모든 경우의 수를 구하여 set에 저장 for (int j = 0; j 1) { for (i = 2; i 멱집합 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class PowerSet { private static char data[]= {'a','b','c','d'}; private static int n=data.length; private static boolean[] include = new boolean[n]; public static void powerSet(int k) { System.out.format("powerSet(%d) 호출됨.\n",k); if(n==k) { for(int i=0;i 최대합 부분배열 문제 : 길이가 n 인 정수의 배열 A[0..n-1]가 있다. A[a] + A[a+1] + … + A[b]의 값 을 최대화하는 구간 (a,b)를 찾는 방법을 Divide-and-Conquer 전략을 이용 하여 설계하고 분석하라. 예를 들어, 배열 A 가 아래와 같이 주어졌을 경우 (n = 10), 31 -41 59 26 -53 58 97 -93 -23 84 답은 a = 2, b = 6 인 경우의 59+26-53+58+97=187 가 된다. 이 문제에 대해 여러가지 방법이 있는데 가장 쉬운 방법부터 소개하겠다. 1. 부분합 수열 : O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int MaxLoof(int *arr, int n) { int i,j,tmp,res.. 소수 판별 알고리즘 어떤 수 n이 소수인지 판별하는 방법 중 가장 기본적인 것은 2부터 n-1까지 n에 대해 나눠보고 나눠지는 경우에는 소수가 아님을 판별하는 방법이 있다. 에라토스테네스 체의 특징을 이용하여 소수를 더 간단하게 구하는 방법이 있다. 예를들어 4를 소인수 분해하면 2*2가 나오고, 63을 소인수분해 해보면 3*3*7이 나온다. 이와 같이 합성수 m를 소인수분해 한 값들은 m의 제곱근보다 작거나 같음을 알 수 있다. 이를 이용하여 소수 판별 알고리즘을 작성하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include int main() { int n; int i,j; printf("판별할 수를 입력.. 이전 1 2 다음