- 개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다.
- 정확하지 않은 부분은 피드백 주시면 감사합니다.
2022-11-23
동적계획법; 행렬 곱셈 순서 문제 해결하기
참고: https://www.youtube.com/watch?v=8Ni1gaP35i8
https://www.acmicpc.net/problem/11049
위키백과 | 행렬곱셈
무엇?
-
행렬 곱셈 원리
- 첫째 행렬의 열 개수와 둘째 행렬의 행 개수가 같아야 함.
- 따라서 교환 법칙은 성립하지 않고, 결합법칙, 분배법칙은 성립
-
행렬 곱셈 비용
위와 같은 m * n 행렬 A와 n * p 행렬 B를 곱하면 다음과 같은 m * p 행렬 C가 생긴다
각 성분은 n번 곱해지고 n번 더해지므로 2n번의 연산이 필요하고,
m * p개의 성분이 있으므로
총 발생하는 연산 횟수는 m * p * 2n번 → O(m·p·n)
왜?
다이나믹 프로그래밍 연습 & 이해하기 😭
어떻게?
-
백준 11049번; 행렬 곱셈 연산 횟수 최소가 되는 곱셈 순서를 찾기
- 문제 정의 및 해 분석
- 다음과 같은 n개의 행렬; M1 * M2 * M3 * … * Mn = M
- 곱셈할 행렬 괄호를 어떻게 칠 것인가의 문제 ⇒ 임의의 n개에 대해서는 경우의 수가 매우 많다
- 최후의 곱셈은 임의의 k를 가정했을 때, 아래와 같을 것
(M1 … * Mk) * (Mk+1 … * Mn) - 우리가 구하고자 하는 것은 최소화한 저 곱셈 비용의 값이므로, 왼쪽 행렬의 곱셈도 미리 최소 비용으로 구해졌어야 하고, 오른쪽 행렬의 곱셈도 미리 최소 비용으로 구해져있어야 함
- 그리고 마지막 저 두 행렬의 곱셈 비용까지 더하면 그것이 최종적인 최소 곱셈 비용 (이 비용은 위에서 구한 m×p×n 값을 말하며, 입력 값으로 주어지기에 쉽게 구할 수 있음!)
- 하위 문제로 분할 & 재귀 관계식 정의하기
- 우리는 저 임의의 i를 모르기 때문에, DP로 다 구한다!
- 위의 분석에 따라 점화식을 정의하면 다음과 같음;
비용(M1 … * Mn) = 비용(M1 … * Mk) + 비용(Mk+1 … * Mn) + P1·Pk+1·Pn+1 - 이를 이차원 DP 테이블 상으로 표현하면 다음과 같음.
DP[i][j] = min(DP[i][k] + DP[k+1][j] + P[i] * P[k+1] * P[j+1])
최소값은 k를 i부터 j-1까지 증가시키며 구한 값들 중의 최소값.
- DP table을 채워나갈 때 주의할 점!
- 우리가 구하고자 하는 칸은 1부터 n까지의 행렬 곱셈의 최소 비용이니까, i가 1이고 j가 n인
DP[i][j]
- 행렬의 곱셈 순서가 바뀔 수 없으므로 i는 j보다 같거나 작어야 함
- i와 j가 같은 경우는 곱셈이 발생하지 않았으므로 0이다 → 베이스 조건!
- 우리가 구하고자 하는 칸은 1부터 n까지의 행렬 곱셈의 최소 비용이니까, i가 1이고 j가 n인
- 문제 정의 및 해 분석
-
나의 코드 + 주석
# https://www.acmicpc.net/problem/11049
import sys
# 입력받기; M = [0, P1, P2, P3 ... ]
N = int(sys.stdin.readline())
M = [0]
for i in range(N):
r, c = map(int, sys.stdin.readline().split())
if i == 0:
M.extend([r, c])
else:
M.extend([c])
# print(M)
# 이차원 DP 테이블
DP = [[0] * (N+1) for _ in range(N+1)]
# DP 테이블에서 '↘' 이런 대각선 방향으로 채워나가야 하기 때문에 인덱스 인터벌을 만듦
itvl = 1
for _ in range(N-1):
for i in range(1, N):
j = i + itvl
if j < N+1: # 인덱스 에러 안 나게 j의 인덱스 제한
min = 2**31
# DP[i][j]는 k를 i부터 j-1까지 증가시키면서
# DP[i][k] + DP[k+1][j] + M[i]*M[K+1]*M[j+1](두 행렬의 곱셈 비용)의 최소값이다
for k in range(i, j):
temp = DP[i][k] + DP[k+1][j] + (M[i]*M[k+1]*M[j+1])
if temp < min:
min = temp
DP[i][j] = min
itvl += 1
print(DP[1][N])
그리디 방법 소개 + 강의실 배정 문제
참고: https://www.youtube.com/watch?v=2nv7pQO4LTU&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=33
https://www.youtube.com/watch?v=7noZLdfHIMQ&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=34
무엇?
- 그리디 알고리즘이란
→ 알고리즘 노트에 정리해서 추가함 - 백준 1931번 회의실 배정 문제
왜?
어떻게?
- 끝나는 시간이 가장 빠른 순으로 뽑으면 됨!
'크래프톤정글 > TIL & WIL' 카테고리의 다른 글
크래프톤정글 5주차; TIL 2 - Red-Black Tree의 insert, delete 연산, C typedef, enum 활용, 메모리에서 스택과 힙의 자라나는 방향 (0) | 2022.12.03 |
---|---|
크래프톤정글 5주차; TIL 1 - C 프로그래밍, 함수 호출 방식, C언어 extern, static 변수 (0) | 2022.12.03 |
크래프톤정글 4주차; TIL 3 - 컴퓨터 구조와 운영체제의 큰 그림 (0) | 2022.11.28 |
크래프톤정글 4주차; TIL 2 - DP 동전 문제, LCS, 파이썬에서 2차원 배열 주의사항, 배낭 문제 (1) | 2022.11.28 |
크래프톤정글 4주차; TIL 1 - DP, 피보나치 수 문제, 플로이드 알고리즘 (0) | 2022.11.28 |