크래프톤정글/TIL & WIL

크래프톤정글 4주차; TIL 4 - DP 행렬 곱셈 문제, 탐욕법 강의실 배정

jamie-lee 2022. 11. 28. 00:19
  • 개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다.
  • 정확하지 않은 부분은 피드백 주시면 감사합니다.

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이다 → 베이스 조건!
  • 나의 코드 + 주석

# 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번 회의실 배정 문제

왜?

어떻게?

  • 끝나는 시간이 가장 빠른 순으로 뽑으면 됨!