.png&blockId=3197e115-ee0d-4d9c-9f5d-4b57cb28634e)
알고리즘 설명
DP란?
복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 메모이제이션(Memoizatoin) 기법을 사용하여 해결함으로써 불필요한 연산과 탐색이 줄어들어 시간복잡도 측면에서 많은 이점을 가지는 방법 메모이제이션 (Memoization) 기법이란? 구현 방식 (2가지)오늘의 알고리즘 문제
정수 삼각형
접근 방법
그림 설명 소스코드
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
int[][] dp = new int[triangle.length][triangle.length];
// for(int i=0; i<dp.length; i++) {
// Arrays.fill(dp[i], 0);
// }
dp[0][0] = triangle[0][0]; // 초기값
for(int i=1; i<triangle.length; i++) {
dp[i][0] = dp[i-1][0] + triangle[i][0];
for(int j=1; j<i+1; j++) {
dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
}
// 마지막 라인에서 max값 찾기
int answer = 0;
for(int i=0; i<dp[dp.length-1].length; i++) {
answer = Math.max(answer, dp[dp.length-1][i]);
}
return answer;
}
}
Java
복사
등굣길
접근 방법
갈 수 있는 길의 수를 메모할 수 있는 memo 배열 선언 memo배열에 물에 잠긴 지역 표시 2중 for문을 사용하여 memo배열 탐색 memo배열의 값이 -1이면 continue (물에 잠겼으므로 진행 ) 윗쪽과 왼쪽이 0이상이라면 더하기 더하는 과정에서 값이 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 더하기 마지막 최단경로 개수를 1,000,000,007로 나눈 나머지 return
소스코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int[][] memo = new int[n+1][m+1]; // 갈 수 있는 길의 수 메모
for (int i = 0; i < puddles.length; i++) {
memo[puddles[i][1]][puddles[i][0]] = -1;
}
memo[1][1] = 1;
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < m+1; j++) {
if(memo[i][j] == -1) {
// System.out.println(memo[i][j] + "입니다");
continue;
}
if(memo[i][j-1] >= 0 && memo[i][j] >= 0) { // 이전(왼쪽)에 숫자가 0이상이면 더하기
memo[i][j] = memo[i][j] + memo[i][j-1] % 1000000007;
}
if(memo[i-1][j] >= 0 && memo[i][j] >= 0) { // 이전(위쪽)에 숫자가 0이상이면 더하기
memo[i][j] = memo[i][j] + memo[i-1][j] % 1000000007;
}
}
}
answer = memo[n][m] % 1000000007;
return answer;
}
}
Java
복사
실행 결과