archive
9. 동적 프로그래밍 본문
1. 어떤 문제를 동적 프로그래밍으로 풀이하는가?
-동적 프로그래밍 : 큰 문제의 해답에 작은 문제의 해답이 포함되어있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이다.
- 피보나치 수열이 가장 대표적인 예시
-피보나치 수열을 재귀로 표현하면 다음과 같다
fib(n):
if(n=1 or n=2): return 1
else return fib(n-1)+fib(n-2)
-위와 같은 재귀적 알고리즘은 간명하지만 때때로 엄청난 비효율을 초래할 수 있으며, n의 피보나치 수를 구하는 앞의 재귀적 알고리즘은 지수 함수에 비례하는 시간이 들게 된다.
-이것은 호출 결과를 한 번만 구해 저장해두었다가 나중에 사용만 하면 될 것을, 매번 호출함으로써 비효율이 발생하는 것
-즉, f(3)을 처음 호출하고 결과를 얻었다면, 이것을 어딘가에 저장해 두고, 나중에 fib(3)이 필요하면 저장한 것을 사용하면 된다는 뜻이며, 이런식으로 부분 결과를 저장하면서 해를 구해나가는 것이 동적 프로그래밍의 핵심이다.
-정리하면, 다음 두 가지 성질이 있는 문제에 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거하는 것을 동적 프로그래밍이라 한다.
(i) 최적 부분 구조를 이룬다
(ii) 재귀적으로 구현했을 중복 호출로 심각한 비효율이 발생한다.
-중복된 재귀홒출을 피하는 이러한 방법을 메모하기(memoization)이라고 하며, 이것을 탑다운 방식으로 동적 프로그래밍으로 하향식 방법이다.
2. 행렬 경로 문제
-양수로 이루어진 nxn 행렬이 주어지고, 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다.
-이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합니다.
-오른쪽이나 아래쪽으로만 이동이 가능하며, 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.
-행렬의 왼쪽 위 원소 (1,1) 에서 원소 (i,j)까지 도달하는 경로들의 점수 중 최고점을 구하는 문제
-원소 (i,j)에 도달하기 직전에 방문할 수 있는 원소는 (i-1, j), (i, j-1) 중 하나인 단 두 개이다.
-원소 (i, j)에는 방문하므로 원소 (i, j)의 값은 반드시 더해져야 한다. 위의 두 경우의 수 중 둘 중 점수가 높은 것을 택하면 그것이 최고 점수가 되는 방식이다.
-이 설명을 다르게 말하면, 문제 (i, j)의 최적해 문제는 (i-1, j)의 최적해 문제와 (i, j-1)의 최적해 문제로 설명된다.
-즉, 자신의 부분 문제에 대한 최적해를 자신의 최적해를 구성하는데 사용한다.
-최적 부분 구조를 가지고 있다.
-이는 재귀적 구현 시 엄청난 중복 호출을 초래하며, 따라서 이 문제는 동적 프로그래밍에 아주 좋은 대상임을 알 수 있다.
-n*n 행렬에 대해 이 문제에 존재하는 부분 문제들의 총수는 고작 n^2가지이다.
- 동적 프로그래밍 시에, 알고리즘의 총 수행 시간은 O(n^2)이다.
3. 돌 놓기 문제
- 3*n 테이블의 각 칸에 숫자가 쓰여있다.
-테이블의 각 칸 중 일부에 제한 조건을 만족하는 방법으로 돌을 놓아 놓인 곳에 있는 수의 합을 최대로 하는 문제이다.
-돌을 놓는 제한 조건은 다음과 같다 : 가로나 세로로 인접한 두 칸에 동시에 돌이 놓일 수는 없으며, 각 열에는 적어도 하나 이상의 돌이 놓인다.
-임의의 열을 채울 수 있는 패턴은 단 네 가지 뿐이다.
-패턴 1의 이웃에는 패턴 2와 3만, 패턴 2의 이웃에는 패턴 1, 3, 4만, 패턴 3의 이웃에는 패턴 1, 2, 패턴 4의 이웃에는 패턴 2만 올 수 있으며 이는 양립 가능하다.
-돌을 놓는 모든 경우의 수를 따져본 다음 가장 높은 점수를 구할 수 있으나, 이는 지수 함수적인 시간이 걸린다.
4. 행렬 곱셈 순서 문제
- 곱셈의 결합법칙을 결정하는 문제, 어떤 순서로 어떤 방식으로 묶어서 수행하든 n개의 행렬 곱셈에 대해서는 총 n-1 번의 곱셈을 수행하게 된다.
4.2. 행렬 곱셈의 조건
행렬 곱셈의 조건은 행렬 A와 B를 곱할 때 A의 열의 개수와 B의 행의 개수가 같아야 한다는 것이다.
* 앞으로 한 행렬의 사이즈를 nxn으로 표현하겠다.
- 2x3 * 3x5 => 가능
- 2x3 * 2x3 => 불가능
이는 행렬 곱셈의 방식을 생각해보면 금방 이해할 수 있는 조건이다.
(= 이 조건을 충족하지 않는다면 곱셈을 할 수 없다는 것을 금방 이해할 수 있다.)
참고로 axb 크기의 행렬과 bxc 크기의 행렬을 곱하면 axc 크기의 행렬이 된다. ⭐️
이 또한 행렬 곱셈의 방식을 생각해보면 자명한 사실이다.
4.3. 행렬 곱셈의 성질
- 행렬 곱셈의 교환법칙은 성립하지 않는다. AB !== BA
=> 위의 행렬 곱셈의 조건과 같은 맥락이다. - 행렬 곱셈의 결합법칙은 성립한다. A(BC) = (AB)C
=> 곱셈 결과 행렬의 크기가 정해지는 규칙을 생각해보면 된다. 어떤 두 행렬을 먼저 곱하든 결국 제일 첫번째 행렬의 행의 개수가 결과 행렬의 행이 되고 마지막 행렬의 열의 개수가 결과 행렬의 열의 개수가 될 것이다.
여러 개의 행렬을 곱할 때, 곱셈 순서에 따라 달라지는 곱셈 연산의 개수의 최솟값이다.
이것을 조금 풀어서 써보면 아래와 같다.
- 여러 개의 행렬을 곱할 것이고,
- 그들을 다양한 순서로 곱할 수 있으며,
- 그에 따라 곱셈 연산의 개수가 달라지는데,
- 결론: 그 여러 곱셈 연산의 개수 중 최솟값이 무엇인가?
2.1. 곱셈 순서
일단, 여러 행렬을 다양한 곱셈 순서로 곱할 수 있다는 것이 전제이다.
이것이 성립하는 이유는 위에서 설명했던 행렬 곱셈의 성질 중 결합법칙 때문이다.
예를 들자면 A(BC)와 (AB)C 중 어떤 것이 연산의 개수가 적어질 것인지 묻는 것이다.
이 순서의 따라 곱셈 연산의 개수가 달라진다.
이해를 돕기 위해 <다양한 곱셈 순서>에 대해 다르게 말하자면,
'행렬 곱셈 식에서 괄호를 어떻게 칠 것인가'가 될 수 있다.
위에서 든 예시처럼 ABC는 A(BC)와 (AB)C 두 가지 방법으로 괄호를 칠 수 있다.
이에 따라 곱셈 순서는 두 가지로 달라진다.
- (AB)C
1) A * B
2) A*B의 결과 * C- A(BC)
1) B * C
2) A * B*C의 결과
당연하지만 위 두 순서만 다른 곱셈의 결과는 같을 것이다.
2.2. 곱셈 연산
그렇다면 과연 문제에서는 곱셈 연산이란 정확히 어떤 연산을 말하는 것이며, 곱셈 연산의 개수가 어떤 식으로 달라질까?
2.2.1. 문제에서 말하는 <곱셈 연산>이란?
문제에서 곱셈 연산은 아래 행렬 곱셈에서 노란색 네모 하나 하나를 말한다.
여기서 곱셈 연산의 개수는 24개이다.
2.2.2. 곱셈 연산의 개수
곱셈 연산의 개수는 A 행렬과 B 행렬을 곱할 때 아래와 같다.
A의 행의 개수 * B의 열의 개수 * A의 열의 개수(=B의 행의 개수)
따라서 아래 행렬 곱셈의 경우 곱셈 연산의 개수는 2 * 2 * 3이 될 것이다.
왜일까?
- C의 한 원소의 값을 얻기 위해서는 일단 A의 열의 개수(=B의 행의 개수)만큼의 곱셈 연산을 해야한다.
이것을 C의 총 원소의 개수만큼 하게 될 것이다.
=> C의 총 원소의 개수 x A의 열의 개수(=B의 행의 개수) - C의 총 원소의 개수는 C의 행의 개수 x C의 열의 개수이다.
=> C의 행의 개수 x C의 열의 개수 x A의 열의 개수(=B의 행의 개수) - 위의 1.1.에 따르면 C의 행의 개수 x C의 열의 개수는 곧 A의 행의 개수 x B의 열의 개수이다.
=> A의 행의 개수 x B의 열의 개수 x A의 열의 개수(=B의 행의 개수)
이에 따라 결국, AB의 곱셈 연산 개수는 A의 행의 개수 x B의 열의 개수 x A의 열의 개수(=B의 행의 개수)이 되는 것이다.
2.2.3. 곱셈 연산 개수의 변화
이제 곱셈 연산의 개수가 곱셈 순서에 따라 달라지는지 예를 들어 보여주겠다.
아래 세 행렬이 있다고 하자.
A: 2x5
B: 5x3
C: 3x4
이들 행렬을 (AB)C, A(BC) 두 순서로 곱했을 때의 곱셈 연산 개수를 보겠다.
이렇게 결합법칙이 성립함에 따라 어떤 순서로도 곱할 수 있지만,
각기 다른 곱셈 과정에서 곱셈 연산 개수 공식인 A의 행의 개수 x B의 열의 개수 x A의 열의 개수(=B의 행의 개수)에 들어가는 각각의 숫자가 달라진다.
그래서 곱셈 순서에 따라 곱셈 연산의 개수가 달라지는 것이다.
앞에서 말했듯이 이 글에서 문제 풀이는 다루지 않겠지만 핵심 포인트를 얘기하자면 다음과 같다.
곱하는 행렬의 개수가 많아질수록 곱셈 연산의 개수의 경우의 수가 어마어마해질 것이다.
따라서 이 경우의 수를 DP를 이용해 저장(Memoization)을 하며 최솟값을 찾아내는 것이 이 문제의 해법이 되는 것이다!
참고 링크 [파이썬/Python] 동적 프로그래밍 - 행렬 곱셈 순서 계산하기 ( Brute-Force Algorithm ) (tistory.com)
5. 최장 공통 부분 순서 (LCS)
- 이거 모르겟음
'C \ C++ > 알고리즘 예습 스터디' 카테고리의 다른 글
| 11. 그리디 알고리즘 (2) (0) | 2024.02.04 |
|---|---|
| 11. 그리디 알고리즘 (1) (0) | 2024.02.01 |
| 4. 정렬 (3) - 힙, 기수 정렬 (0) | 2024.01.28 |
| 4. 정렬 (2) - 병합, 퀵 정렬 (0) | 2024.01.20 |
| 4. 정렬 (1) - 선택, 버블, 삽입 정렬 (0) | 2024.01.19 |
