Persistence

동적 프로그래밍 동적 프로그래밍은 제한 조건이 있을 때에 무언가를 최적화하는 경우 유용하다. 예를 들어 들어갈 수 있는 크기가 제한된 배낭에서, 값어치가 최대가 되도록 물건을 채우는 ''배낭 채우기'' 문제 같은 것이 그것이다. 동적 프로그래밍은 하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있다. 예를 들어 배낭에 넣을 물건 - 책, 거울, 노트북 등 - 의 가치는 다른 물건들과 관계가 없다. 모든 동적 프로그래밍 답안에는 격자가 있다. 격자의 각 칸에는 최적화하고자 하는 값을 적는다. 배낭 채우기 문제의 경우 물건의 가치를 적는다. cell[i][j]의 최대값은 // i는 행, j는 열 1. 지금까지 구한 cell[i-1][j]의 값 중에서 가장 최대값이거나 2. 현..