1-A 메모리 초과

안녕하세요 수범님 ㅎㅎ

일단, 이건 제 잘못이 크네요..

memcpy()함수에 대한 설명이 교안에 좀 부족했던 거 같습니다.

memcpy()는 vector를 복사할 때 깊은 복사가 되지 않습니다.

수범님께서 이렇게 해주셨는데요.

			memcpy(&ret, &v, sizeof(v));

이렇게 해서 올바르게 copy가 일어나고 로직이 잘 수행된 거 같지만, 사실은 잘 되지 않을 수 있습니다. 이를 UB라고 합니다.

교안에 있는 내용을 좀 수정해봤는데요. 다음과 같습니다. 해당 내용은 수정되어 방금 반영되었습니다.

memcpy()와 copy()

어떤 변수를 깊은 복사할 때 memcpy()와 copy()를 씁니다. memcpy()는 Array끼리 복사할 때 쓰이고 copy()는 Array, vector 모두 쓰일 수 있습니다.

얕은 복사와 깊은 복사

참고로 얕은 복사(Shallow copy)는 메모리 주소값을 복사한 것이라 복사한 배열을 수정하면 원본 배열이 수정되는 복사방법이며 깊은 복사(Deep copy)는 새로운 메모리 공간을 확보해 완전히 복사해 복사한 배열을 수정하면 원본 배열은 수정되는 않는 복사방법을 의미합니다.

memcpy()

memcpy()는 어떤 변수의 메모리에 있는 값들을 다른 변수의 “특정 메모리값”으로 복사할 때 사용합니다. Array를 깊은 복사할 때 쓰입니다.

void memcpy ( void destination, const void * source, size_t num );

이처럼 v라는 Array를 ret에다가 복사하는 것을 볼 수 있습니다.

#include<bits/stdc++.h>
using namespace std; 
int main(void) {
int v[3] = {1, 2, 3};
int ret[3]; 
memcpy(ret, v, sizeof(v) );
cout << ret[1] << "\n";
ret[1] = 100;
cout << ret[1] << "\n";
cout << v[1] << "\n";
return 0;
}
/*
2
100
2
*/

제대로 깊은 복사가 되어 ret을 수정하더라도 vector v는 수정되지 않는 것을 볼 수 있습니다.

보통은 어떻게 쓰일까요?

예를 들어 a라는 원본배열이 수정되는 로직이 있습니다. 근데 그 다음에 이 원본배열이 수정되지 않은 상태값을 기반으로 또 어떠한 로직이 필요할 때가 있습니다. 

그럴 때 memcpy를 주로 씁니다. (물론 다른 이유로도 쓰지만요.)

아래의 모습은 temp라는 배열에 a를 담아두고 a를 수정하는 로직을 구현한 뒤 a라는 배열에 다시 예전 온전한 a를 담은 temp를 이용해 다시 a를 만드는 모습입니다.   

#include <bits/stdc++.h>
using namespace std;
int a[5], temp[5]; 
int main(){
    for(int i = 0; i < 5; i++)a[i] = i;
    memcpy(temp, a, sizeof(a));
    for(int i : temp) cout << i << ' ';
    cout << '\n';
    // 원본 배열 a를 수정하여 출력하는 로직
    // a를 수정해서 ~~를 더하는 로직이 될 수 있겠죠?
    a[4] = 1000;
    for(int i : a) cout << i << ' '; 
    cout << '\n';
    // 그 다음 다시 temp를 기반으로 원본배열을 담아 둠.
    memcpy(a, temp, sizeof(temp));
    for(int i : a) cout << i << ' '; 
    cout << '\n';
    return 0;
}
/*
0 1 2 3 4
0 1 2 3 1000
0 1 2 3 4 
*/

다만 memcpy()는 vector에서는 깊은 복사가 되지 않습니다. 

#include<bits/stdc++.h>
using namespace std; 
int main(void) {
vector<int> v {1, 2, 3};
vector<int> ret(3);
memcpy( &ret, &v, 3*sizeof(int) );

cout << ret[1] << "\n";
ret[1] = 100;
cout << ret[1] << "\n";
cout << v[1] << "\n";
return 0;
}
/*
2
100
100
*/

앞의 코드처럼 ret[1]을 수정했더니 v[1]도 수정되는 것을 볼 수 있습니다. 

이는 memcpy는  TriviallyCopyable인 타입이 아닌 경우 함수자체가 제대로 동작하지 않습니다.  

아래 글은 memcpy의 설명 모습입니다.

Copies count bytes from the object pointed to by src to the object pointed to by dest.

If the objects overlap, the behavior is undefined. If the objects are not trivially copyable (e.g. scalars, arrays, C-compatible structs), the behavior is undefined.

다음 코드처럼 is_trivial를 통해 해당 타입이 TriviallyCopyable한지 확인할 수 있는데 vector는 그렇지 않는 것을 볼 수 있습니다. 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    if (is_trivial<vector<int>>())
        cout << "Hello Kundol!\n";
}
// kundol이 출력되지 않음

memcpy는 Array에서만 동작한다는 것을 기억해주세요. 

copy()

memcpy()와 똑같은 동작을 하는 함수입니다. vector와 Array 모두 쓰일 수 있습니다.

OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)

만약 vector v를 ret에다가 옮기고 싶다면 다음과 같이 하면 됩니다.  

v : 복사당하는 vector, ret : 복사하는 vector 

copy(v.begin(), v.end(), ret.begin());   

#include<bits/stdc++.h>
using namespace std; 
int main(void) {
vector<int> v {1, 2, 3};
vector<int> ret(3);
copy(v.begin(), v.end(), ret.begin());  
cout << ret[1] << "\n";
ret[1] = 100;
cout << ret[1] << "\n";
cout << v[1] << "\n";
return 0;
}
/*
2
100
2
*/

다음과 같이 ret이란 vector에 vector v의 값이 잘 들어간 것을 볼 수 있습니다. 이 때 복사하는 vector와 복사당하는 vector의 크기를 맞춰주는 것이 중요합니다. v의 크기는 3이며, ret의 크기도 3으로 설정된 것을 볼 수 있습니다. 그리고 깊은 복사가 되어 ret을 수정하더라도 v에는 아무런 영향을 미치지 않는 것을 볼 수 있습니다.

Array는 다음과 같이 쓰입니다. 

#include<bits/stdc++.h>
using namespace std; 
int main(void) {
int v[3] = {1, 2, 3};
int ret[3];
// + 3은 3으로 고정된 것이 아닌 해당 배열의 사이즈를 추가한다.
copy(v, v + 3, ret);  
cout << ret[1] << "\n";
ret[1] = 100;
cout << ret[1] << "\n";
cout << v[1] << "\n";
return 0;
}
/*
2
100
2
*/

즉, vector 같은 경우 memcpy가 아니라 copy를 써주셔야 합니다.

		int sum = accumulate(v.begin(), v.begin() + 7, 0);
		if (sum == 100) {   
			copy(v.begin(), v.end(), ret.begin());  
			ret.pop_back();
			ret.pop_back(); 

이렇게 코드를 바꿔보시겠어요?

그리고 불필요한 코드를 제거해봤는데요.

전체 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;

vector<int> v(9);
vector<int> ret(9);

void makePermutation(int n, int r, int depth) {
	if (depth == r) {
		int sum = accumulate(v.begin(), v.begin() + 7, 0);
		if (sum == 100) {   
			copy(v.begin(), v.end(), ret.begin());  
			ret.pop_back();
			ret.pop_back(); 
			sort(ret.begin(), ret.end());
			for (auto data : ret)cout << data << '\n';
			
			exit(0);
		}
		return;
	}
	for (int i = depth; i < n; i++) {
		swap(v[i], v[depth]);
		makePermutation(n, r, depth + 1);
		swap(v[i], v[depth]);
	}
}


int main(void) {

	for (int i = 0; i < 9; i++) { cin >> v[i]; }
	makePermutation(9, 7, 0);   
	return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

답변 감사합니다!