개발하는데 다 이유가 있겠지

스택과 레지스터

스택(stack)

• 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간
• 선언되는 순서와 반대로 메모리가 해제되는 LIFO(LastInFirstOut)구조용도

1. 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장
2. 함수의 제어흐름 관리 : 함수가 다른 함수를 호출할 때, 반환주소와 이전함수의 스택프레임 정보가 스택에 저장장점
3. 동적으로 메모리를 할당하고 해제할 수 있음
4. 구현이 간단하며, 메모리 관리 overhead가 낮음

레지스터(register)

프로세서 내부의 고속작동 메모리로, 프로시저 실행 중. 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용

용도

1. 중간 연산결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용
2. 빠른 데이터 접근 : 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용장점
3. 매우 높은 데이터 접근속도를 제공
4. 데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가

---

꼬리 재귀 최적화(Tail Recursion Optimization)

• 재귀 함수 호출 시 호출 스택의 사용을 최적화하는 기법
• 재귀 함수가 호출될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 됨
• 재귀 함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거
• 이를 통해 함수가 반환될 때 호출 스택을 재사용할 수 있음
• 반환값을 바로 return하기 보다는 파라미터로 전달 -> 호출 스택에 쌓이지 않고 후속 호출로 이동
• 마지막 호출에서 스택 프레임을 재활용하므로, 메모리 사용량이 일정하게 유지

---

그리디 알고리즘과 동적 프로그래밍

그리디 알고리즘(Greedy Algorithm, 탐욕법)

정의

매 순간마다 가장 좋아보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대함

특징

• 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식
• 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않음

동적 프로그래밍(Dynamic Programming, DP)

정의

복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘

특징

• 중복된 하위 문제들을 여러 번 해결하는 것을 방지해 효율성을 높임
• 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 기법을 사용

유형

상향식(Bottom-Up) : 작은 문제부터 차례대로 해결해 나가면서 큰 문제의 해결책을 구함

하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결 / 필요할 때 하위 문제를 해결