Knapsack

09 May 2019 Tags:

HackerRank, Dynamic Programming

HackerRank link

Knapsack

주어진 배열로 목표 합을 배열의 원소를 0번 또는 여러번 사용하여 넘치지 않고 가장 근접한 합을 만들어 리턴!!

ex) arr=[2,3,4] target sum = 10 인경우
[2,2,2,2,2] , [2,2,3,3], 등..

input
t
n k
배열 원소들

t : test case 수
n : 배열 사이즈
k : 목표 합

제약조건
1 <= t <= 10
1 <= n,k,arr[i] <= 2000

풀이 과정

먼저 심플하게 생각해 보면 모든 경우의 수를 다 해보면 풀릴 것 같다.

또한, 예시 입력을 봤을 때에도 arr[i]의 각 원소는 중복 될 수 있다.

모든 경우의 수를 다 해보면 비 효율적이므로,

첫 번째로 할만한 경우는 더하지 않고 가능한 경우이다.

어떤 수를 나눈 나머지가 0 인경우 더해볼 필요가 없다. 그럼 어떻게 나눠야 할까?

소수 구하는 방법처럼 2, 3의 곱들을 제거 해 보았다.

또한 2+3 = 5의 경우도 만들어질 수 있으므로, 제거해 보았다.

그런데 23같은 경우 2x10+3이므로 23도 지워져야 된다. 따라서, 곱셈만으로는 구하기 어려워 보인다.

이 때문에 효율적으로 모든 경우의 수를 더하여 체크한는 방법을 생각해 보았다.

재귀적으로 현재 수에서 배열의 수를 순차적으로 더하는 방법이 가능하다.

그런데, 제약 조건을 봤을 때, n,k,arr[i]이 2000이다. 사이즈가 굉장히 적다.

사이즈가 굉장히 적기 때문에, flag를 두어서 이미 체크한 경우를 생각할 수있다.

그래서 중복으로 함수를 call 할필요 없게 만들 수 있다.

또한, 입력의 중복된 원소를 제거하기 위해 오름차순으로 정렬을 한다음 중복되는 수는 제거해 준다.

풀이 핵심

제약조건이 낮기 때문에, 심플하게 재귀적으로 모든 수를 더하여 체크할 수 있다.
제약조건이 낮기 때문에, flag를 두어 중복 체크를 방지 가능

Algorithm

입력받은 수를 오름차순으로 정렬한다.
중복된 입력은 제거 한다.
재귀적으로 0부터 입력을 모두 더하여 체크 한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the unboundedKnapsack function below.
    static final int  maxInput = 2000;
    static int checkMax = 0;
    
    static void check(boolean[] isChecked, ArrayList<Integer> al, int cur, int target) {
        
        if(cur > target || cur > isChecked.length) return;
        
        if(isChecked[cur]) {
            return;
        }
        
        isChecked[cur] = true;
        
        if(checkMax < cur ) checkMax = cur;
        
        for(int e : al) {
            check(isChecked, al, cur+e, target);
        }
        
    }
    
    static int unboundedKnapsack(int k, int[] arr) {
         ArrayList<Integer> al = new ArrayList<>(); 
         boolean[] isChecked = new boolean[maxInput +1];
         checkMax = 0;
            
         Arrays.sort(arr);
         
         int i = 0;
         int before = 0;
         for(int e : arr) {
             if(before == e) {
                 continue;
             }
             
             al.add(e);
             before = e;
         }
         
         check(isChecked, al, 0,k);
         
         return checkMax;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
          BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        for(int test = 0; test < t; test++) {
            String[] nk = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nk[0]);

            int k = Integer.parseInt(nk[1]);

            int[] arr = new int[n];

            String[] arrItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int arrItem = Integer.parseInt(arrItems[i]);
                arr[i] = arrItem;
            }

            int result = unboundedKnapsack(k, arr);
            System.out.println(result);
            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }
        
        bufferedWriter.close();

        scanner.close();
    }
}

Stock Maximize

08 May 2019 Tags:

HackerRank, Dynamic Programming

HackerRank link

Stock Maximize

풀이 핵심

최댓값이 바뀌는 시점을 파악한다.
거꾸로 시작해서 최댓값이 바뀌는 시점까지 이익을 계산한다.

Algorithm

거꾸로 시작해서 최댓값이 바뀌는 시점까지 이익을 계산한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
     
    // Complete the stockmax function below.
    static long stockmax(long[] prices) {
        long max = 0;
        long profit = 0;
        
        for(int i = prices.length - 1; i >= 0; i--) {
            if(prices[i] > max) {
                max = prices[i];
            }
            
            profit += (max - prices[i]);
        }
        
        return profit;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
          
            String[] pricesItems = scanner.nextLine().split(" ");
            
            n = pricesItems.length;
                    
            long[] prices = new long[n];
            
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                long pricesItem = Long.parseLong(pricesItems[i]);
                prices[i] = pricesItem;
            }

            long result = stockmax(prices);
            System.out.println(result);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Minimum Loss

06 May 2019 Tags:

HackerRank, Search, HashMap

HackerRank link

Minimum Loss

풀이 핵심

본인 풀이

어떤 값을 둘의 차이가 최소인 두 년도를 찾아야 한다. → sort 후 앞뒤 뺌
두 값의 앞뒤가 앞은 크고 뒤는 작아야됨. → HashMap으로 판단

Editorial
이진트리를 이용한다.

Algorithm

입력 시 HashMap에 키(price)와 index를 저장한다.
sort를 한다.
차례데로 살펴 보면서 Hash 맵을 이용하여, 두 사이의 gap이 작은 부분을 캐치 한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

import javax.swing.plaf.synth.SynthSeparatorUI;

public class Solution {

    static HashMap<Long, Integer> map = new HashMap<>();
    // Complete the minimumLoss function below.
    static long minimumLoss(long[] price) {
        long min = Integer.MAX_VALUE;
        Arrays.sort(price);
        
        // 오름차순
        // 20 [7] 8 2 [5]
        // 2 5 7 8 20
        for(int i = 0; i < price.length - 1; i++) { 
            // 두 값이 뭐가 됐든 더 작은 값의 키 값이 더 커야된다.
            // 더 큰게 왼쪽 - 더 작은게 오른쪽          
            if(map.get(price[i]) - map.get(price[i+1]) > 0) {
                long dif = price[i+1] - price[i];                
                if(dif < min) min = dif;
            }
        }
        
        return min;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        long[] price = new long[n];

        String[] priceItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            long priceItem = Long.parseLong(priceItems[i]);
            price[i] = priceItem;
            map.put(priceItem, i);
        }

        long result = minimumLoss(price);
        
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

editorial

#include<assert.h>

#define pf printf
#define sf scanf

using namespace std;

typedef long long vlong;

const vlong inf = 1000000000000000000LL;


vlong arr[200005];
void solution() {

	set<vlong>st;
	set<vlong>::iterator up;

	int n;
	vlong temp, ans = inf, mx = 0;

	sf("%d", &n);
	assert(n>1 && n <= 200000);

	for (int i = 1; i <= n; i++)
	{
		sf("%lld", &arr[i]);
		assert(arr[i]>0 && arr[i] <= 10000000000000000LL);
	}

	st.insert(arr[1]);
	mx = max(mx, arr[1]);
	for (int i = 2; i <= n; i++)
	{
		if (mx > arr[i])
		{
			up = st.upper_bound(arr[i]);
			temp = *up - arr[i];
			ans = min(ans, temp);
		}
		st.insert(arr[i]);
		mx = max(mx, arr[i]);
	}

	assert(ans != inf);

	pf("%lld\n", ans);
}


int main() {

	solution();

	return 0;
}

Flipping the Matrix

28 Apr 2019 Tags:

HackerRank, Constructive Algorithms

HackerRank link

Flipping the Matrix

풀이 핵심

reverse만 하기 때문에 이동 가능한 좌표가 따로 있다.
하나씩 reverse를 이용해서 채우면 어떠한 경우에도 최대값을 위치 시킬 수 있다.

ex) 문제 예제에서
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108

(0,0)에 올 자리 : (0,0), (0, 3), (3, 0), (3, 3) 중 제일 큰값 : => 119
(0,1)에 올 자리 : (0,1), (0, 2), (3, 1), (3, 2) 중 제일 큰값 : => 114
(1,0)에 올 자리 : (1,0), (1, 3), (2, 0), (2, 3) 중 제일 큰값 : => 56
(1,1)에 올 자리 : (1,1), (1, 2), (2, 1), (2, 2) 중 제일 큰값 : => 125

모두를 더하면 414

Algorithm

위 예제에서 필요한 값을 보면,

matrix의 최대 길이 : 좌표
matrix의 절반 길이 : 반복할 횟수

아래 두 값을 이용하여 간단하게 이중 for문을 이용하여 돌려서,
각 네 좌표의 최대값을 순서데로 더한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static int max(int a, int b, int c, int d) {
        int max = 0;
        int[] arr = {a,b,c,d};
        
        for(int i : arr) {
            if(i > max) max = i;
        }
        
        return max;
    }
    
    // Complete the flippingMatrix function below.
    static int flippingMatrix(int[][] matrix) {
        int sum = 0;
        /*
         1. 0,0에 올 자리 : (0,0), (0, 3), (3, 0), (3, 3) 중 제일 큰값 : => 119
                          
         2. 0,1에 올 자리 : (0,1), (0, 2), (3, 1), (3, 2) 중 제일 큰값 : => 114
         
         3. 1,0에 올 자리 : (1,0), (1, 3), (2, 0), (2, 3) 중 제일 큰값 : => 56
         
         4. 1,1에 올 자리 : (1,1), (1, 2), (2, 1), (2, 2) 중 제일 큰값 : => 125 
         
             112 42 83 119
            56 125 56 49
            15 78 101 43
            62 98 114 108
         */
        
        int l = matrix.length / 2;
        int m = matrix.length;
        
        for(int y = 0 ; y < l ; y++) {
            for(int x = 0 ; x < l ; x++) {
                sum += max(matrix[y][x], matrix[y][m-1-x], matrix[m-1-y][x], matrix[m-1-y][m-1-x]);
            }
        }
        
        
        return sum;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[][] matrix = new int[2*n][2*n];

            for (int i = 0; i < 2*n; i++) {
                String[] matrixRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                for (int j = 0; j < 2*n; j++) {
                    int matrixItem = Integer.parseInt(matrixRowItems[j]);
                    matrix[i][j] = matrixItem;
                }
            }

            int result = flippingMatrix(matrix);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

PriorityQueue

20 Apr 2019 Tags:

Data Structure, PriorityQueue, C++

PriorityQueue

큐는 선입 선출을 위한 자료구조이다.

이 때문에 큐는 배열 또는 링크드 리스트로 구현이 가능하다.

우선순위 큐는 우선 순위가 있는 큐이다.

먼저 들어온 데이터가 우선이 되지 않고, 우선순위가 높은 데이터가 먼저나가는 구조이다.

이 때문에, Heap을 이용하여 구현한다.

Heap 구조를 이용하기 때문에 시간 복잡성은 O(logn) 이다.

Heap 구조의 갯수는 2^(h-1) <= n <= 2^h - 1 이다.

h-1 <= log2 n <= h
-1 <= log2 n -h <= 0
-log2 n -1 <= -h <= -log2 n
log2 n + 1 >= h >= log2 n
log2 n <= h <= log2 n + 1 < log2 (n+1) + 1

h = log2(n+1) = O(log2n)

추가나 삭제 시 O(logn)시간 복잡도

[추상자료형]

	name	input	output	설명
데이터 전부 삭제	clear	-	-	데이터를 전부 삭제 한다.
큐 사이즈 정보 반환	size	-	size	큐의 사이즈 정보를 반환한다.
데이터 추가	add	데이터	-	큐에 데이터를 추가한다.
데이터 poll	poll	-	데이터	큐에서 데이터를 poll 한다.
데이터 peek	peek	-	데이터	큐에서 데이터를 peek 한다.

poll은 큐에서 데이터를 완전히 받아와서 큐에서는 해당 데이터가 존재 X
peeK는 큐의 데이터를 살짝 볼 수 있도록 데이터를 받지만 삭제되지 않는다.

사용예

대표적으로 우선순위 큐는 MST(Minimal Spanning Tree)를 구현하는데 많이 사용한다.

Prim’s MST
Kruskal MST

둘다 최소의 간선을 잇는 알고리즘으로 먼저 우선순위 큐에 간선 정보를 입력하고 최소 간선을 받아서 잇는다.

다른 사용 예로는 무언가 우선순위가 필요한 시뮬레이션이라든지 이런 프로그램 구현시 사용 가능하다.

ex) 생산량이 다른 두 아르바이트 생의 커피 생산 시뮬레이션, 은행, 생산 등

Source Code

#include <iostream>

using namespace std;

class Element {
public :	
	int key;
	int item;
	Element(int key) {
		this->item = 0;
		this->key = key;
	}

	Element() {
		this->item = 0;
		this->key = 0;
	}

	// 요것만 수정하면 최대/최소로 바뀐다.
	int compare(Element newNode) {
		return this->key <= newNode.key ? -1 : 1;	// 최소 
		// return this->key >= newNode.key ? -1 : 1; // 최대
	}
};

class PriorityQueue {

private :
	int totalSize;
	int maxSize;
	Element * data;

public :
	PriorityQueue(int totalSize) {
		
		this->totalSize = 0;
		// 편의상 0번은 버릴 것이기 때문에 +1을 해준다.
		this->maxSize = totalSize+1;
		data = new Element[totalSize+1];
	}

	~PriorityQueue() {
		delete[] data;
	}

	void clear() {
		totalSize = 0;
	}

	int size() {
		return totalSize;
	}

	void add(Element newitem) {
		// 1. 일단 맨 뒤에 넣는다고 생각하고
		// 2. 상위 부모와의 역전 관계를 확인한다.

		// 예외 처리. 사실 상  초기화 시에 입력으로 올 데이터 만큼 크게 선언해준다.
		if (totalSize + 1> maxSize) {
			return;
		}


		int child = ++totalSize;
		int parent = child / 2;

		while (parent != 0) {

			// 상위 부모와의 역전 관계를 확인한다.
			// 바꾸지 말아야 한다면, 그만 한다.
			if (data[parent].compare(newitem) < 0) {
				break;
			}

			// 바꿔야 되니까 자식과 부모를 바꾸고
			data[child] = data[parent];

			// 상위로 올라가서 다시 검사한다.
			child = parent;
			parent = child / 2;
		}

		data[child] = newitem;

	}

	// 최상위 값을 보여준다.
	Element peek() {
		return data[1];
	}

	Element poll() {
		Element returnData = data[1];
		int tail = totalSize--;

		// 맨 아래가 헤드로 온다고 생각하고 들어갈 자리를 찾는다.
		int parenet = 1;
		int child = 2;

		while (child <= totalSize) {
			
			// 자식 둘중 더 최소 또는 최대에 맞는지 확인한다.
			if (child + 1 <= totalSize && data[child + 1].compare(data[child]) < 0) {
				child++;
			}

			// 바꿔야 되는지 확인한다.
			if (data[tail].compare(data[child]) < 0) {
				break;
			}

			data[parenet] = data[child];
			
			parenet = child;
			child = parenet * 2;

		}

		data[parenet] = data[tail];

		return returnData;
	}
};


int main() {

	PriorityQueue * pq = new PriorityQueue(1024);

	pq->add(Element(5));
	pq->add(Element(1));
	pq->add(Element(2));
	pq->add(Element(7));
	pq->add(Element(9));
	pq->add(Element(11));
	pq->add(Element(4));
	pq->add(Element(8));

	while (pq->size() != 0) {
		cout << pq->poll().key << endl;
	}
}

Older Newer

Power Coding 파워 코딩

Knapsack

HackerRank link

풀이 과정

풀이 핵심

Algorithm

Source Code

Stock Maximize

HackerRank link

풀이 핵심

Algorithm

Source Code

Minimum Loss

HackerRank link

풀이 핵심

Algorithm

Source Code

Flipping the Matrix

HackerRank link

풀이 핵심

Algorithm

Source Code

PriorityQueue

PriorityQueue

사용예

Source Code