DP 와 Greedy

 

@ DP (Dynamic programming) 동적계획법

최적 부분 구조 + 중복 부분 문제 가 있을 때 DP 로 풀 수 있고,

두 가지 방법이 있다. 1. 메모이제이션 (재귀) 2. Tabulation (반복문구조)

- 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드 발생 문제가 있음. 

- 성능 면에서 DP 는 메모이제이션을 재귀적 구조로 사용하는 것보다 반복적 구조iterative로 작성하는게 효율적

@ Greedy Algorithm

최적 부분 구조 + 탐욕 선택 속성 이 있을 때 그리디는 최적의 솔루션이 보장

 

 

# 부분 문제의 최적의 솔루션을 이용해서 

# 기존 문제의 최적의 솔루션을 구할 수 있으면 (전체)

# 그, 문제에는 최적 부분 구조가 있습니다.

 

@ Divide and Conquer and Combine 분할 정복

부분으로 나누어, 부분 문제를 정복하여, 이로인해 기본 문제를 해결한다.

 

@ Recursive 재귀

부분문제 정복 => base case , 기본문제 해결=> recursive case 

 

 

 

안녕 - 오늘 티스토리 작성글 자꾸 날아가는 중