고귀양이의 노트.

[ 자료1 ]에서 소개된 알고리즘을 javascript로 포팅하였습니다.

bin-packing 알고리즘은 굉장히 많이 쓴다. 

1d bin-packing의 대표적 예시가 메모리 어느 지점에 프로세스를 적재할 것인지 결정하는 알고리즘이

될 것이고, 2d bin-packing의 대표적 예시는 다양한 크기의 glyph를 atlas상에 배치 하거나,

여러 sprite 이미지를 큰 atlas이미지에 압축하는 것이 될 것이다.

                                                                               [그림1 출처]

[ 자료2 ] 에서와 같이 수많은 bin packing 알고리즘이 있지만, 개중에 하나인

skyline bottom-left bin packing algorithm를 소개하고자 한다.

 바로 본론으로 들어가서, skyline bottom-left는 빈공간을 추적하고 있는데, 이것들 node라고 한다.

이 빈공간은 아주 단순한 형태로 저장하고 있는데, [ x, y, width ]의 형태로 저장하고 있다.

x : 추적하는 빈공간 node의 왼쪽 시작 지점

y : 추적하는 빈공간 node의 위쪽 시작 지점

width : 추적하는 빈공간 node의 너비

height가 없어서 의아할 수 있는데, skyline bottome-left가 추적하는 "빈공간"을 알면 이해할 수 있다.

다음 그림을 보면,

box를 채웠을때, 생성된 node의 아래쪽은 전부 해당 node가 추적중인 "빈공간"으로 간주하기

때문에, height정보가 필요없다.

항상 box들의 아래쪽 빈공간을 추적하기 때문에 box크기가 들쑥날쑥하면, 정렬시켜서 넣던가 하는

휴리스틱들을 추가로 적용해보아햐 한다.

이제 실제 packing 과정을 살펴보자.

var bestWidth = Number.MAX_SAFE_INTEGER;
var bestHeight = Number.MAX_SAFE_INTEGER;
var bestIndex = -1;
var region = [0, 0, width, height];

//1) 모든 노드들을 돌면서 들어갈 수 있는 곳을 탐색한다.
for (var i = 0; i < this._nodes.length; ++i) {
	//1-1) fit에서 width 만큼의 node중 가장 큰 봉우리를 찾는다
	var y = this.fit(i, width, height);

	//1-2) y가 minus가 아니라면 들어갈 수 있는 봉우리를 찾았다.
	if (y >= 0) {
		var node = this._nodes[i];

		//1-3) 봉우리중에 (하늘에서)가장 낮은 놈이 best다
		if ( y + height < bestHeight || (y + height == bestHeight && node[2] < bestWidth)) {
			bestHeight = y + height;
			bestIndex = i;
			bestWidth = node[2];
			region = [node[0], y, width, height];
		}
	}
}

모든 노들을 돌면서, fit과정을 거치는데, fit은 width만큼 단순히 node들을 방문하면서 (하늘에서)가장 높은

봉우리를 찾는다. width만큼 방문하기 때문에, 높아야 겹치지 않고 배치할 수 있기 때문이다.

[그림4] 에서는 1번 node쪽 봉우리가 가장높으므로 해당 봉우리의 y값을 취한다.

그리고 그렇게 선택된 봉우리중에 가장 "낮은"값을 취하여 region( 박스가 배치될 영역 )을 갱신한다.

//2) 들어갈만한 적당한 곳이 없다
if (bestIndex == -1) {
	return undefined;
}

//3) 적당한 곳이 결정되어 node를 넣는다.
var node = [region[0], region[1] + height, width];
this._nodes.insert(bestIndex, node);

//4) 현재 노드가 들어감으로 기존노드와 겹침이 있을 수 있으므로 shrink작업을 한다
var i = bestIndex + 1;
while (i < this._nodes.length) {
	node = this._nodes[i];
	var prevNode = this._nodes[i - 1];

	//4-1) 이전 노드의 위치 + width 보다 작다 => 겹친다
	if (node[0] < prevNode[0] + prevNode[2]) {
		var shrink = prevNode[0] + prevNode[2] - node[0];

		var x = node[0];
		var y = node[1];
		var w = node[2];

		//4-2) shrink
		this._nodes[i][0] = x + shrink;
		this._nodes[i][1] = y;
		this._nodes[i][2] = w - shrink;

		//4-3) width가 minus라면 그 node는 삭제
		if (this._nodes[i][2] <= 0) {
			this._nodes.splice(i, 1);
			i -= 1;
		}
	} else {
		break; // 겹침이 없다면 괜춘괜춘
	}

	i += 1;
}

그리고 그렇게 배치가 되면 새로운 빈공간( 새로 배치된 박스의 아래부분 )이 생기므로 node를 추가한다.

새로운 node가 들어감으로, 기존 노드와의 영역다툼 해소를 위해 shrink를 해준다.

이때, shrink도중 음수가 나오게 되면 해당 node는 invalid로 제거한다.

//5) y위치가 같은 노드가 있다면 하나의 node로 만든다
this.merge();

//6) 사용량 추적용
this._used += width * height;

return region;

마지막으로, y위치( = 봉우리)가 같은 node가 있다면, merge하여 하나의 node로 만들어서 여러모로 계산도 줄이고,

최적화를 한다. 그리고 region을 반환하면 끝!

+ full source

Array.prototype.insert = function (index, item) {
  this.splice(index, 0, item);
};

class RectBox {
  constructor(x, y, width, height, color) {
    this._x = x;
    this._y = y;
    this._width = width;
    this._height = height;
    this._color = color;

    this.render = this.render.bind(this);
  }

  render(context) {
    context.fillStyle = this._color;
    context.fillRect(this._x, this._y, this._width, this._height);
  }
}

class Bin {
  constructor() {
    this._handle = null;

    this.addRect = this.addRect.bind(this);
    this.fill = this.fill.bind(this);
    this.draw = this.draw.bind(this);

    this.pack = this.pack.bind(this);
    this.fit = this.fit.bind(this);
    this.merge = this.merge.bind(this);

    var canvas = document.getElementById("myCanvas");
    var addButton = document.getElementById("addRect");
    addButton.onclick = this.addRect;

    this._canvasContext = canvas.getContext("2d");

    this._width = 512;
    this._height = 512;
    this._nodes = [[0, 0, this._width]];
    this._used = 0;

    this._rects = [];
  }

  fill() {
    var width = Math.floor(Math.random() * 100 + 30); // 30 ~ 130
    var height = Math.floor(Math.random() * 100 + 30); // 30 ~ 130

    var region = this.pack(width, height);
    if (undefined == region) {
      return;
    }

    var color = "#" + (((1 << 24) * Math.random()) | 0).toString(16);

    var newRect = new RectBox(
      region[0],
      region[1],
      region[2],
      region[3],
      color
    );
    this._rects.push(newRect);

    this.draw();
  }

  addRect() {
    this.fill();
  }

  draw() {
    for (var i = 0; i < this._rects.length; ++i) {
      this._rects[i].render(this._canvasContext);
    }
  }

  fit(index, width, height) {
    var node = this._nodes[index];
    var x = node[0];
    var y = node[1];
    var widthLeft = width;

    if (x + width > this._width) {
      return -1;
    }

    var i = index;
    while (widthLeft > 0) {
      node = this._nodes[i];
      y = Math.max(y, node[1]);
      if (y + height > this._height) {
        return -1;
      }

      widthLeft -= node[2];
      i += 1;
    }

    return y;
  }

  merge() {
    var i = 0;
    while (i < this._nodes.length - 1) {
      var node = this._nodes[i];
      var nextNode = this._nodes[i + 1];
      if (node[1] == nextNode[1]) {
        this._nodes[i][0] = node[0];
        this._nodes[i][1] = node[1];
        this._nodes[i][2] = node[2] + nextNode[2];
        this._nodes.splice(i + 1, 1);
      } else {
        i += 1;
      }
    }
  }

  pack(width, height) {
    var bestWidth = Number.MAX_SAFE_INTEGER;
    var bestHeight = Number.MAX_SAFE_INTEGER;
    var bestIndex = -1;
    var region = [0, 0, width, height];

    //1) 모든 노드들을 돌면서 들어갈 수 있는 곳을 탐색한다.
    for (var i = 0; i < this._nodes.length; ++i) {
      //1-1) fit에서 width 만큼의 node중 가장 큰 봉우리를 찾는다
      var y = this.fit(i, width, height);

      //1-2) y가 minus가 아니라면 들어갈 수 있는 봉우리를 찾았다.
      if (y >= 0) {
        var node = this._nodes[i];

        //1-3) 봉우리중에 (하늘에서)가장 낮은 놈이 best다
        if (
          y + height < bestHeight ||
          (y + height == bestHeight && node[2] < bestWidth)
        ) {
          bestHeight = y + height;
          bestIndex = i;
          bestWidth = node[2];
          region = [node[0], y, width, height];
        }
      }
    }

    //2) 들어갈만한 적당한 곳이 없다
    if (bestIndex == -1) {
      return undefined;
    }

    //3) 적당한 곳이 결정되어 node를 넣는다.
    var node = [region[0], region[1] + height, width];
    this._nodes.insert(bestIndex, node);

    //4) 현재 노드가 들어감으로 기존노드와 겹침이 있을 수 있으므로 shrink작업을 한다
    var i = bestIndex + 1;
    while (i < this._nodes.length) {
      node = this._nodes[i];
      var prevNode = this._nodes[i - 1];

      //4-1) 이전 노드의 위치 + width 보다 작다 => 겹친다
      if (node[0] < prevNode[0] + prevNode[2]) {
        var shrink = prevNode[0] + prevNode[2] - node[0];

        var x = node[0];
        var y = node[1];
        var w = node[2];

        //4-2) shrink
        this._nodes[i][0] = x + shrink;
        this._nodes[i][1] = y;
        this._nodes[i][2] = w - shrink;

        //4-3) width가 minus라면 그 node는 삭제
        if (this._nodes[i][2] <= 0) {
          this._nodes.splice(i, 1);
          i -= 1;
        }
      } else {
        break; // 겹침이 없다면 괜춘괜춘
      }

      i += 1;
    }

    //5) y위치가 같은 노드가 있다면 하나의 node로 만든다
    this.merge();

    //6) 사용량 추적용
    this._used += width * height;

    return region;
  }
}

var s_bin = null;
window.onload = () => {
  s_bin = new Bin();
};

Complete binary tree

단 두개의 자식 노드만 갖는 "이진 트리"중 노드가 왼쪽부터 차례대로 채워져 있는 트리를 말한다.

위 그림의 왼쪽은 왼쪽부터 차례대로 채워져 있으므로 완전 이진 트리이다.

(3번 노드의 자식 노드 두개가 모두 채워질 경우 "포화 이진 트리"가 된다.)

오른쪽은 2번 노드의 왼쪽 자식 노드가 비어있고 오른쪽 자식 노드가 채워져 있으므로

완전 이진 트리를 만족하지 못한다.

Heap

개발자 채용 필기 테스트에 단골로 나오는 자료구조이므로 잘 알아두자.

최소 힙을 기준으로 부모 노드가 항상 자식 노드보다 작은 형태의 "완전 이진 트리"를 말한다.

보통 배열로 간단하게 구할 수 있다. 배열로 구현시 (부모 노드 인덱스 = 자식 노드 인덱스 / 2)

(왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2) (오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1)

로 인덱싱을 쉽게 할 수 있다.

우선 순위 큐(priopriority queue)의 구현시 가장 많이 쓰는 구조가 바로 Heap이다.

최소 힙의 조건에 의해 root 노드는 항상 전체 노드중 가장 작은 값이 위치하게 된다.

삽입, 삭제만 알면 간단히 구현할 수 있다.

삽입

현재 그림과 같은 Heap이 있다고 하자. Heap의 삽입은 먼저 가장 끝의 노드에 이루어진다.

여기에 "2"를 추가해 보자. 그럼 다음과 같이 추가가 될 것이다.

부모 노드는 항상 자식 노드 보다 작아야 한다. 현재 새로 추가된 2보다 부모 노드인 6이 더 크므로

최소 힙을 만족하지 못한다. 따라서, 둘이 swap을 해준다.

swap후 또 부모 노드를 보니 여전히 최소 힙을 만족하지 못한다. 다시 swap을 한다.

이제서야 최소 힙을 만족하는 형태가 되었다. 이처럼 삽입의 경우 가장 마지막 노드에 새 노드를 추가한 후

부모 노드 보다 커지거나 루트 노드가 될 때 까지 swap을 해준다.

비교 노드의 인덱스가 1/2씩 줄음으로 시간 복잡도는 O(logN) 이다.

삭제

힙의 삭제는 루트 노드에서 이뤄진다. 따라서 2가 pop되어 삭제가 되고 마지막 노드가 루트 노드가 된다.

삽입과 달리 이번에는 최소 힙을 만족 하기 위해 루트 노드로부터 자식 노드로 비교를 한다.

왼쪽 자식 노드 부터 확인하는데 마침 3이므로 swap한다.

다시 자식 노드를 확인 해 보니 7이므로 종료한다. 삽입과 동일한 과정을 반대로 할 뿐이므로

시간 복잡도는 O(lonN)이다.

Code

위 삽입, 삭제 기능만 잘 구현하면 된다.

#include <iostream>
using namespace std;

class Heap {
private:
	int* nodes;
	int size;
	int capacity;

public:
	Heap(int defaultCapacity) {
		this->capacity = defaultCapacity;
		this->size = 0;
		this->nodes = new int[this->capacity];
	}

	~Heap() {
		delete this->nodes;
	}

	void add(int data) {
		// 예외 발생( 크기 재할당을 해주어도 된다 )
		if (this->size >= this->capacity)
			throw this->size;

		// 배열로 구현 시 인덱스는 1부터 시작
		this->nodes[++this->size] = data;

		// 순위 조정
		int i = this->size;
		while (i > 1 && this->nodes[i] < this->nodes[i / 2]) {
			swap(i, i / 2);
			i /= 2;
		}
	}

	int pop() {
		// 예외 발생
		if (this->size == 0)
			throw this->size;

		// 첫번째 원소 반환 후 마지막 원소를 첫번째에 대입
		int ret = this->nodes[1];
		this->nodes[1] = this->nodes[this->size--];

		// 조정
		int i = 1;
		while (this->size >= (i * 2 + 1)) {
			if (this->nodes[i] > this->nodes[i * 2]) {
				swap(i, i * 2);
				i *= 2;
			}
			else if (this->nodes[i] > this->nodes[i * 2 + 1]) {
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else {
				break;
			}
		}

		return ret;
	}

	void printAll() {
		if (this->size == 0) {
			cout << "This heap has no element." << endl;
			return;
		}

		cout << "size : " << this->size << endl;
		for (int i = 1; i <= this->size; i++) {
			cout << this->nodes[i] << " ";
		}
		cout << endl;
	}

private:
	void swap(int idx1, int idx2) {
		int tmp = this->nodes[idx1];
		this->nodes[idx1] = this->nodes[idx2];
		this->nodes[idx2] = tmp;
	}
};

그래프에서 하나의 노드로부터 각 노드까지의 최단 거리를 구하기 위한 알고리즘으로,

코딩 테스트의 경로 탐색 문제를 해결하기 위해 기본적으로 알아야 한다.

다익스트라와 달리 모든 노드 쌍에 관한 최단 거리를 구하는 '플로이드-워셜 알고리즘'이 있다.

(다익스트라를 각 노드에 대해 구하면 동일하게 모든 쌍에 관한 최단 거리를 구할 수 있다.)

동작

 dist[i] = min( dist[i], dist[j] + wieght[j][i] )

(i노드까지의 최단거리) = (현재 i 노드까지의 최단거리), (이전 노드 j까지의 최단거리 + j 에서 i까지 거리)

두 값중 작은 값을 취하면 된다. 위 공식을 시작 노드로부터 점진적으로 진행시키면 된다.

BFS와 같이 queue를 이용하여 다음 노드로 진행 시키는데, 우선 순위 큐(힙)을 사용하면

업데이트 횟수가 줄어들어 더 빠르게 진행할 수 있다. (여기서도 우선 순위 큐로 설명한다.)

먼저 최단 거리를 저장한 배열을 선언하고 시작 노드(0번)에 거리(시작이므로 0)를 표시한 뒤,

나머지 노드에 INF(무한한값, 보통 -1로 둔다.)으로 채워 넣고, queue에 시작 노드를 넣는다.

    1. queue에서 데이터를 꺼내어(0번) 연결된 모든 노드(1, 3번)의 거리를 계산하고 기록한 뒤,

       기록된 거리값으로 queue에 삽입한다.

    2. queue에서 데이터를 꺼내어(최소힙이므로 1번) 연결된 모드 노드(3번)의 거리를 계산하여 더 작으므로

       업데이트 한다. 업데이트 되었으므로 다시 queue에 삽입한다.

    3. queue에서 데이터를 꺼내고(3번) 연결된 모든 노드(2, 4번)의 거리 계산 후 기록한 뒤, queue에 삽입한다.

       구현에 따라 다르지만, 현재 queue에 거리4로 먼저 넣은 3번 노드가 있지만 거리3으로 구한 것이 최단이므로,

       무시된다. 최소힙으로 구현하는 이점이다.

    4. queue에서 데이터를 꺼내어(2번) 연결된 모든 노드(1번)의 거리를 계산하지만 이미 1번에 더 작은 값이 있으므로,

       무시된다. 또 데이터를 꺼내어(4번) 연결된 모든 노드(5번)에 대해 계산하여 갱신 시킨다. 그 후 queue에 넣는다.

    5. queue에서 데이터를 꺼내어(5번) 연결된 모든 노드(4번)에 대해 계산하지만 이미 작은 값이 있어 무시된다.

       queue에 더이상 데이터가 없으므로 알고리즘을 종료한다.

    6. 시작 노드(0번)으로부터 각 노드까지의 최단 거리가 다 구해졌다.

코드

public class graph {
	// 최소힙에 넣기 위해 정의한 (노드번호, 거리)쌍의 클래스
	private class _pair implements Comparable<_pair> {
		public int dst;
		public int weight;
		public _pair(int d, int w) {
			this.dst = d;
			this.weight = w;
		}

		// 비교를 위해 Override
		@Override
		public int compareTo(_pair target) {
			return this.weight <= target.weight ? -1 : 1;
		}
	}
    
	private ArrayList<_pair>[] adjList; // 인접 리스트
	private PriorityQueue<_pair> queue; // 우선 순위 큐
	private int[] shortestDist;         // 최단 거리 배열
	
	public graph(int n) {
		adjList = new ArrayList[n];
		shortestDist = new int[n];
		
		Arrays.fill(shortestDist, -1);
		for (int i = 0; i < n; i++) {
			adjList[i] = new ArrayList();
		}
		queue = new PriorityQueue<>();
	}
	
	// 간선 추가
	public void addEdge(int src, int dst, int w) {
		this.adjList[src].add(new _pair(dst, w));
	}
	
	// 다익스트라
	public void dijkstra(int start) {
		// 시작 노드 삽입, 거리 행렬 기록
		queue.offer(new _pair(start, 0));
		shortestDist[start] = 0;
		
		// 큐에 데이터가 없을 때까지
		while (!queue.isEmpty()) {
			_pair p = queue.poll();
			
			for (_pair adj : adjList[p.dst]) {
				int dist = adj.weight + p.weight;
				
				// 계산된 거리가 기록되어있는 거리보다 작거나
				// INF값( -1 )일 경우
				if (dist < shortestDist[adj.dst] || shortestDist[adj.dst] == -1) {
					shortestDist[adj.dst] = dist;
					
					queue.offer(new _pair(adj.dst, dist));
				}
			}
		}
	}
	
	// 최단 거리 배열 출력
	public void printDist() {
		for (int i : shortestDist) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

public class Main {

	public static void main(String[] args) {
		graph g = new graph(6);
		
		g.addEdge(0, 1, 1);
		g.addEdge(0, 3, 4);
		g.addEdge(1, 3, 2);
		g.addEdge(2, 1, 1);
		g.addEdge(3, 2, 8);
		g.addEdge(3, 4, 8);
		g.addEdge(4, 2, 3);
		g.addEdge(4, 5, 2);
		g.addEdge(5, 4, 1);
		
		g.dijkstra(0);
		
		g.printDist();
	}
}