✏️ 11/29 강의 필기

8.3 통 채우기 문제

정의
: 모든 물건을 가장 적은 수의 통에 채워넣는 문제

통 채우기 그리디 방법

• 최초 적합 (First Fit)
  • 첫 번째 통부터 차례로 살펴보면서, 가장 먼저 여유가 있는 통에 넣는다.
• 다음 적합 (Next Fit)
  • 직전에 물건을 넣은 통부터 살펴보고, 여유가 있으면 넣는다.
• 최선 적합 (Best Fit)
  • 여유가 있는 통 중에 남는 부분이 가장 적은 통에 넣는다.
• 최악 적합 (Worst Fit)
  • 여유가 있는 통 중에 남는 부분이 가장 많은 통에 넣는다.

근사비율

• 최초 / 최선 / 최악 적합
  • 2OPT > OPT'
  • 근사 비율 : 2
• 다음 적합
  • 2OPT > OPT'
  • 근사 비율 : 2

pseudocode

• 입력 : n개 물건 각각의 크기
• 출력 : 사용된 통의 개수

Approx_BinPacking(){
	cnt = 0
    for i=1 to n {
    	if (물건 i를 넣을 여유가 있는 기존의 통이 있으면)
        	그리디 방법에 따라 정해진 통에 i를 넣는다.
        else
        	새 통에 물건 i를 넣는다.
            cnt = cnt + 1 
    }
    return cnt
}

시간복잡도

• 최초 / 최선 / 최악 조합
  • 새 물건을 넣을 때마다 기존의 통을 살펴보아야 함
  • O(n^2)
• 다음 적합
  • 직전에 사용된 통만 살펴보면 됨
  • O(n)

8.4 작업 스케줄링 문제

8.5 클러스터링 문제