완전탐색, 동적계획법, 탐욕법

1. 완전탐색, BFS, DFS

   : 모든 선택지 탐색하는 방법.

     하나의 문제를 작은 sub 문제로 쪼개서 재귀로 풀 수 있는 경우 多

 

2. 동적계획법

   : 완전 탐색처럼 해결하나,

    중복되는 sub 문제를 한번만 계산되도록 memoization을 활용하는 문제

 

3. 탐욕법

   : 한 문제를 작은 문제로 쪼개서 재귀로 푸는 것은 완전탐색, 동적계획법과 동일하나,

    각 단계마다 당장 가장 좋은 방법만 선택

    ① 여러 부분 문제로 나누기

    ② 어떤 우선 순위로 선택할지 결정 (손으로 몇 개 풀면서)

    ③ 답이 항상 최적해인지, 각 단계에서 최적해가 전체 최적해를 만드는지 생각