대엉코딩

오늘은 적성시험을 보느라 많은 걸 하진 못했지만...^

요즘 문자열관련 문제를 좀 풀어보고 있는 중입니다..

c++ string 에서 push_back(char c) 즉 push_back은 쓸수 있지만 한글자만 넣을 때 사용가능

문자열을 붙일 경우 그냥 + 를 사용해서 뒤에 붙이시면 됩니다.

string to int --> stoi(string)

int to string --> to_string(int) 

사용

간단하게 정리했습니다

오늘은 프로그래머스 해쉬문제를 풀면서 하나 알게된 사실이 있습니다..

c++ algorithm 라이브러리 sort()를 이용할 경우

문자열은 사전 순으로 정렬이 된 결과가 나옵니다.

unordered_map의 경우 잘 안써와서 미숙한데, 그래도 알아두어야 겠다 생각하여 따로 작성해서 

게시글로 올려야 겠네요....! 

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

	return 0;
}

** 잘못된 내용이 있으면 알려주세요 **

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 역시 스택프레임에 객체의 주소를 가지고 올라감으로써 쉽게 객체의 멤버변수에 접근할 수 있도록 해주고 있

  습니다.

vector는 오름차순 정렬 되어있어야합니다(이진탐색 기반이기 때문에)

참조 타입 변수(레퍼런스) 는 별명과 같은 느낌이라고 보면 될 것이다.

c++의 포인터 와 레퍼런스의 차이점을 알아보자.

# 포인터는 null을 가리킬 수 있지만 참조 타입 변수는 null을 가리킬 수 없다.

   - 포인터를 초기화 하지 않거나 null을 가리키고 있는 포인터에 접근 했을 때

     발생하는 에러가 참조 타입 변수에서는 나타나지 않는다.

# 참조 타입 변수는 선언과 동시에 초기화 하지않으면 컴파일 오류가 발생한다.

# 포인터는 * , -> 등의 포인터 연산자를 통해서 접근 해야 하지만 참조 타입 변수는

   마치 지역변수 처럼 접근할 수 있다.

# 참조 타입 변수는 초기화 과정에서만 값을 할당 할 수 있고 이후에 다시 할당을

   시도 할 경우 컴파일 에러가 발생한다. 하지만 포인터 변수는 참조 대상을 언제든지 변경할 

   수 있다.

- 대표적인 swap 예제 이다.

Call by value로 swap을 할경우 swap 함수에서 변수의 값을 전달 받기는 하지만

Num1,과 num2의 값만 넘겨 받았을 뿐 그것이 num1과 num2는 아니기 때문에

함수가 종료되면 main 함수에 직접 영향을 끼치지 못한다.

Call by reference의 경우 주소를 통해 전달 받은 값들을 변경하는 것이므로

종료된 이후에도 참조 했던 주소의 값들이 바뀌어 있으므로 main함수에 있는 num1과

Num2도 영향을 받아 swap이 된다.

그리고 call by value 이용하여 함수에 접근 할 경우 value 값을 저장할 새로운 공간을 할당

받아야 하므로

call by reference에 비하여 시간이 더욱 오래 걸린다.

<예시코드>

<결과창>