• 탐욕 알고리즘(Greedy Algorithm)
  • 무차별 대입 알고리즘(Brute Force Algorithm)
  • 동적 프로그래밍(Dynamic Programming)


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


탐욕 알고리즘(Greedy Algorithm)

  • 결정할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종 답에 도달하는 방식
    • 장점 : 구현하기 쉬움, 매우 빠름 (m log n)
    • 단점
      • 최적일수도, 아닐수도 있는 해를 구함
      • 구한 해가 최적에 얼마나 가까운지 모름


무차별 대입 알고리즘(Brute Force Algorithm)

  • 탐욕 알고리즘을 대체할 수 있는 알고리즘
  • 항목의 조합 가능한 수를 열거한 후, 전체 합이 가중치를 넘어가는 것은 제거
    • 1) 물건의 모든 가능한 조합을 나열
    • 2) 총합이 허용된 무게를 초과하는 조합을 모두 제거
    • 3) 남은 조합 중 가장 큰 값을 가지는 조합을 아무거나 하나 택함


탐색트리 :(트리는 일종의 그래프)

  • 첫번째 원소는 고려해야하는 물건 중 선택
    • 냅색에 그 물건을 위한 공간이 있으면, 노드는 물건을 선택한 결과를 반영하여 만들어진다. (왼쪽 자식)
    • 선택하지 않는 결과도 탐색(오른쪽 자식)
    • 위 과정을 단말 노드가 아닌 자식에게 재귀적으로 적용된다.
    • 최종적으로 제한조건에서 가장 큰값을 가진 노드를 선택할 것
  • 트리의 노드수를 알면 알고리즘의 복잡도를 알 수 있음
  • 레벨의 개수는 항목의 개수 : n+1
  • 각 레벨당 노드는 항목이 갈수록 많아짐 → 레벨 i에서 노드의 개수는 2^i
  • n개의 항목이 있을 때 트리의 노드개수는 2^i 를 0부터 n까지 더한값이 된다.
    • 값이 2의 n 제곱 + 1 임을 알 수 있다.


-- toConsider : 트리의 상단 노드에 있는 물건 리스트
-- avail : 남는 여유 공간의 양
-- result : 지금까지 탐색한 것 중 최고의 답을 기록(이전값보다 더 좋은지)
def maxValue(toConsider, avail):
   if toConsider == [] or avail == 0:
       result = (0,())
   elif toConsider[0].getUnits() > avail: #true면 왼쪽가지를 볼 필요가 없음
       result = maxVal(toConsider[1:] #리스트 요소 중 최댓값
                      , avail)
   else: #양쪽 가지 다 고려해야함.
       nextItem = toConsider[0]
       withVal, withToTake = maxVal(toConsider[1:],
                                   avail - nextItem.getUnits())
       withVal += nextItem.getValue() #요소를 가졌을 때의 값
       withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
       
       if withVal > withoutVal:
					result = (withVal, withToTake + (nextItem,)) 
			 else:
					result = (withoutVal, withoutToTake) 
   return result



-- 메뉴 랜덤으로 만들기
import random

def buildLargeMenu(numItems, maxVal, maxCost):
		items = []
    for i in range(numItems):
				items.append(Food(str(i),
			  random.randint(1, maxVal),
				random.randint(1, maxCost)))
		return items

for numItems in (5,10,15,20,25,30,35,40,45,50,55,60):
items = buildLargeMenu(numItems, 90, 250)
testMaxVal(items, 750, False)


동적 프로그래밍(Dynamic Programming)

  • 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법


def fib(n):
		if n == 0 or n == 1:
				return 1
		else:
				return fib(n-1) + fib(n-2)

fib(120) = 8,670,007,398,507,948,658,051,921


  • 같은 값들을 계속해서 가져오는 문제
  • 값을 한번 저장하면 다시 계산할 필요가 없음


테이블을 만들어 지금까지 한 것을 기록한다,

  • fib(x)를 계산하기 전에, fib(x)가 페이블에 이미 저장되어있는지 확인
  • 있다면 값을 가져오고, 없다면 계산 후 테이블에 저장한다 ⇒ 메모이제이션


def fastFib(n, memo = {}):
		if n == 0 or n == 1:
				return 1 
		try:
				return memo[n] 
		except KeyError:
				result = fastFib(n-1, memo) +\ fastFib(n-2, memo)
				memo[n] = result 
				return result


어디서 쓸 수 있을까?

  • 최적 부분 구조 문제일 경우 풀 수 있는 방법
    • for x >1, fib(x) = fib(x-1) + fib(x-2)
  • 중복 부분 문제일 경우 풀 수 있는 방법
    • 최적 해를 구할 때 같은 문제를 여러번 풀어야 하는 문제
    • fib(x)를 1번 계산하거나 여러 번 계산하는 경우
  • 근사가 아닌 최적화 해법이 구해짐



[강의 1, 2 요약]

  • 실제로 중요한 문제들은 최적화된 문제로 바꿀 수 있다.
  • 탐욕알고리즘(Greedy Algorithm)은 적당한 정답을 준다 (최적화 해법이 아니긴 함)
    • 이론적으로 최적화 해법을 찾는다고해도 기하급수적인 경우가 많다.
  • 이때 동적프로그래밍을 쓰면 좋은 결과를 얻을 수 있다.
    • 항상 최적의 해를 주고 대부분 빠르게 주기도한다.


다음강의 : Chapter 3. Graph-theoretic Models