생각정리하기

# docker 초기화

$ docker rm -f `docker ps -aq`

# k8s 초기화

$ kubeadm reset

$ systemctl restart kublet

# iptables에 있는 데이터를 청소하기 위해

$ reboot 

brew 을 통해 mariadb설치

$ brew install mariadb 

서비스 시작

$ brew services start mariadb

$ mysql -uroot

여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다. 

2
6 10
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4
6 17
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4

24 3
laptop
camera
grinder
30 4
laptop
camera
xbox
grinder

이 문제는 DP(Dynamic Programming) 문제로 유명하다는 Knapsack문제의 변형문제라고 한다. 

이 문제는 다르게 표현하면, 정해진 weight ( 즉, 캐리어의 용량 ) 내에서 최대 절박도를 구하는 문제다. 

구해야 하는 출력값에는 절박도, 물건 개수, 물건 이름이 있다. 

먼저 최대 절박도를 구해보자 .

식으로 간단히 표현해봤다. 

DP에서 가장 중요한 부분은 개인적인 의견으로 기저부분이라고 생각한다.. 

먼저 기저부분을 작성해준다. 

다음 논리적인 식을 적어주면된다. 현재 아이템을 선택 안 할때와 했을 때 절박도 중 최대값을 구해서 return해주면 절박도의 최대값을 구할 수 있다. 

But. 우리가 원하는 출력값에는 물건개수와 물건이름도 알아야한다. 

위의 식만 이용해선 물건개수와 물건이름을 알 수없다. 

아래 식을 추가해준다. 

이렇게 물건개수와 물건이름 또한 구할 수 있다. 

* 출처 : getItemList부분은 "알고리즘 문제해결 전략" 책을 참고하여 풀었습니다. 

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class Packing {

static int cache[][]  = new int[1001][100];

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int c = scanner.nextInt();

List<String> items = null;

for ( int i = 0 ; i < c ; i++) {

int n = scanner.nextInt();

int w = scanner.nextInt();

List<Stuff> stuffs = new ArrayList<Stuff>();

items = new ArrayList<String>();

for ( int j = 0 ; j < n ; j ++  ) {

String name = scanner.next();

int weight = scanner.nextInt();

int hope = scanner.nextInt();

Stuff stuff = new Stuff(name, weight, hope);

stuffs.add(stuff);

}

for (int j = 0; j < 1001 ; j++) {

for(int k = 0; k < 100 ; k++) {

cache[j][k] = -1;

}

}

int point = 0;

int hope = findMaxHope(stuffs, w, point);;

getItemList(stuffs, w, point, items );

System.out.println(hope + " "+items.size());

for ( int j = 0 ; j < items.size() ; j++ ) {

System.out.println(items.get(j));

}

}

}

private static void getItemList(List<Stuff> stuffs, int w, int point, List<String> items )

{

if( point == stuffs.size() ) {

return;

}

if( w <= 0 ) {

return;

}

// 두 값이 다르다면  , 최대 절박도를 얻을 수 있다. 

    if (findMaxHope(stuffs, w, point) == findMaxHope(stuffs, w, point+1))

    getItemList(stuffs, w, point + 1, items);

    else

    {

    items.add(stuffs.get(point).getName());

    getItemList(stuffs, w - stuffs.get(point).getWeight() , point + 1, items);

    }

}

private static int findMaxHope(List<Stuff> stuffs, int w, int point) {

// 기저부분 

if( point == stuffs.size() ) {

return 0;

}

if( w <= 0 ) {

return 0;

}

if( cache[w][point] != -1) {

return cache[w][point];

}

// hope는 절박도 

int hope = 0;

// 현재 아이템을 선택하지 않는 경우 ( 무게가 무거워 베낭에 담을 수 없을 시 )

hope = findMaxHope(stuffs, w, point+1);

// 현재 아이템을 선택할 경우 

if( w >= stuffs.get(point).getWeight() )

{

int rhope = ( findMaxHope(stuffs, w - stuffs.get(point).weight , point+1) ) + stuffs.get(point).hope ;

if( rhope > hope ) {

hope = rhope;

}

}

cache[w][point] = hope;

return hope;

}

static class Stuff {

String name;

int weight;

int hope;

public Stuff(String name, int weight, int hope) {

this.name = name;

this.weight = weight;

this.hope = hope;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getWeight() {

return weight;

}

public void setWeight(int weight) {

this.weight = weight;

}

public int getHope() {

return hope;

}

public void setHope(int hope) {

this.hope = hope;

}

}

}

n    data anwer

4    [[0,0],[1,1],[0,2],[2,0]]    3

int n;

// x,y포인트을 저장 변수

int data[n][2];

for ( int I = 0 ; I < n ; I++) {

      data[I][0] = x좌표;

      data[I][1] = y좌표;

}

// 첫번째 쐐기

for (  I = 0 ; I < 쐐기의 수 - 1 ; I++) {

// 두번째 쐐기

for ( j = I+1 ; j < 쐐기의 수 : j++ ) {

// 두 쐐기가 같은 행이나 열에 있는 경우 제외 

       if(data[i][0] == data[j][0] || data[i][1] == data[j][1] )

      {

        continue;

      }

      // 두 쐐기를 통해 사각형을 만들었을 때, 각 좌표값들을 저장

int endX = Math.max(data[j][0], data[i][0]);

int startX = Math.min(data[j][0], data[i][0]);

int endY = Math.max(data[j][1], data[i][1]);

int startY = Math.min(data[j][1], data[i][1]);

}

}

answer값 출력