빈 패킹(Bin Packing) 문제란 서로 다른 무게를 가진 m개의 원소와 각각 용량이 C인 빈(bin)들이 주어졌을 때, 모든 원소를 빈에 할당하면서 사용되는 빈의 총 개수를 최소화하는 문제입니다. 단, 모든 원소의 무게는 빈의 용량보다 작다는 조건을 전제로 합니다.
빈 패킹 문제의 실제 응용 분야
여러 디스크에 데이터 배치하기
트럭 등 컨테이너 화물 적재
라디오/TV 방송의 고정 광고 시간대에 광고 배치하기
작업(Job) 스케줄링
문제 예시
입력: weight[] = {4, 1, 8, 1, 4, 2}
빈 용량 c = 10
출력: 2
모든 원소를 담으려면 최소 2개의 빈이 필요합니다.
첫 번째 빈: {4, 4, 2}, 두 번째 빈: {8, 2}하한선(Lower Bound) 계산하기
필요한 최소 빈 수의 하한선은 ceil() 함수를 이용해 항상 계산할 수 있습니다.
최소 빈 수 >= ceil((전체 무게의 합) / (빈 용량))
위 예시의 경우 하한선은 "ceil((4 + 1 + 8 + 1 + 4 + 2) / 10)" = 2 입니다.
빈 패킹은 NP-hard 문제이므로, 실제로는 아래와 같은 근사(Approximation) 알고리즘들을 활용합니다.
온라인(Online) 알고리즘
온라인 알고리즘은 원소가 한 번에 하나씩 순서를 예측할 수 없는 상태로 도착하고, 다음 원소를 살펴보기 전에 현재 원소를 반드시 어떤 빈에 넣어야 하는 상황에 적합합니다.
1. Next Fit (다음 핏)
다음 원소를 처리할 때, 직전 원소가 들어간 같은 빈에 담길 수 있는지만 확인합니다. 담을 수 없을 때만 새로운 빈을 만듭니다.
C++ 구현 코드
// Next Fit 알고리즘으로 필요한 빈의 개수를 계산하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// Next Fit 온라인 알고리즘으로 필요한 빈의 수를 반환
int nextFit(int weight1[], int m, int C){
// 결과(빈 개수)와 현재 빈의 남은 용량 초기화
int res = 0, bin_rem = C;
// 원소를 하나씩 배치
for (int i = 0; i < m; i++) {
// 현재 빈에 이 원소가 들어갈 수 없는 경우
if (weight1[i] > bin_rem) {
res++; // 새 빈 사용
bin_rem = C - weight1[i];
}
else
bin_rem -= weight1[i];
}
return res;
}
// 드라이버 코드
int main(){
int weight1[] = { 3, 6, 5, 8, 2, 4, 9 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in Next Fit : "
<<nextFit(weight1, m, C);
return 0;
}실행 결과
Number of bins required in Next Fit : 4
Next Fit은 매우 단순한 알고리즘으로, m개의 원소를 처리하는 데 O(m) 시간과 O(1) 추가 공간만 필요합니다.
2. First Fit (첫 번째 핏)
다음 원소를 처리할 때, 기존 빈들을 순서대로 검색하여 해당 원소가 들어갈 수 있는 첫 번째 빈에 배치합니다. 기존 빈 어디에도 들어갈 수 없다면 그때 새 빈을 만듭니다.
C++ 구현 코드
// First Fit 알고리즘으로 필요한 빈의 개수를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// First Fit 온라인 알고리즘으로 필요한 빈의 수를 반환
int firstFit(int weight1[], int m, int C){
// 결과(빈 개수) 초기화
int res = 0;
// 각 빈의 남은 공간을 저장할 배열 생성 (최대 n개의 빈 가능)
int bin_rem[m];
// 원소를 하나씩 배치
for (int i = 0; i < m; i++) {
// weight1[i]를 담을 수 있는 첫 번째 빈 탐색
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i]) {
bin_rem[j] = bin_rem[j] - weight1[i];
break;
}
}
// weight1[i]를 담을 수 있는 빈이 없는 경우
if (j == res) {
bin_rem[res] = C - weight1[i];
res++;
}
}
return res;
}
// 드라이버 코드
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in First Fit : "
<<firstFit(weight1, m, C);
return 0;
}실행 결과
Number of bins required in First Fit : 4
위 구현의 시간 복잡도는 O(m²)이지만, 자가 균형 이진 탐색 트리(Self-Balancing BST)를 활용하면 O(m log m) 시간으로 개선할 수 있습니다.
3. Best Fit (최적 핏)
Best Fit의 핵심 아이디어는 다음 원소를 가장 꽉 차게 담을 수 있는 위치, 즉 원소를 넣었을 때 남는 공간이 최소가 되는 빈에 배치하는 것입니다.
C++ 구현 코드
// Best Fit 알고리즘으로 필요한 빈의 개수를 계산하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// Best Fit 온라인 알고리즘으로 필요한 빈의 수를 반환
int bestFit(int weight1[], int m, int C){
// 결과(빈 개수) 초기화
int res = 0;
// 각 빈의 남은 공간을 저장할 배열 생성
int bin_rem[m];
// 원소를 하나씩 배치
for (int i = 0; i < m; i++){
// weight1[i]를 담을 수 있는 최적의 빈 탐색
int j;
// 최소 남은 공간과 최적 빈의 인덱스 초기화
int min = C + 1, bi = 0;
for (j = 0; j < res; j++){
if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
bi = j;
min = bin_rem[j] - weight1[i];
}
}
// weight1[i]를 담을 수 있는 빈이 없으면 새 빈 생성
if (min == C + 1) {
bin_rem[res] = C - weight1[i];
res++;
}
else // 최적의 빈에 원소 배치
bin_rem[bi] -= weight1[i];
}
return res;
}
// 드라이버 코드
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in Best Fit : "
<<bestFit(weight1, m, C);
return 0;
}실행 결과
Number of bins required in Best Fit : 4
Best Fit 역시 자가 균형 이진 탐색 트리를 활용하면 O(m log m) 시간 안에 수행할 수 있습니다.
오프라인(Offline) 알고리즘
오프라인 버전에서는 모든 원소를 미리 알고 있는 상태에서 문제를 풉니다. 온라인 알고리즘의 약점은 크기가 큰 원소를 담기 어렵다는 점인데, 특히 큰 원소가 시퀀스의 뒤쪽에 나타나면 더욱 불리해집니다. 이 문제는 입력 시퀀스를 정렬하여 큰 원소부터 먼저 배치함으로써 개선할 수 있습니다.
First Fit Decreasing (내림차순 정렬 First Fit)
모든 무게를 내림차순으로 정렬한 후 First Fit을 적용하는 방식입니다.
C++ 구현 코드
// First Fit Decreasing 알고리즘으로 필요한 빈의 개수를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
/* 위에서 정의한 firstFit() 재사용 */
int firstFit(int weight1[], int m, int C){
// 결과(빈 개수) 초기화
int res = 0;
// 각 빈의 남은 공간을 저장할 배열 생성
int bin_rem[m];
// 원소를 하나씩 배치
for (int i = 0; i < m; i++) {
// weight1[i]를 담을 수 있는 첫 번째 빈 탐색
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i]) {
bin_rem[j] = bin_rem[j] - weight1[i];
break;
}
}
// weight1[i]를 담을 수 있는 빈이 없는 경우
if (j == res) {
bin_rem[res] = C - weight1[i];
res++;
}
}
return res;
}
// First Fit Decreasing 오프라인 알고리즘으로 필요한 빈의 수를 반환
int firstFitDec(int weight1[], int m, int C){
// 먼저 모든 무게를 내림차순으로 정렬
sort(weight1, weight1 + m, std::greater<int>());
// 정렬된 항목에 대해 First Fit 호출
return firstFit(weight1, m, C);
}
// 드라이버 코드
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in First Fit "
<< "Decreasing : " << firstFitDec(weight1, m, C);
return 0;
}실행 결과
Number of bins required in First Fit Decreasing : 3
First Fit Decreasing은 원소를 미리 정렬하기 때문에 샘플 입력에서 가장 좋은 결과(3개의 빈)를 보여주었습니다. 이처럼 큰 원소를 먼저 배치하면 작은 원소들로 남은 공간을 효율적으로 채울 수 있습니다.
마찬가지로 First Fit Decreasing도 자가 균형 이진 탐색 트리를 활용하면 O(m log m) 시간에 수행 가능합니다.
정리: 알고리즘별 비교
Next Fit: O(n) 시간, O(1) 공간 — 가장 빠르지만 성능은 낮음 (약 2배 이내 보장)
First Fit: O(n²) → O(n log n) — 순차 검색 방식
Best Fit: O(n²) → O(n log n) — 남는 공간 최소화 전략
First Fit Decreasing: 사전 정렬 + First Fit — 일반적으로 가장 우수한 근사 결과 제공 (11/9 OPT + 6/9 보장)