-
한빛 알고리즘 chapter8 동적프로그래밍 행렬경로문제최적화_통계_알고리즘/알고리즘 2012.07.16 00:39
봄싹 텔레파시 스터디에서 스터디한 내용으로 작성해봤습니다~~
Top Down, Bottom Up 2가지 방식을 모두 사용하는 형식의 인터페이스를 했더니 약간
인터페이스부분이 깔끔하지 않네요...ㅠㅠ
-----------------------------------------------------------------------------------------------------------
public interface MatrixPath {
/**
*
* @param dataA 데이터용 2차원 배열
* @param resultA 결과저장용 2차원 배열
* @param row 결과요청 row
* @param col 결과요청 col
* @return 최종 결과값
*/
public int matrixPath(int[][] dataA, int[][] resultA, int row, int col);
}
-----------------------------------------------------------------------------------------------------------
//[Top down 방식:재귀형식]
public class DonghunMatrixPath implements MatrixPath {
@Override
public int matrixPath(int[][] dataA, int[][] resultA, int i, int j) {
int result = 0;
if(i==0 && j == 0){
result = dataA[i][j];
}else if(i==0){
result = dataA[i][j] + matrixPath(dataA, resultA, 0, j-1);
}else if(j==0){
result = dataA[i][j] + matrixPath(dataA, resultA, i-1, 0);
}else{
result = dataA[i][j] + max(matrixPath(dataA, resultA, i-1, j), matrixPath(dataA, resultA, i, j-1));
}
resultA[i][j] = result;
return result;
}
private int max(int a, int b){
if(a>b){
return a;
}else{
return b;
}
}
}
-----------------------------------------------------------------------------------------------------------
//[Bottom up 방식:재귀]
public class DonghunMatrixPathBottomUp implements MatrixPath{
@Override
public int matrixPath(int[][] dataA, int[][] resultA, int row, int col) {
int result = 0;
for(int i=0; i <= row; i++ ){
for(int j=0; j <= col; j++){
if(i==0 && j==0){
result = dataA[0][0];
}else if(i==0){
result = dataA[0][j] + resultA[0][j-1];
}else if(j==0){
result = dataA[i][0] + resultA[i-1][0];
}else{
result = dataA[i][j] + max(resultA[i-1][j], resultA[i][j-1]);
}
resultA[i][j] = result;
}
}
return result;
}
private int max(int a, int b){
if(a>b){
return a;
}else{
return b;
}
}
}
------------------------------------------------------------------------------------------------------------------//Test codepublic class DonghunMatrixPathTest {//입력데이터static int[][] dataA = {{ 6, 7, 12, 5},{ 5, 3, 11, 18},{ 7,17, 3, 3},{ 8,10, 14, 9}};@Testpublic void testMatrixPath(){int[][] resultA = new int[4][4];MatrixPath path = new DonghunMatrixPath();int result = path.matrixPath(dataA, resultA, 3, 3);System.out.println("[result Array:TopDown(Recursive)]");print(resultA);Assert.assertEquals(68, result);}@Testpublic void testMatrixPathBottomUp(){int[][] resultA = new int[4][4];MatrixPath path = new DonghunMatrixPathBottomUp();int result = path.matrixPath(dataA, resultA, 3, 3);System.out.println("[result Array:BottomUp]");print(resultA);Assert.assertEquals(68, result);}private void print(int[][] data){for(int i=0; i < data.length; i++){for(int j=0; j < data[0].length; j++){System.out.print(data[i][j] + " ");}System.out.print("\n");}}}'최적화_통계_알고리즘 > 알고리즘' 카테고리의 다른 글
문제2번 지뢰찾기 (0) 2012.07.25 한빛 알고리즘 chapter8 동적프로그래밍 조약돌놓기 문제 (0) 2012.07.16 한빛 알고리즘 chapter8 동적프로그래밍 행렬경로문제 (0) 2012.07.16 Algorithm 관련 사이트 (0) 2012.07.08 2차원배열 오른쪽방향으로 돌면서 채우기 (Groovy) (0) 2012.06.30 Programming Challenge 1 (Groovy) (0) 2012.06.29 댓글 0