[MIT] Data Science - 2. Optimization Problems

Introduction to Computational Thinking and Data Science
(6.0002, Fall 2016)

Introduction to Computational Thinking and Data Science

MIT 공대의 "Introduction to Computational Thinking and Data Science"(6.0002, Fall 2016) 강의 정리 자료

MIT6_0002F16_lec2.pdf

1.25MB

 

 

핵심 키워드

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

 

학습 내용

탐욕 알고리즘(Greedy Algorithm)

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

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

• 탐욕 알고리즘을 대체할 수 있는 알고리즘
• 항목의 조합 가능한 수를 열거한 후, 전체 합이 가중치를 넘어가는 것은 제거

동적 프로그래밍(Dynamic Programming)

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

 

 

 

 

 

 

 

실습 코드

MIT_Reference_code.zip