[퀴즈 오답노트] 스택과 레지스터, 꼬리 재귀 최적화, memorization, tabulation, 이행적 폐쇄

스택과 레지스터

스택과 레지스터 모두 지역저장장치 역할을 한다

 

스택

프로시저 호출을 처리하는데 중요한 역할

1. 함수의 로컬 변수 저장

2. 함수의 제어 흐름 관리

 

장점

동적으로 메모리를 할당하고 해제할 수 있다. -> malloc, calloc

구현이 간단하며(stack), 메모리 관리 오버헤드가 낮다

 

레지스터

중간 연산 결과의 저장에 활용

---

꼬리 재귀 최적화

return에 재귀함수를 쓴다고 다 꼬리 재귀 최적화가 아니다

# 꼬리 재귀 최적화 구현
return factorial(n-1, n*acc)

이렇게 return에도 아무것도 남기지 않아야 한다.

# 틀린 예시
return n*factorial(n-1)

기억해야 할 지역변수가 있으면 함수를 종료시키지 못하고 스택에 변수를 저장해놓게 된다.

---

Memorization vs Tabulation

쉽게 설명하면 Memorization -> 탑 다운, Tabulation -> 바텀 업 이다.

Memorization은 캐시에 기억되고,

Tabulation은 리스트를 통해 메모리에 기억된다는 차이가 있다.

 

Memoization vs Tabulation in DP

---

이행적 폐쇄 Transitive Closure

임의의 두 정점간에 경로가 존재하는지의 여부 → 최종적으로 갈 수 있는가를 파악하는 것

그리고 이행적 폐쇄 행렬은 갈 수 있는지 없는지 여부를 나타내는 행렬이다

 

플로이드 워셜로 파악해서 Transitive Closure Matrix를 만들 수 있다