코틀린 코딩테스트 강좌, 행렬 곱 연산 횟수의 최솟값 구하기

코딩테스트에서 자주 등장하는 행렬 관련 문제는 다양한 변형이 존재하며, 그중에서도 행렬의 곱셈에 관련된 문제는 많은 수험생들이 어려워하는 주제입니다. 이 글에서는 ‘행렬 곱 연산 횟수의 최솟값 구하기’ 문제를 살펴보고, 이를 해결하기 위한 알고리즘과 코드를 자세히 설명하겠습니다.

문제 설명

행렬 A의 크기가 A_rows x A_cols, 행렬 B의 크기가 B_rows x B_cols일 때, 두 행렬의 곱셈을 수행하기 위해서는 A의 열의 개수 A_cols와 B의 행의 개수 B_rows가 일치해야 합니다. 이 연산의 복잡도는 A_rows x A_cols x B_cols로 계산됩니다.

여러 개의 행렬을 곱할 때 연산 효율을 높이기 위해서는 ‘행렬 곱셈의 순서’를 적절히 선택하는 것이 중요합니다. 우리는 주어진 행렬 리스트에 대해, 모든 가능한 곱셈 순서에 대해 연산 횟수를 계산하고, 그 중 최솟값을 찾아야 합니다.

입력 형식

첫 줄에 자연수 N (1 ≤ N ≤ 30)이 주어집니다. 다음 N줄에는 각 행렬의 크기를 나타내는 두 정수 R과 C가 주어집니다. 여기서 R은 행의 수, C는 열의 수를 의미합니다. 각 행렬의 곱셈을 위해서는 R×C형태로 주어진다고 가정합니다.

출력 형식

최소 행렬 곱 연산 횟수를 한 줄에 출력합니다.

예제 입력

예제 출력

풀이 과정

이 문제를 해결하기 위해 사용하는 알고리즘은 ‘행렬 곱셈 순서 결정 동적 프로그래밍(Dynamic Programming) 방법’입니다. 이 방법을 사용하면 각 행렬 조합의 곱셈 연산 비용을 효율적으로 계산할 수 있습니다.

동적 프로그래밍 접근

주어진 문제에서 행렬의 곱셈 순서를 결정하기 위해, 다음과 같은 단계로 진행합니다:

입력된 행렬 크기를 바탕으로 DP 테이블을 만듭니다.
곱셈 비율을 재귀적으로 계산하여 최소 값으로 갱신합니다.
최종적으로 DP 테이블의 최종값을 출력합니다.

DP 배열 및 초기화

우선, 2차원 배열 dp를 선언하고 모든 값을 0으로 초기화합니다. 이 배열은 dp[i][j]가 행렬 i부터 j까지의 최소 곱셈 비용을 저장하는 역할을 합니다.

연산 횟수 계산 로직

행렬의 곱셈 연산 횟수를 계산하기 위해 다음과 같은 방식으로 DP를 진행합니다:

i부터 j까지의 모든 가능한 구간을 순회합니다.
현재 구간의 중간 점 k를 선택합니다 (i ≤ k < j).
현재 DP 값과 중간 점을 기준으로 두 부분을 나누어 각각의 비용을 계산한 후 합산합니다.
최소값을 갱신합니다.

코드 구현

아래는 위 과정을 코틀린으로 구현한 코드입니다:

    fun matrixChainOrder(dims: IntArray): Int {
        val n = dims.size - 1
        val dp = Array(n) { IntArray(n) }

        for (chainLength in 2..n) {
            for (i in 0..n - chainLength) {
                val j = i + chainLength - 1
                dp[i][j] = Int.MAX_VALUE
                for (k in i until j) {
                    val cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                    dp[i][j] = minOf(dp[i][j], cost)
                }
            }
        }
        return dp[0][n - 1]
    }

    fun main() {
        val n = readLine()!!.toInt()
        val dims = IntArray(n + 1)
        for (i in 0 until n) {
            val (r, c) = readLine()!!.split(" ").map { it.toInt() }
            dims[i] = r
            if (i == n - 1) {
                dims[i + 1] = c
            } else {
                dims[i + 1] = c
            }
        }
        println(matrixChainOrder(dims))
    }

결론

이 문제를 통해 우리는 행렬 곱셈의 최적화 과정, 즉 최적의 곱셈 순서를 결정하는 방법을 익혔습니다. 동적 프로그래밍을 통해 사소한 부분부터 차례로 계산하여 전반적인 연산 횟수를 줄이는 것이 중요합니다. 코딩 테스트에서 이러한 문제에 충분히 대비하고, 반복적으로 연습하여 강점을 가지길 바랍니다. 다음 시간에는 더욱 깊이 있는 문제를 다뤄보겠습니다!