대엉코딩

1. 힙 메모리를 사용하는 이유?

- 위의 그림에서 보듯이 heap의 공간과 stack 의 공간에 나누어져 있습니다.

- 그리고 stack메모리의 경우 사용되는 양은 런타임시 결정이 되지만 스택메모리의 최대 공간 (사용가능한) 은 컴파일 시

  이미 지정이 됩니다.

- 왜 스택공간이 있는데 굳이 힙 메모리를 사용해야 하는가 ? 에 대한 궁금증이 떠오르게 됩니다.

- 제가 경험해보고 아는 선에서 몇가지만 이야기해보겠습니다.

-- (1) dynamic (동적할당)

         알고리즘 문제를 풀 때 처럼 입력의 최대값이 정해져 있는경우 그 최대치로 메모리 공간을 할당해서 컴파일 시간

         에 결정을 해서 스택메모리를 사용할 수도 있지만 (큰 사이즈의 경우 다음에 언급), 만약 사용자에 입력에 의해서 

         공간의 변동이 정해지는 경우 개발자 입장에서 미리 그 크기를 예측할 수 없으므로 런타임 시간에 변동에 맞게 

         메모리를 할당해야하는 경우 입니다.

-- (2) size 문제 (엄청 큰)

         이전 게시글에서 언급했다싶이 stack memory의 경우 최대 사이즈가 미리 정해지는 만큼 엄청 큰 사이즈가 필요

         할 경우 stack overflow가 발생할 수 있습니다. 이 때 스택에는 주소를 가리키는 포인터만 설정해주고, heap 메모

         리 공간에 큰 사이즈를 선언해서 가리키게끔 할 수 있습니다.

-- (3) 스택메모리의 life cycle

         스택 메모리의 경우 stack frame단위로 쌓이게 되는데 그 함수가 끝날경우 (life cycle)이 끝날 경우, 스택 메모리에

         서 해제됩니다. 이 경우에도 어떤 데이터를 유지하고 싶을 때는 힙 메모리 공간을 사용합니다. (직접 해제 해주기 

         전 까지 힙 영역에 저장하고 있는 데이터는 사라지지 않으므로)

2. 힙 메모리 사용 in C++

- stack 메모리 대신 heap 메모리를 사용하는 경우는 필요한 용량이 매우 크다던지, dynamic(동적)으로 런타임 시간에

   결정이 되는 변수를 사용한다던지 할 때인데요

- C++에서는 new를 통해서 힙에 공간을 할당 받고 스택 메모리에서의 포인터 변수가 이를 가리키도록 합니다.

- new를 통해서 할당을 받을경우 반드시 까먹지말고 delete을 해주어야만 메모리 leak을 막을 수 있습니다.

- new이외에도 unique_ptr 을 사용한다던지, 배열의 경우 vector를 사용하여 힙에 선언을 해준다면

- 메모리 해제 과정을 신경쓰지 않아도 되게끔 좀 더 안전하게 사용하실 수도 있습니다. 하지만 new를 사용하신다면

- 까먹지말고 반드시 delete으로 해제를 해주어야 한다는 점.!

3. stack 메모리 사용할 때와 heap 메모리 사용할 때의 차이점(장단점?)

- 우선 stack에 선언할 경우 속도가 더 빠릅니다.

- heap의 경우 원하는 만큼의 공간의 힙메모리상에서 찾고 할당하고 나중에는 이를 해제해야 하므로 상대적으로 시간이

- 많이 소요됩니다.

- 그럼에도 heap에는 큰 용량을 필요로 하는 변수라던지, 동적으로 결정이 되는 변수일 때 사용이 가능합니다.

- 그러므로 큰 사이즈가 아닌 경우 (100kb 미만? 정도?) 정도는 속도가 빠른 스택메모리를 사용하는 것이 좋습니다.

- 또 다른 차이점은 스택메모리의 경우 여러번수를 선언하고 주소를 찍어보시면 아시겠지만,

- 빽빽하게?? a가 4바이트를 차지하고, b가 4바이트를 차지한다면 메모리 주소도 4바이트(32bits) 차이가 납니다.

                   (물론 연속되게 위치하고 있을 경우를 가정)

- 중간에 빈 공간없이 빽빽하게 차지하지만, 힙의 경우 구멍이 송송뚤린 것 처럼 사이에 공간이 있습니다.

- 스택처럼 빡빡하게 메모리를 채우지는 않습니다.

0. 메모리 구조를 알아야 하는 이유.

- c++는 개발자가 메모리를 관리를 할 줄 알아야하고, memory 누출이 발생할 경우 (만약 지속적으로)

프로그램이 오류가 날 수도, 다운이 될 수도 있습니다.

- 컴퓨터 구조론인가.....배울 때 많이 학습했던 부분인 것 같은데 시간이 꽤 경과되어서... 다시 중요한 부분 위주로 다시 정리해보겠습

   니다.

1.  메모리 구성

2. Stack

- 이번 글에서는 c++의 스택구조에 대해서 상세히 정리를 해볼까 합니다.

- 변수의 코드를 짜서 포인터를 이용해서 주소를 출력해보시면 아시겠지만, 변수의 주소가 스택으로써 아래에서 위 저장

- 컴퓨터는 변수의 이름을 저장해서 바로 접근하는 것이 아닌, stack의 top의 위치에서 얼마나 떨어져있는지를 기억하여 

  접근합니다.

3. 스택프레임

- 사실 Stack 메모리에 쌓이는 단위는 변수 단위가 아닌 스택프레임 단위인데 이는 function단위 입니다.

- 변수가 하나씩 쌓이는게 아니라 function에서 차지하는 메모리 만큼이 한번에 stack에 쌓이는 것입니다.

- 또한, stack에는 function이나 main 함수의 변수들 뿐만 아니라 스택에 쌓인 function이 종료되면 다시 그 이전의

- 함수 (메인이 될수도, 또다른 function이 될수도)로 돌아 가야 하기 때문에 function call을 한 function 의 return     

   address , 그리고 그 function의 arguments 등이 같이 스택메모리 공간에 쌓입니다.

- 그 function이 끝나면 스택메모리에서 해당부분이 사라집니다.

- 프로그램 실행시 어느정도의 메모리 공간을 확보하는데 간단한 예로 너무 깊이 재귀함수를 실행할 경우, 이 스택메모

  리 공간에 계속 쌓이게 되고, 이는 스택오버플로우를 발생시키는 경우를 종종 확인하실 수 있습니다.

- c++에서는 this라는 키워드를 제공하는데 , 이를 통해서 함수를 실행하면서 객체의 멤버 변수에 쉽게 접근할 수 있습니

  다. this 역시 스택프레임에 객체의 주소를 가지고 올라감으로써 쉽게 객체의 멤버변수에 접근할 수 있도록 해주고 있

  습니다.

www.acmicpc.net/problem/1463

1. 풀이방법

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

2. 주의사항

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

-결과는 "메모리 초과"

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}