• 계산 모델(Computation Model)
  • 최적화 모델(Optimization Model)
  • 탐욕 알고리즘(Greedy algorithm)
  • 파이썬 람다(lambda)


Chapter 1. Introduction and Optimization Problems 강의를 듣고 정리한 내용입니다.


계산 모델(Computation Model)

  • 이제까지 일어났던 무언가를 이해하거나 매일 보는 현상들을 설명하는 모델
  • 아직 일어나지않은 미래를 예측할 수 있게 해주는 모델
    • 예) 날씨 변화 모델 : 천 년동안 날씨가 어떻게 변했는지에 대해 모델과 미래에 어떻게 될지 예측하는 모델을 만들 수 있음


최적화 모델(Optimization Model)

  • 제한 조건을 가지며 목적 함수를 최대화 또는 최소화 하는 모델
  • 목적함수 : 최대화 또는 최소화 해야하는 것, 제한조건들은 몇몇 해를 제거하는 것
  • 냅색(=옛날 배낭)문제
    • 목적함수 : 매매할때 값이 최대한 많이 나가도록 하는 것
    • 제한조건 : 냅색안에 들어갈 수 있는 양
    • 도둑이 가장 값비싼 물건을 훔쳐야하는 최적화 문제
    • 연속 냅색 문제
      • 일부분만 가져갈 수 있는 문제(금괴가 아닌 금모래로 가져갈 수 있는 경우)
      • 탐욕 알고리즘으로도 풀 수 있고, 풀기 쉬운 편
    • 0/1 냅색 문제
      • 금괴를 가져가거나 아예 못 가져가는 경우
      • 한번 결정하면 그 결정이 다음 결정에 영향을 미침


최적화 문제를 푸는 방법

  • 무차별 대입 알고리즘
    • 모든 경우의 수를 고려해 승자를 선택
    • 그러나 실용적이지 않음
  • 탐욕 알고리즘(Greedy algorithm)
    • 여러가지 경우 중 하나를 결정할 때 그 순간 best라고 생각되는 것을 선택해나가는 방식
    • 가장좋은것의 의미는 정의에 따라 달라짐 → 가장 좋은것을 정의하기 위해 keyFunction을 사용
    • 탐욕 알고리즘은 좋은 해를 구할수는 있어도 최적 해를 구할수는 없음
class Food(object):
    def __init__(self, n, v, w):
        self.name = n
        self.value = v
        self.calories = w

    def getValue(self):
        return self.value

    def getCost(self):
        return self.calories
   
    def density(self):
        return self.getValue()/self.getCost()

    def __str__(self):
        return self.name + ':<' + str(self.value)\
                + ',' + str(self.calories) +
 '>'

-- 가장 좋은것의 의미를 어떻게 정의했는지 알려주는 함수
def greedy(items, maxCost, keyFunction):
    itemsCopy = sorted(items, key = keyFunction,
											 reverse = True)
    result = []
    totalValue, totalCost = 0.0, 0.0
   
    for i in range(len(itemsCopy)):
        if (totalCost + itemCopy[i].getCost()) <= maxCost:
            result.append(itemsCopy[i])
            totalCost += itemsCopy[i].getCost()
            totalValue += itemsCopy[i].getValue()
  
    return (result, totalValue)
  • 복사해서 사용하는 것은 좋은 습관
  • 시간소요
    • 모든 물건을 정렬 → 시간복잡도 : n log n (n은 물건의 개수)
    • for loop : n번
    • 최종 시간복잡도 : O(n log n) → 매우 효율적 !


파이썬 람다(lambda)

  • 익명의 함수를 만들 때 사용
  • (lambda 식별자 배열 : 원하는 식)
  • 이 파라미터들로 표현된 식을 계산하고 결과를 반환하는 함수를 만듦
  • def를 쓰는 대신에 인라인 함수로 정의
  • apply 나 map을 쓸 때 주로 사용.


다음강의 : Chapter 2. Optimization Problems