글

작성일자

[Java] 우선순위 큐(Priority Queue) 활용 예제코드

자바에서 제공하는 컨테이너(Container) 중 어떤 데이터에 대해 우선순위 값을 부여하고, 이 우선순위를 기준으로 자동으로 정렬되어, 우선순위에 따라 데이터를 꺼내어 사용할 수 있는 우선순위 큐에 대한 예제 코드를 정리합니다.

먼저 우선순위 값을 갖는 데이터에 대한 타입 정의가 필요합니다. 아래처럼 Node라는 클래스를 추가해 타입을 정의합니다.

package tstPriorityQueue;

public class Node implements Comparable<Node> {
	private String UUID;
	private String parentUUID;
	private double G;
	private double H;
	
	public Node(String UUID, double G, double H) {
		this.UUID = UUID;
		this.parentUUID = null;
		this.G = G;
		this.H = H;
	}
	
	public double getF() { return G + H; }
	public double getG() { return G; }
	public double getH() { return H; }
	public String getNode() { return UUID; }
	public String getParentNode() { return parentUUID; }
	
	public void setG(double v) { G = v; }
	public void setH(double v) { H = v; }
	public void setParentNode(String v) { parentUUID = v; }
	
	@Override
	public int compareTo(Node target) {
	    if (this.getF() > target.getF()) {
            return 1;
        } else if (this.getF() < target.getF()) {
            return -1;
        }

	    return 0;
	}
	
	public String toString() {
		return UUID + '(' + getF() + ')';
	}
}

위의 클래스에서 중요한 부분은 우선순위값을 얻기 위한 getF() 함수입니다. 이 함수는 데이터의 상대적인 크기의 비교를 위한 인터페이스인 Comparable 구현할 때 사용되는 함수인데요. 바로 compareTo 라는 함수로써, 위의 경우에는 우선순위값이 작은 것을 먼저 꺼내어 사용하겠다는 정의입니다.

실제로, 위의 Node 클래스에 대한 타입으로 정의된 데이터를 컨테이너에 넣고, 사용하는 코드는 아래와 같습니다.

package tstPriorityQueue;

import java.util.PriorityQueue;

public class EntryMain {

	public static void main(String[] args) {
		// Create items
		Node node1 = new Node("423182c4-edb5-11e6-bc64-92361f002671", 1.0, 5.1);
		Node node2 = new Node("42318742-edb5-11e6-bc64-92361f002671", 1.0, 2.4);
		Node node3 = new Node("42318878-edb5-11e6-bc64-92361f002671", 1.0, 3.8);
		Node node4 = new Node("42318968-edb5-11e6-bc64-92361f002671", 1.0, 6.2);
		Node node5 = new Node("42318a3a-edb5-11e6-bc64-92361f002671", 1.0, 4.5);
		
		// Create priority queue
		PriorityQueue<Node> pQueue = new PriorityQueue<Node>();
		
		// Add items to queue
		pQueue.offer(node1); // same code as pQueue.add(node1)
		pQueue.offer(node2);
		pQueue.offer(node3);
		pQueue.offer(node4);
		pQueue.offer(node5);
		
		// Get items from queue
		while(!pQueue.isEmpty()) {
			Node node = pQueue.poll();
			System.out.println(node);
		}
	}

}

데이터를 5개 생성해서, 우선순위 큐 저장소에 저장하고 최종적으로 26번 코드를 통해 5개의 데이터를 우선순위에 따라 꺼내어 화면에 표시합니다. 그 결과는 아래와 같습니다.

42318742-edb5-11e6-bc64-92361f002671(3.4)
42318878-edb5-11e6-bc64-92361f002671(4.8)
42318a3a-edb5-11e6-bc64-92361f002671(5.5)
423182c4-edb5-11e6-bc64-92361f002671(6.1)
42318968-edb5-11e6-bc64-92361f002671(7.2)

작성일자

[C++] binary_search 정리

메모리 기반의 방대한 데이타가 있다고 가정을 할 때.. 이 데이터 목록 중 어떤 데이타가 존재하는지의 여부를 가장 빠르게 검색해주는 방식이 binary_search인데요. 이 STL 함수를 정리해 봅니다.

먼저 메모리 기반의 방대한 데이터를 준비해 봅니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };

}

데이타가 몇개 되지 않지만 방대하다고 칩시다. binary_search를 사용하기 위해서는 먼저 데이터가 정렬되어 있어야 합니다. 내림차순으로 정렬하는 코드를 추가하면.. 다음과 같습니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };
    auto predicate = [](int a, int b) { return a > b; };
    values.sort(predicate);

    copy(values.begin(), values.end(), ostream_iterator<double>{ std::cout, " "});
    cout << endl;
}

람다 함수로 내림차순 정렬을 위한 기준으로 삼았습니다. 그리고 잘 정렬되었는지 콘솔에 표시해 보았구요. 이제 binary_search 함수를 사용하기 위한 데이터 덩어리가 준비 되었고, 다음처럼 데이터 덩어리중 값 5가 존재하는지의 여부를 검색하는 코드는 다음과 같습니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };
    auto predicate = [](int a, int b) { return a > b; };
    values.sort(predicate);

    copy(values.begin(), values.end(), ostream_iterator<double>{ std::cout, " "});
    cout << endl;

    int wanted{ 5 };
    bool bSearched = binary_search(begin(values), end(values), wanted, predicate);
    if (bSearched) {
        cout << "Found !" << endl;
    } else {
        cout << "Not found." << endl;
    }
}