재귀적 해법은 중복 호출 문제가 발생할 수 있다 -e.g. 피보나치 →동적 프로그래밍을 하면 해결할 수 있다. 동적 프로그래밍의 적용 요건 ①최적 부분 구조 -큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다 ②재귀호출시 중복 -재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복된다. 1) 행렬 경로 문제 -양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다 -이동 방법 (제약조건) ① 오른쪽이나 아래쪽으로만 이동할 수 있다 ② 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 -목표 :행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대가 되도록 한다 2) 돌 놓기 -3×N 테이블의 각 칸에 양 또는 음의 정..
