동적계획법
St1tch
동적계획법문제를 여러 조각들로 나누고, 이 때 여러 번 계산되는 문제들을 메모리에 저장해서 속도를 올리는 개념보통 경우의수, 확률, 이항계수 등에 사용한다.Ø 재귀 호출: 문제를 여러 조각으로 쪼개 재귀적으로 해결하는 방법Ø 완전 탐색: 재귀 호출을 이용해 최적화 문제 풀기Ø 메모이제이션: 시간과 공간 트레이드오프로 동적 계획법 알고리즘 만들기Ø 경우의 수 세기와 확률 문제 DP 로 풀기 ★동적계획법 과정① 모든 답을 만들어서 제일 좋은 답을 찾는 완전 탐색 알고리즘을 설계합니다.② 부분 문제 정의에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다.③ 이를 위해 입력을 조작하거나 형태를 바꿔야 할 수도 있습니다.④ 재귀 호출은 이전의 선택과는 관련 없이 앞으로 남은 선택에 관련된 답만..