문제 기술 2) 다음과 같은 형태의 일방통행 도로망에서 호텔에서 공항까지 가는 버스를 운행하고 있다. 호텔에서 공항까지 가는 도로망의 구조는 다음과 같다. 위쪽 도로에 n개 교차로 u1, u2, …, un이 있고, 아래쪽 도로에 n개 교차로 l1, l2, …, ln이 있다. u0(=l0)는 호텔을 나타내고, un+1(=ln+1)은 공항을 나타낸다. 그리고 i
문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 4 6 5 3 5 7 5 1 1 3 2 5 4 8 가장 아래 행의 셀로부터 오른쪽 위쪽 대각선 방향 혹은 위쪽 방향 혹은 왼쪽 위쪽 대각선 방향으로만 가면서 가장 위의 행의 셀까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 ..
문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 9 6 5 3 6 7 5 2 1 3 2 5 4 8 (1, 1) 셀 (1, 1)에서 오른쪽 방향 혹은 위쪽 방향으로만 가면서 셀 (m, n)까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고, 이 배..