오늘 풀어본 문제는 프로그래머스의 정수 삼각형이라는 문제이다.
문제 설명은 다음과 같다.
문제 설명
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
이 문제를 보고 풀이를 생각 해보니 동적계획법(Dynamic Programming)을 사용하여 풀 수 있겠다고 생각했다.
삼각형의 크기에 해당하는 배열을 복사해주고 현재 위치에서 위를 확인하여 더해주는 방법을 적용해보니 정답이 나왔다.
풀이 코드는 다음과 같다.
class Solution {
public static int solution(int[][] triangle) {
int answer = 0;
int[][] table = triangle.clone();
for (int i = 1; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
if ((j - 1 >= 0 && j - 1 < triangle[i - 1].length) && (j >= 0 && j < triangle[i - 1].length)) {
table[i][j] += table[i - 1][j] > table[i - 1][j - 1] ? table[i - 1][j] : table[i - 1][j - 1];
} else if (j - 1 >= 0 && j - 1 < triangle[i - 1].length) {
table[i][j] += table[i - 1][j - 1];
} else {
table[i][j] += table[i - 1][j];
}
}
}
for (int i = 0; i < table[table.length - 1].length; i++) {
if (table[table.length - 1][i] > answer) {
answer = table[table.length - 1][i];
}
}
return answer;
}
}우선 먼저 파라미터로 받은 삼각형을 테이블이라는 변수에 복사해주고 삼각형 배열의 두번째 줄 부터 원소의 갯수만큼 반복을 한다. 이유는 맨 위 꼭대기는 위에 더할 숫자가 없기 때문이다.
그리고 원소마다 자신의 바로 위나 위의 왼쪽에 있는 값중 더 큰 값을 현재 값이랑 더해서 저장한다.
이렇게 끝까지 반복하고 삼각형 테이블의 맨 밑에 남아있는 값중 가장 큰 값이 위에서 아래로 더한 값 중 가장 큰 값이 된다.
동적계획법(Dynamic Programming)
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
DP를 쓰는 이유
왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다.
하지만 DP를 사용하면 작은 문제에서 이미 계산을 한 것은 저장을 해놓기 때문에 다시 계산을 하지 않아도 되는 장점이 있다.
DP의 사용 조건
DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.
1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)
- Overlapping Subproblems(겹치는 부분 문제)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재 사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
- Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.
만약 A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
DP 사용하기
DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다. 그래서 DP를 적용할 수 있는 문제인지를 알아내는 것부터 코드를 짜는 과정이 난이도가 쉬운 것부터 어려운 것까지 다양하다.
일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.
- DP로 풀 수 있는 문제인지 확인한다.
- 문제의 변수 파악
- 변수 간 관계식 만들기
- 메모하기(memoization or tabulation)
- 기저 상태 파악하기
- 구현하기
- DP로 풀 수 있는 문제인지 확인
애초에 이 문제부터 해결이 매우 어렵다. 우선 DP의 조건부분에서 써내렸듯이, 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다.
즉, 위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크해보는 것이 좋다.
보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
- 문제의 변수 파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉, 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 한다.
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.
또한, 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용한다. 해당 문제를 몰라도 된다.
또, 유명한 Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용한다. 이와 같이 해당 문제에서 어떤 변수가 있는지를 파악해야 그에 따른 답을 구할 수 있다.
- 변수 간 관계식 만들기
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다.
그러한 식을 점화식이라고 부르며 그를 통해 우리는 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.
- 메모하기
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
- 기저 상태 파악하기
여기까지 진행했으면, 가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.
피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.
해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 이 경우, 피보나치 수열은 매우 간단했지만 문제에 따라 좀 복잡할 수 있다.
- 구현하기
개념과 DP를 사용하는 조건, DP 문제를 해결하는 과정도 익혔으니 실제로 어떻게 사용할 수 있는지를 알아보고자 한다. DP는 2가지 방식으로 구현할 수 있다.
- Bottom-Up(Tabulation 방식) - 반복문 사용
- Top-Down(Memoization) - 재귀 사용
구현 방법
1. Bottom-Up 방식
이름에서 보이듯이, 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-Up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.
사실 위에서 메모하기 부분에서 Memoization이라고 했는데 Bottom-Up일 때는 Tabulation이라고 부른다.
왜냐면 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling"이라고 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.
사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.
- Top-Down 방식
이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.피보나치의 예시처럼, f(n) = f(n - 2) + f(n - 1)의 과정에서 n이 점점 감소하며 함수를 내려가는 방식에서 보이듯, n = 5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.
이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.
기타 내용
두 가지 방법(Top-Down vs Bottom-Up) 중 더 나은 것이 있는지, 하나만 가능한 경우가 있는지?
두 방법 중 어느 것이 시간적으로 더 효율이 잇는지 묻는데 그 답은 알수 없다. 실제로 재귀는 내부 스택을 만들고 함수를 호출하는 과정이 더 있어보여서 반복이 더 빠를 것 같다고 느낄 수 있다.
하지만, Top-Down을 통해 문제를 풀어가는 경우에는 점화식에 따라 불필요한 계산을 오히려 Bottom-Up보다 덜하는 경우가 있기 때문에 궁극적으로는 알 수 없다.
그 외, Top-Down은 재귀를 통해 내려가니까 Stack이 쌓여 StackOverflow 같은 에러가 발생하지 않느냐라고 하는데, 우리가 해결해야 하는 수준의 문제에서는 그러한 경우는 거의 없다.
혹시나 발생했다면 점화식을 잘못 만들었을 가능성이 높으니 다시 한 번 시도해보자.
또한 2가지 방법 중 2가지를 모두 사용하지는 못하고 하나만 사용할 수 있는 경우가 있느냐는 질문에는 '있다'라고 할 수 있다.
하지만 그것은 DP에 익숙해지고 나서 경험적으로 많이 알아낼 수 있다.
Divide and Conquer(분할 정복)와 차이점은?
분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다.
예를 들어 병합 정렬을 생각해 보자.
병합 정렬을 수행 시에 작은 하위 문제로 쪼개지지만 중복하여 하위 문제가 발생하지 않는다. 무슨 말이냐면, 분할된 부분은 모두 독립적이고, 동일한 부분을 중복하지 않는다는 것이다.
중복되는 경우는 어떤 것인가? 피보나치 수열을 생각해보자. 피보나치 수열은 fn = fn-1 + fn-2라는 수식을 갖는다.
즉, n이 어떤 수가 되던, n - 1번째 수와 n - 2번째 수를 더해야 한다.
즉, n = 5일 때, n - 1은 4이고, n - 2는 3인데, 3을 구하기 위해선 n - 2가 1인 경우까지 하위 문제로 내려가야 한다. 즉, n이 어떤 수이든 그 하위 수를 구하는 부분은 중복해서 나타난다.
그래서 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결이 가능한 것이다.
