빈 패킹 알고리즘

빈 패킹 알고리즘(Bin Packing Algorithm)은 주어진 아이템들을 최소 개수의 용기(빈, Bin)에 효율적으로 배치하는 최적화 문제를 해결하는 알고리즘이다. 이 문제는 조합 최적화 문제 중 하나로, 물류, 메모리 관리, 작업 스케줄링 등에서 널리 사용된다.

문제 정의

빈 패킹 문제는 다음과 같이 정의할 수 있다.

• 각 아이템은 크기(weight)를 가지며, 모든 빈(bin)은 고정된 용량(capacity)을 가진다.
• 목표는 가능한 한 적은 빈을 사용하여 모든 아이템을 배치하는 것이다.

빈 패킹 문제는 NP-완전(NP-complete) 문제로 알려져 있으며, 최적해를 구하는 것은 계산적으로 어렵다. 따라서, 근사 알고리즘(heuristic algorithm)이 자주 사용된다.

빈 패킹 알고리즘의 종류

빈 패킹 알고리즘은 온라인 알고리즘과 오프라인 알고리즘으로 나뉜다.

온라인 알고리즘

아이템을 입력받는 즉시 배치해야 하며, 앞으로 들어올 아이템을 미리 알 수 없다.

• First Fit(FF) → 가장 먼저 사용 가능한 빈에 배치.
• Best Fit(BF) → 가장 적은 여유 공간이 남는 빈에 배치.
• Worst Fit(WF) → 가장 많은 여유 공간이 남는 빈에 배치.

오프라인 알고리즘

모든 아이템을 미리 알고 있으며, 정렬 후 배치할 수 있다.

• First Fit Decreasing (FFD) → 아이템을 내림차순 정렬한 후 FF 알고리즘 적용.
• Best Fit Decreasing (BFD) → 아이템을 내림차순 정렬한 후 BF 알고리즘 적용.

확장된 빈 패킹 알고리즘

빈 패킹 알고리즘은 다양한 응용 환경에서 변형되어 사용된다.

선형 빈 패킹 알고리즘 (Linear Bin Packing)

• 아이템의 크기가 연속적인 범위를 가질 때 사용.
• 각 빈의 크기도 동적으로 조정될 수 있음.
• 자원 분배 및 동적 메모리 할당 문제에서 유용함.

다차원 빈 패킹 알고리즘 (Multidimensional Bin Packing)

• 각 아이템이 단순한 크기뿐만 아니라 여러 차원의 속성(예: 길이, 너비, 높이)을 가질 때 사용.
• 3D 물류 시스템(박스 적재, 컨테이너 로딩)에서 활용됨.

음수를 포함한 빈 패킹 알고리즘 (Bin Packing with Negative Items)

• 일부 아이템이 용량을 차지하는 것이 아니라 용량을 회복시키는 경우.
• 예: 전력 분배 시스템에서 특정 장치는 전력을 소비하지만, 다른 장치는 전력을 생성할 수 있음.

동적 빈 패킹 알고리즘 (Dynamic Bin Packing)

• 아이템이 실시간으로 추가/삭제될 수 있는 환경에서 사용.
• 클라우드 컴퓨팅에서 가상 머신(VM) 할당, 네트워크 트래픽 분배 등에 활용됨.

예제

다음과 같은 아이템과 빈을 고려하자.

• 빈 용량: 10
• 아이템 크기: [2, 5, 4, 7, 1, 3, 8]

First Fit(FF) 알고리즘을 적용하면:

1. 첫 번째 빈: [2, 5, 1] (총합: 8)
2. 두 번째 빈: [4, 3] (총합: 7)
3. 세 번째 빈: [7] (총합: 7)
4. 네 번째 빈: [8] (총합: 8)

총 4개의 빈이 사용됨.

코드 예제

def first_fit(items, bin_capacity):
    bins = []
    
    for item in items:
        placed = False
        for bin in bins:
            if sum(bin) + item <= bin_capacity:
                bin.append(item)
                placed = True
                break
        if not placed:
            bins.append([item])

    return bins

# 예제 실행
items = [2, 5, 4, 7, 1, 3, 8]
bin_capacity = 10
bins = first_fit(items, bin_capacity)

print(bins)

출력 결과 예시:
[[2, 5, 1], [4, 3], [7], [8]]

시간 복잡도

각 알고리즘의 시간 복잡도는 다음과 같다.

• First Fit (FF) → O(N²) (최악의 경우)
• Best Fit (BF) → O(N log N) (정렬 포함)
• FFD / BFD → O(N log N) (정렬 후 배치)

응용

빈 패킹 알고리즘은 여러 분야에서 활용된다.

• 물류 및 창고 관리 → 상자를 트럭에 최적 배치.
• 메모리 관리 → RAM 할당 문제.
• 작업 스케줄링 → CPU 및 프로세스 배분.
• 네트워크 자원 할당 → 데이터 패킷을 서버에 효율적으로 분배.

같이 보기

• 그리디 알고리즘
• NP-완전 문제
• 배낭 문제

참고 문헌

• Garey, Michael R., and David S. Johnson. "Computers and Intractability: A Guide to the Theory of NP-Completeness." W. H. Freeman, 1979.
• Coffman, E. G., Garey, M. R., and Johnson, D. S. "Approximation algorithms for bin packing: A survey." Approximation algorithms for NP-hard problems, 1997.