한빛 알고리즘 chapter8 동적프로그래밍 행렬경로문제
봄싹 텔레파시 스터디에서 스터디한 내용으로 작성해봤습니다~~
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;
}
}
}
'최적화_통계_알고리즘 > 알고리즘' 카테고리의 다른 글
문제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 |