|
|
| (같은 사용자의 중간 판 하나는 보이지 않습니다) |
| 1번째 줄: |
1번째 줄: |
| '''빈 패킹 알고리즘'''(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
| |
| * 아이템: [8, 2, 4, 7, 3]
| |
| | |
| === First Fit ===
| |
| | |
| * 8 → 첫 번째 빈에 배치. [8]
| |
| * 2 → 첫 번째 빈(8)을 확인, 공간이 남아있으므로 배치. [8,2]
| |
| * 4 → 첫 번째 빈(8+2=10)은 가득 참 → 새로운 빈 생성 [8,2] [4]
| |
| * 7 → 첫 번째 빈(8+2=10)은 가득 참 → 두 번째 빈(4)은 공간이 모자람. 새로운 빈 생성 [8,2] [4] [7]
| |
| * 3 → 첫 번째 빈(8+2=10)은 가득 참, 두 번째 빈(4)에 공간이 있음 [8,2] [4,3] [7]
| |
| | |
| === Best Fit ===
| |
| | |
| * 8 → 첫 번째 빈에 배치. [8]
| |
| * 2 → 첫 번째 빈(8)을 확인, 공간이 남아있으므로 배치. [8,2]
| |
| * 4 → 첫 번째 빈(8+2=10)은 가득 참 → 새로운 빈 생성 [8,2] [4]
| |
| * 7 → 첫 번째 빈(8+2=10)은 가득 참 → 두 번째 빈(4)은 공간이 모자람. 새로운 빈 생성 [8,2] [4] [7]
| |
| * 3 → 첫 번째 빈(8+2=10)은 가득 참, 두 번째 빈(4)에 공간이 있지만 세 번째 빈(7)에 넣는 것이 Best Fit이므로 [8,2] [4] [7,3]<ref>가장 빈 공간이 적도록 어떤 빈이든 최대한 꽉 채우는 선택을 하는 것이다.</ref>
| |
| | |
| === Worst Fit ===
| |
| | |
| * 8 → 첫 번째 빈에 배치. [8]
| |
| * 2 → 첫 번째 빈(8)을 확인, 공간이 남아있으므로 배치. [8,2]
| |
| * 4 → 첫 번째 빈(8+2=10)은 가득 참 → 새로운 빈 생성 [8,2] [4]
| |
| * 7 → 첫 번째 빈(8+2=10)은 가득 참 → 두 번째 빈(4)은 공간이 모자람. 새로운 빈 생성 [8,2] [4] [7]
| |
| * 3 → 첫 번째 빈(8+2=10)은 가득 참, 두 번째 빈(4)과 세 번째 빈(7)에 넣을 수 있지만, 두 번째가 Worst Fit이므로 [8,2] [4,3] [7]<ref>삽입을 하고도 공간이 가장 많이 남아있도록 하는 것이 목표이다.</ref>
| |
| | |
| ==코드 예제==
| |
| <syntaxhighlight lang="python">
| |
| 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)
| |
| </syntaxhighlight>
| |
| 출력 결과 예시:
| |
| [[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.
| |
| [[분류:알고리즘]]
| |
