- 문제를 해결하는 최적의 답(optimal solution)을 찾아야 하는 문제 - optimal solution은 하나 이사일 수 있다. - maximum 혹은 minimum value를 가지는 solution을 찾는 문제들이 주를 이룬다. ex) 가장 빨리 도착하는 경로의 소요 시간은? 또는 언제 주식을 사고 팔 때 가장 수익이 높은지? value : 소요시간, 수익 solution : 경로, 언제 주식을 사고 팔때
동적계획법 DP(Dynamic Programming)이란
- optimization problem을 해결하는 전략 중 하나 - subproblem(s)의 optimal solution(s)을 활용해서 problem의 optimal solution을 찾는 방식 - 계속 쪼개다보면 겹치는(overlapping) subproblems은 한번만 계산하고 그 결과를 저장한 뒤 재사용한다. 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘을 의미한다. 특정 범위까지의 최적해를 구하기 위하여 다른 범위까지의 최적해를 이용하여 효율적으로 해를 구하는 알고리즘 설계 기법 → 이전에 구한 값을 기반으로 규칙성을 파악하여 다음 값을 구하는 것 → 쉽게 말하면 하나의 큰 문제를 여러 개의 작은 문제로 나우어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
DP를 사용하는 이유
재귀함수와 방식이 유사하다.
재귀함수 : 단순히 사용할 때 작은 문제 하나에서 작은 문제가 있다면 계속 반복하여야 하기 때문에 규모가 큰 계산은 비효율적이다.
분할정복(Divide and Conquer) : 분할 정복은 문제를 분할했을 떄 겹치는 문제가 발생하지 않는다.
☞ 중복 계산을 피하면서 최적 부분 구조를 활용하여 문제를 해결하는 효율적인 알고리즘 설계 기법 중 하나이다.
DP의 두 가지 접근 방식
Top-Down approach
Bottom-Up approach
구조
recursive
iterative(for-loop)
subproblem 결과 저장
memoization (function call 결과를 저장해서 이후에 같은 input에 대한 호출은 저장한 결과값을 사용하는 것)
tabulation (작은 subproblem부터 시작해서 최종 problem 결과를 도출할 때까지 결과를 차례대로 기록하는 것)
언제 선호하는지
subproblems의 일부만 계산해도 최종 optimal solution을 구할 수 있을 때
모든 subproblems을 계산해야 최종 optimal solution을 구할 수 있을 때
Top-Down : 해결하기 위해서 좀더 작은 크기 문제로 해결해보자
Bottom-up : 일단 작은 것부터 해결해 나가자(빌드업) => 알고리즘 문제에서 많이 사용하는 편
DP를 사용한 알고리즘 설계 순서
주어진 문제의 optimal solution이 구조적으로 어떤 특징을 가지는지 분석한다.
재귀적인 형태로 optiomal solution의 value를 정의한다.
(주로) Bottom-up 방식으로 optimal solution의 value를 구한다.
지금까지 계산된 정보를 바탕으로 optimal solution을 구한다.
예제 1 정상까지 오르는데 n번의 스텝이 필요한 계단이 있다. 한 번에 한 스텝 혹은 두 스텝을 오를 수 있을 때, 계단의 정상까지 오르기 위해 몇 개의 유니크한 방법이 있는지 구하시오(단 n>=1)
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
접근 방법
7
→
7
3
8
10
15
8
1
0
18
16
15
2
7
4
4
20
25
20
19
4
5
2
6
5
24
30
27
26
24
삼각형으로 되어 있는 숫자를 2차원 배열 형태로 표현한다.
아래와 오른쪽 대각선 아래로 계산이 되기 때문에 계산을 하여 아래로 숫자를 계산하여 2번 계산이 필요한 중간 부분은 가장 계산에서 큰 숫자를 입력한다.
f(n)=f(n-1)+f(n-2)이므로 계속해서 계산할 때 메소드를 호출하지 않도록 dp[][] 2차원 배열을 만들어서 계산한 값을 저장해둔다.
마지막 열에최종 계산된 모든 수가 존재하는데 해당 숫자 중에서 가장 큰 숫자를 반환한다.
코드
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
int answer = 0;
for(int i=0; i<triangle.length-1; i++){
for(int j=0; j<triangle[i].length; j++){
dp[i+1][j] = Math.max(dp[i][j]+triangle[i+1][j],dp[i+1][j]);
dp[i+1][j+1] = Math.max(dp[i+1][j+1],triangle[i+1][j+1]+dp[i][j]);
}
}
answer = Arrays.stream(dp[dp.length-1]).max().getAsInt();
return answer;
}
}
