Divide and Conquer로 문제를 잘게 쪼갠후 정복하면서 이 값들을 다시 조합한다.
동적프로그래밍은 계산결과를 저장(Memoization)했다가 재활용하는 기법임. 흔히 그리디와 비교되는데 그리디는 로컬 최적해를 구하는 것만 알 뿐 글로벌 최적해를 구할 지는 모른다.
다이나믹 : 부분 문제끼리 서로 관련성이 있어 재활용이 가능할 때
그리디 : 앞의 선택이 이후의 선택에 영향을 주지 않고 + 문제의 최적 해결 방법이 부분 문제에 대해서도 최적일 때 (Optimal Substructure). Optimal Substructure는 다이나믹도 해당됨.
분할 정복 : 부분 문제를 잘개 쪼개서 다시 조합하는 기법인데 기본적으로 부분 문제들끼리 독립적일 때 사용함(재활용이 안됨)
문자열을 연산하는 함수
eval("1+5") #6
itertools 빌트인 모듈에서 사용하는 함수로 배열의 값들을 순열로 표현한다;.