오늘 배운 것들

1. 퀴즈 정리

1-1. 스택과 레지스터

스택(stack)은 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간
후입선출(Last In First Out)구조

• 용도:
  함수의 로컬 변수 저장: 호출된 각 함수의 로컬 변수들이 스택에 저장
  함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반환 주소(return address)와 이전 함수의 스택 프레임 정보를 스택에 저장
• 장점:
  동적으로 메모리를 할당하고 해제
  구현이 간단하며, 메모리 관리overhead가 낮습니다.
• 키워드
  지역 변수, 제어 흐름 관리(후입선출), 반환 주소, 오버헤드

레지스터(register)는 프로세서 내부의 고속 작동 메모리
프로시저 실행 중 자주 접근하는 변수나 중간 계산 값을 저장

• 용도:
  중간 연산 결과의 저장
  빠른 데이터 접근
• 장점:
  매우 높은 데이터 접근속도를 제공합니다.
  데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가합니다.
• 키워드
  속도, 자주 접근하는 변수, 중간 계산 값

1-2. 꼬리 재귀 최적화(Tail Recursion Optimization)

꼬리 재귀 최적화는 재귀함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거합니다.
이를 통해 함수가 반환될 때 호출 스택을 재사용 할 수 있습니다.
구체적으로, 꼬리 재귀 함수는 반환 값을 바로 return 하기 보다는 파라미터로 전달합니다.
이렇게 하면 호출 스택에 쌓이지 않고 후속 호출로 이동됩니다.
마지막 호출에서 스택 프레임을 재활용하므로, 메모리 사용량이 일정하게 유지됩니다.

• 키워드
  오버플로우, 스택 프레임 재활용

1-3. 그리디 알고리즘과 동적 프로그래밍

1. 그리디 알고리즘(Greedy Algorithm)
   • 정의: 매 순간마다 가장 좋아 보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대합니다.
   • 특징: 각 단계에서의 최적의 해답을 찾아나가면서 전체 문제의 최적 해답을 찾아 나가는 방식입니다. 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않습니다.
   • 키워드
     지역 최적화가 곧 전역 최적화, 이후의 상황 미고려
2. 동적 프로그래밍(Dynamic Programming)
   • 정의: 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘입니다.
   • 특징: 중복된 하위문제들을 여러 번 해결하는 것을 방지하여 효율성을 높입니다. 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation)기법을사용합니다.
   • 하위유형:
     상향식(Bottom-Up): 작은 문제부터 차례대로 해결해나가면서 큰 문제의 해결책을 구합니다.
     하향식(Top-Down): 큰 문제를 작은 문제로 나누어 해결합니다. 필요할 때 하위 문제를 해결합니다.
   • 키워드
     문제 나누기, 중복 계산 제거, 최적 부분 구조, 중복 부분 문제

2. 동적 프로그래밍(DP)

2-1. 행렬 곱셈 순서(백준 11049)

행렬들의 크기가 주어졌을 때 행렬들을 모두 곱하는데 필요한 곱셈 연산 수의 최솟값 $M$을 구하는 문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다.

언제나 최적 부분 구조를 찾는 것이 가장 중요하다.

2-1-1. 조건 확인

아래와 같은 크기의 행렬 네 개가 주어진 경우를 가정
1×2, 2×3, 3×4, 4×5
그렇다면 필요한 행렬곱의 횟수는 3번이다.
행렬곱의 순서에 따라 가능한 모든 경우의 수와 곱셈 연산 수를 나열하면 다음과 같다.

연산의 위치 표시: 1×2 ① 2×3 ② 3×4 ③ 4×5

1. ①②③, 1×2×3 + 1×3×4 + 1×4×5
2. ①③②, 1×2×3 + 3×4×5 + 1×3×5
3. ②①③, 2×3×4 + 1×2×4 + 1×4×5
4. ②③①, 2×3×4 + 2×4×5 + 1×2×5
5. ③①②, 3×4×5 + 1×2×3 + 1×3×5
6. ③②①, 3×4×5 + 2×3×5 + 1×2×5

앞선 순서와 관계없이 마지막 연산이 같으면(1과3, 2와5, 4와 6) 마지막에 더해지는 연산 수 역시 같음을 확인할 수 있다.
이는 두 행렬을 곱할 때 행렬이 어떤 순서로 곱해졌는지와 무관하게 두 행렬의 크기에 의해서만 곱셈 연산의 수가 결정되기 때문이다.
이를 이용하여 아래와 같이 일반화할 수 있다.

1. 최적 부분 구조
   $I = ((e_0, e_1), (e_1, e_2), ... , (e_{n-1}, e_{n}))$일 때 $I_{i, j}=((e_{i-1}, e_i), ..., (e_{j-1}, e_j))(i≤j)$라고 하고
   주어진 수열$I$에 대한 최소 곱셈 연산 수를 $M_I$라고 할 때
   $M_I = min_{k=1}^{n-1} (M_{I_{1, k}} + M_{I_{k+1, n}} + e_0×e_k×e_n)$
2. 중복 부분 문제
   계속하여 수열을 이분하며 수열의 길이가 1이될 때까지 전개하면 계산이 중복된다.

2-1-2. 코드

import sys
input = sys.stdin.readline
INF = 2**31

def main() -> None:
    N = int(input())
    A = [tuple(map(int, input().split())) for _ in range(N)]
    c = [[INF if i != j else 0 for j in range(N)] for i in range(N)]
    
    for i in range(2, N+1): # 길이
        for j in range(0, N-i+1): # 위치
            for k in range(1, i):
			    s, m, e = j, j+k-1, j+i-1
                if c[s][e] > (m:=c[s][m] + c[m+1][e] + A[j][0]*A[m][1]*A[e][1]):
                    c[s][e] = m
                    
    print(c[0][N-1])

if __name__ == "__main__":
    main()

수열의 길이가 1일 때부터 상향식으로 계산을 구현하였다.