Development Palette

담을 수 있는 무게가 정해져 있는 가방(Knapsack)에 쪼갤 수 없는 짐을 담지 않거나 담았을 때 (0/1) 최적의 가치를 찾는 알고리즘 배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다. 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부르고, 동적계획법(Dynamic Programming)으로 풀 수 있다. 참고로, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem)라 부르고, 그리디 알고리즘으로 풀 수 있다. 배낭 문제 - 위키백과, 우리 모두의 백과사전 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하..

서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들. 즉, 교집합이 없다. Union - Find 알고리즘은 대표자를 정해 특정 멤버가 대표하여 각 집합을 구분한다. Union - Find 알고리즘의 집합연산 세가지 Make - Set(x) : 각 원소를 대표자로 하는 집합 만들기 Find - Set(x) : x가 속한 그룹의 대표자 찾기 Union(x, y) : x가 속한 그룹과 y가 속한 그룹을 합치기.. 이때 Find - Set을 이용해 대표자를 찾아 비교하여 소속그룹인지 확인한다. 연산의 효율을 높이기 위한 방법 Rank를 이용한 Union 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장. 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class AdjMatrixTest { static int N; // 정점 개수 static boolean[][] adjMatrix; // 인접행렬 (가중치 없음) public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedRead..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class AdjListTest { static class Node{ int vertex; // 인접정점 인덱스 Node link; public Node(int vertex, Node link) { this.vertex = vertex; this.link = link; } @Override public String toString() { return "Node [vertex=..

Q. 정사각형으로 이루어진 공간에 초록은 1, 하양은 0으로 나타낸다. 다양한 크기를 갖는 정사각형의 각각 색깔별 갯수는? package com.ssafy.w0819; //분할정복 public class MakeSpaceTest_분할정복 { static int white, green; static int [][] spaces; public static void main(String[] args) { int n = 8; spaces = new int [][] { {1,1,0,0,0,0,1,1}, {1,1,0,0,0,0,1,1}, {0,0,0,0,1,1,0,0}, {0,0,0,0,1,1,0,0}, {1,0,0,0,1,1,1,1}, {0,1,0,0,1,1,1,1}, {0,0,1,1,1,1,1,1}, {0,0,..

너비우선탐색 (Breadth First Search, BFS) 루트 노드의 자식노드들을 먼저 모두 차례로 방문, 이렇게 방문했던 자식 노드들의 그 자식들을 차례로 방문하는 방식. 즉, 루트 -> 자식1 -> 자식2 -> 자식3 -> 손자(?)1 -> 손자2.. 이런식 Queue 사용 : 인접한 노드들을 탐색 후, 차례로 다시 너비(높이(레벨)가 같은) 우선 탐색을 해야함.. 따라서 선입선출을 이용해야한다 이때 index를 이용해 탐색한다. 즉, Integer타입 (왼쪽자식은 x2, 오른쪽자식은 x2+1) Queue q = new LinkedList(); 깊이우선탐색 (Depth First Search, DFS) 루트 노드에서 출발해 깊이 탐색하다가 더 이상 갈 수 없으면, 가장 마지막에 만났던 노드로 돌..

package com.ssafy.w0812.permutation; import java.util.Arrays; // w0803.p - PermutationTest2.java 비트마스크응용; // N개의 서로 다른 수에서 뽑는 순열 public class PermutationTest_Bitmasking { static int N=3,R=3;// --> 3개중에 2개뽑기 3x2 //static int N=3,R=3; //static int N=3,R=1; static int[] input; static int[] numbers; private static void permutation(int cnt, int flag) { if(cnt == R) { System.out.println(Arrays.toStrin..

- 현 순열에서 사전 순으로 다음 순열 생성 - 자바는 네퍼의 API가 없으므로 직접 구현해야함.. - 네퍼로 순열을 생성하는 것을 응용하여 조합을 할 수 있다. - 주의 : 네퍼 하기 전 오름차순 정렬 후, 가장 작은 순열을 먼저 처리 해야한다. 순열 package com.ssafy.w0812.permutation; import java.util.Arrays; public class NextPermutationTest { public static void main(String[] args) { int[] input = {7,1,4}; Arrays.sort(input); // 가장 작은 순열 만들기 , 1,4,7 do { // 순열 사용 System.out.println(Arrays.toString(in..