[TIL][Krafton Jungle] 3주차 - (6) : DP : 행렬 체인 / 프로시저 CS

오늘은 컴퓨터 시스템과 관련된 CS 정리를 퀴즈 문제와 같이 정리하겠다.

 

그전에 DP의 행렬 체인 알고리즘을 공부하고 해당 문제를 푸는 과정을 정리하겠다.

---

DP : 행렬 체인 알고리즘

행렬 체인의 연산은 몇번째의 행렬을 먼저 계산하는가에 따라 연산의 횟수가 달라진다.

따라서 주어진 행렬의 체인을 최소로 연산하는 횟수를 구하는 알고리즘을 공부해보자.

 

`Introduction to Algorithm` 책에 해당 로직에 대한 설명이 나와있다.

 

매우 이해하기 힘들지만, 간단히 정리해 보겠다.

 

행렬을 쭉 나열하고 그 행렬의 열이 체인형태로 (NxM , MxP) 나열되어 있어서 곱을 순서대로 할 수 있다.

 

Ai = pi-1 x pi 의 차원을 가진다.

(이부분이 어려울 수 있는데, A의 i번째가 3x6 매트릭스라면 p의 i-1번째는 3, p의 i번째 수는 6이다)

 

이때, i번째 행렬에서 j번째 행렬 사이에 k번째 행렬을 Ak 라고 하고,

m[i][j]는 매트릭스 열의 i번째 매트릭스와 j번째 매트릭스 사이의 연산의 횟수라고 하면,

 

(Ai ~ Ak 의 연산횟수의 합) + (Ak+1 ~ Aj의 연산횟수의 합) + pi-1*pk*pj  = m[i][j] 이라고 할 수 있다.

 

책의 공식

 

이때 i와 j의 특정 k를 어떤 값으로 선택하냐에 따라서 연산횟수는 달라지기 때문에

i와 j사이의 각 k에서 연산된 m[i][j]의 값을 서로 비교하고, 최소값으로 갱신해 나가면서 i와 j번째의 거리를 늘린다.

 

최종적으로 우리가 원하는 m[1][n]까지 i와 j 사이의 범위를 늘려 값을 검사하고, 최종 최소값을 출력해야 한다.

 

따라서 이 알고리즘은 L (=j-i) , i , k 를 3중 반복문으로 탐색하여 O(n^3)의 시간복잡도를 가진다.

(이때 j는 L을 통하여 값을 선언할 수 있다.)

 

이 알고리즘의 방법을 이용하는 문제를 풀고 코드를 리뷰해보자.

 

BaekJun - #11049 : 행렬 곱셈 순서 (DP)

 

출처 : https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

문제의 알고리즘을 참고한 책의 의사코드를 먼저 보고, 코드를 작성했다.

책의 행렬 체인 곱 알고리즘 의사 코드

해당 문제는 위의 알고리즘 공부를 하면서 배운 문제상황과 똑같기 때문에 바로 코드를 보자.

 

import sys

n = int(sys.stdin.readline())
INF = float('inf')

matrix_p = []
for i in range(n):
    a,b = map(int,sys.stdin.readline().strip().split())
    if not matrix_p:
        matrix_p.append(a)
    matrix_p.append(b)

cal_count = [[0 for _ in range(n+1)] for _ in range(n+1)]

for l in range(2,n+1):
    for i in range(1,n-l+2):
        j = i+l-1
        cal_count[i][j] = INF
        for k in range(i,j):
            cal_count[i][j] = min(cal_count[i][j] , cal_count[i][k] + cal_count[k+1][j] + (matrix_p[i-1]*matrix_p[k]*matrix_p[j]))

print(cal_count[1][n])

 

cal_count[i][j] 은 위에서 말했던 m의 배열과 일치하는데 이는 i부터 j번째 매트릭스 사이에 연산되는 연산횟수를 말한다.

(k는 특정 매트릭스를 상징하는 것이 아닌, 매트릭스를 나누는 경계의 수라고 생각해야 하는 것에 주의해야 한다.)

 

matrix_p 배열에는 각 매트릭스 체인의 차원들이 들어있는데

예를들어 입력으로 매트릭스 3개가 (3x6 , 6x2, 2x4) 이렇게 들어왔다면,

matrix_p = [3,6,2,4] 가 된다.

 

마지막 for문안에 k로 나눈 연산횟수의 최소값을 갱신(위의 공식에 min함수를 사용한 모습)하는 코드를 삽입함으로써 문제를 해결하고 있다.

 

연산을 이해하기 위해 for문의 처음부터 거슬러 가보면,

처음 체인의 길이가 2일때는 cal_count[i][k] + cal_count[k+1][j] 가 모두 0이어서 연산에 포함되지 않는다.

체인이 2라는 것은 우리가 알고 있는 단순 2개의 매트릭스를 곱하는 것이기 때문에

뒤에 있는 matrix_p 배열안의 값으로 단순 차원 곱연산만 한다.

 

이후 체인의 범위를 점점 늘려가서 저장되어 있던 사이 값을 이용하여 최소값을 또 다시 갱신한다는 매커니즘을 잘 따라가보면 해당 코드가 어떤 방식으로 문제에 접근하는지 이해할 수 있다.

 

책을 활용해서 문제를 풀어보았는데, DP는 역시 문제별로 생각하는 접근 방식이 다 다른것 같다.

 

해당 문제의 변환된 버전을 접하게 되었을 때, 스스로 이 방식을 활용하여 풀기 위해서

이 문제를 어떻게 접근했고, 해결해 나갔는지 기억해야 할 것 같다.

 

---

컴퓨터 시스템 CS 정리

프로시저

프로시저는 C언어의 함수와 같다.

 

P 프로시저에서 Q 프로시저를 호출할때는

스택 공간을 할당(%rsp의 값을 줄이는(sub) 방식으로 그 사이 공간을 할당한다.)하고,

call 인스트럭션을 통해 해당 인스트럭션으로 이동하는 방식으로 제어권을 전달한다.

 

이때 인자의 1번째~6번째는 argument Reg를 통해서 참조할 수 있도록 저장해두는 방식으로 전달을 하고,

그 이후인 7번째부터는 call하기 전의 caller가 본인의 스택 프레임에 인자들을 저장한다.

 

그러면 callee들은 callee Reg에다가 argument Reg의 값들을 옮겨다 사용하고,

7번째 이후부터의 인자들은 자신의 스택 프레임 공간인 `Argument build area`에 caller 프레임에 있는 인자들의 값을 주소 간접 참조를 통해 옮겨다가 저장한다.

 

이 스택 프레임 구조는 1장에서 살펴봤던 가상 메모리의 런타임 스택에 해당한다.

 

특정 caller가 call 인스트럭션으로 callee를 호출할때는 call 인스트럭션 다음의 인스트럭션 주소를 return address에 할당한다.

(이때 address가 push되어 %rsp값을 -8로 갱신해야 하지만, call 인스트럭션이 자동으로 수행해준다.)

 

 가장 헤깔렸던 부분은, caller에서 사용하던 레지스터 안의 값들이, callee가 해당 레지스터를 사용하여 기존의 값을 훼손되는 일이 없도록 따로 기존 데이터를 보존하는 작업을 caller쪽에서 하는건지 callee쪽에서 하는건지였다.

 

결과적으로 말하면, callee는 call되어 연산을 수행하기 전에,

어디에서 사용하던 데이터인지 모르는 Register 속의 데이터를 본인 프레임에 저장해둔다.

 

그 후 해당 레지스터를 사용하고, 본인의 모든 수행이 끝나면

return 되기 전에 프레임에 보존해뒀던 데이터를 원래 레지스터로 다시 넣어 두며 해당 값을 보존한다.

 

 

또한 callee 내에서 지역 변수를 저장해두고 연산을 수행하는 일이 있을 수 있다.

 

이때는, 본인의 스택 프레임 영역의 TOP부분에 공간을 할당한 뒤 그 곳에 데이터들을 저장하고,

해당 값을 사용할 때는 %rsp의 값으로부터 간접 참조를 하여 데이터를 가져온다.

 

 

---

3주차 퀴즈 리뷰 

 

2. 꼬리 재귀 최적화(Tail Recursion Optimization)을 호출 스택(Call stack)의 관점에서 설명하시오.

 

꼬리 재귀 최적화는 재귀 함수 호출 시 호출 스택의 사용을 최적화하는 기법이다.

 

재귀 함수가 호출될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 된다고 한다.

 

꼬리 재귀의 아이디어는, 인자에 재귀하며 갱신되는 값(최종 return 값)을 전달하면서,

따로 자시 자신을 재귀하는 return 말고 다른 연산이 필요없게 만들어

함수가 종료될때, 프레임을 종료시키며 새 프레임을 할당하기에 caller의 프레임 영역을 callee가 재사용한다.

따라서 스택은 쌓이지 않고 계속 다시쓰는 방식으로 재사용 된다.

 

이때, 핵심은 'return 함수(인자1,인자2)' 처럼 함수의 마지막에 다른 연산 없이 함수 자신만 호출하는 경우여야 한다. 

 

꼬리 재귀 최적화를 적용한 팩토리얼 함수 코드는 다음과 같다.

# 일반적인 재귀 함수
def factorial_recursive(n):
    if n == 0:
        return 1
    else:
        return n * factorial_recursive(n - 1)

# 꼬리 재귀 최적화를 적용한 함수
def factorial_tail_recursive(n, acc=1):
    if n == 0:
        return acc
    else:
        return factorial_tail_recursive(n - 1, n * acc)

# 일반적인 재귀 함수 호출
result1 = factorial_recursive(5)  # 120

# 꼬리 재귀 최적화를 적용한 함수 호출
result2 = factorial_tail_recursive(5)  # 120

 

꼬리 재귀 최적화된 factorial_tail_recursive() 함수는 원하는 값을 인자로 전달함으로서,

연산을 인자 내부에서 수행하고, return에 자기 자신을 호출하기만 하며 마무리된다.

 

---