정글사관학교 30일차 TIL: 코치님의 조언, 행렬 곱셈 순서(#11049)

1. 코치님 조언

1. 혹시 아직도 뭐가 뭔지 모르겠다?

내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해보기. 이 과정의 가장 근본적인 목표는 (코테 통과가 아니라) 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다.

일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다.

 

미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될 지 모르기 때문에 정형화된 문제들로 연습하는 것이고 이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해 계산 복잡도를 고려하고, 문제 유형을 나누어 익히고, 정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다.

 

2. 이제까지 배운 것들 사이 상관관계

눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword들은 서로 연관이 있습니다.

• 분할 정복은 재귀함수로 구현하기 좋습니다.
• 이분 탐색은 분할 정복의 한 가지 방법입니다.
• 재귀 함수를 반복문(loop)으로 바꿀 때 스택을 사용하면 쉽게 바꿀 수 있습니다. (문제에 따라서는 스택을 안 쓰고도 바꿀 수 있습니다.)
• DFS는 재귀로 구현하면 매우 쉽게 구현할 수 있고 반복문으로 구현하려면 스택을 사용하면 됩니다.
• BFS를 구현할 때 큐(queue)를 사용하며, 큐를 priority queue로 바꾸면 Dijkstra 알고리즘이 됩니다.(!!!)
• DP(Dynamic programming)도 분할 정복을 구현하는 방법들 중 한 가지이며, 따라서 재귀함수로 구현하기 좋습니다. (솔직히 점화식이 보이는데 이걸 깨닫지 못한다면...)
• DP 문제를 단순 재귀 함수로 구현하면 같은 함수가 여러 번 불리는 경우가 있으므로 한 번 계산한 함수는 그 결과값을 저장하는 기법을 사용하는데 그 기법을 memoization이라고 합니다.
• 1주차의 완전 탐색 문제를 3주차에 다시 보면 문제의 graph를 탐색하는 방법으로 생각이 가능하다는 걸 깨달을 수 있습니다.

각각의 풀이 방법을 외우려고 하지 않고 이런 연관성을 가지고 보면, 컴퓨터로 풀 수 있는 문제의 모양을 보는데 도움이 되리라고 생각합니다.

3. DP에 대해서 좀 더 이야기하자면

• k차원 array를 만들고 array를 채워나가는 DP의 풀이 방식, 소위 bottom-up 방식의 풀이는 가끔 이해하기 어려운 경우가 있습니다. 사실 bottom-up 방식은 재귀를 이용한 top-down 방식을 (stack 없이) 반복문으로 만든 겁니다. 이렇게 만들어 놓고 보면 상당량의 최적화, 특히 공간 최적화를 더 할 수 있는 경우가 많기 때문에 이 방식의 풀이를 좋아하는 분들이 계신데..일단은 이해가 중요합니다. 이해할 수 있는 풀이를 먼저 찾는 것을 권장합니다.
• Python은 cache decorator를 제공하여 top-down DP 구현을 쉽게 만듭니다. (function argument == array index)
• "점화식을 알면 DP를 쉽게 짤 수 있는데 점화식을 어떻게 만들지 모르겠다"고 하는 분들이 계실 텐데, 맞습니다. 점화식을 만드는 자체가 문제를 푸는 것이고, 좀 더 정확하게는 문제를 어떻게 잘 자를 수 있는가를 찾는 과정입니다. 사실 1주차 재귀, 2주차 분할정복에서부터 필요했던 능력입니다.

가끔 보면 문제를 딱 보고 어떻게 자르면 되는지 알아차리기를 원하는 분이 계시는데, 그 정도의 능력은 저는 재능의 영역으로 봅니다. 솔직히 이게 되면 못 풀 문제 없죠. 특정 사람들만 알아듣는 말로 "직사의 마안"을 가졌다고 표현합니다.

 

그렇다고, 노력해도 기를 수 없는 능력이냐 하면... 뭐, 하다 보면 늘기는 합니다.(오늘의 핵심 문장!)

 

 

2. 행렬 곱셈 순서(#11049)

이어서 바로 문제 풀이. 오늘은 DP 문제를 다시 보고 있는데, 그 중에서도 가장 골 아프게 했던 행렬 곱셈 순서(#11049)를 다시 풀어본다.

 

주어진 행렬곱을 수행할 때, 곱셈 횟수의 최솟값을 구하는 문제이다. 예를 들어 주어진 행렬이 아래와 같다고 해보자.

• A = 5 X 2
• B = 2 X 3
• C = 3 X 4
• D = 4 X 2
• E = 2 X 5

이때, ABCDE의 행렬곱에 대해 곱셈 횟수 최솟값은 다음 중 하나에 있을 것이다. 그리고 각각의 괄호 안에 있는 행렬곱에 대해 재귀적으로 경우의 수를 나눠서 살펴볼 수 있다.

• A(BCDE)
  • A X B(CDE)
  • A X (BC)(DE)
  • A X (BCD)(E)
• (AB)(CDE)
  • ...
• (ABC)(DE)
  • ...
• (ABCD)(E)
  • ...

이렇게 끝까지 쪼개서 맨 끝에 나오는 경우의 수를 모두 구한 뒤, 거꾸로 채워가면서 최솟값을 구하는 방식이다. 이를 DP 테이블에 배열해보자. 테이블에서 행을 시작하는 행렬, 열을 끝에 나오는 행렬이라고 해보자. 위의 ABCDE는 아래와 같이 나타낼 수 있다. (원래는 인덱스 0이 들어가는데 아래에서는 생략)

예컨대 우리가 구하고 싶은 게 ABCD의 최소 곱셈 횟수라고 해보자. ABCD는 A(BCD), (AB)(CD), (ABC)(D) 중에서 최솟값일텐데 이는 위의 가(A 하나)+나(BD: 실제로는 BCD인데 C는 곱셈 횟수에 필요 X) / 다(AB)+마(CD) / 라(AC)+바(D) 중 최솟값일테다. 이를 점화식으로 나타내면 아래와 같다.

 

DP[r][c] = min(k는 r부터 c까지)(DP[r][k] + DP[k+1][c] + rows[r] * cols[k] * cols[c])

 

 여기서 rows, cols는 위의 A,B,C,D,E에서 각각 행, 열의 값을 저장해둔 리스트이다. 인덱스는 각 행렬의 순서를 반영해서 저장된다.

 

             A   B  C  D  E

rows = [5, 2, 3, 4, 2]

cols = [2, 3, 4, 2, 5]

 

이제 마지막. 점화식만 나오면 그 뒤는 간단(?)하다더라.. 위의 DP 테이블을 왼쪽 위에서 오른쪽 아래로 대각선을 그었을 때, 아래쪽은 필요 없는 영역이니 배제하고 위쪽 삼각형에서 대각선 방향으로 삼중 for문을 돌며 DP 테이블 값을 갱신해나간다.

 

이제 코드를 보면 아하 싶을 것이다. (처음에 바로 코드 보면 뭔 말인지 1도 모름..)

 

from sys import stdin

input = stdin.readline

N = int(input())
matrix = []
dp = [[0] * (N) for _ in range(N)]

for i in range(N):
    matrix.append(list(map(int, input().split())))

for i in range(1, N): # 몇 번째 대각선?
    for j in range(0, N-i): # 대각선에서 몇 번째 열?
        if i == 1:
            dp[j][j+i] = matrix[j][0] * matrix[j][1] * matrix[j+i][1]
            continue
        
        dp[j][j+i] = 2**32 #(최댓값으로 배치)
        for k in range(j, j+i):
            dp[j][j+i] = min(dp[j][j+i], 
                             dp[j][k] + dp[k+1][j+i] + matrix[j][0] * matrix[k][1] * matrix[j+i][1])

print(dp[0][N-1])