재귀적 해법은 중복 호출 문제가 발생할 수 있다
-e.g. 피보나치
→동적 프로그래밍을 하면 해결할 수 있다.
동적 프로그래밍의 적용 요건
①최적 부분 구조
-큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다
②재귀호출시 중복
-재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복된다.
1) 행렬 경로 문제
-양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다
-이동 방법 (제약조건)
① 오른쪽이나 아래쪽으로만 이동할 수 있다
② 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다
-목표
:행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대가 되도록 한다
2) 돌 놓기
-3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다
-조약돌을 놓는 방법 (제약조건)
① 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다
② 각 열에는 적어도 하나 이상의 조약돌을 놓는다
-목표
: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌
'알고리즘' 카테고리의 다른 글
| 쉽게 배우는 알고리즘-03연습문제 (0) | 2023.10.23 |
|---|---|
| 쉽게 배우는 알고리즘-02 연습문제 (2) | 2023.10.23 |
| 쉽게 배우는 알고리즘-08집합의 처리 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-06검색트 (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-05선택 알고리즘 (0) | 2023.10.23 |