오늘의 공부

new 와 delete 

new는 C언어의 malloc을, delete는 free를 대신하는 키워드이다. 

new와 delete연산자는 내부에서 malloc()과 free()함수를 호출한다. 

◎굳이 왜 malloc과 free를 쓰지 않고 new와 delete를 사용하는 것일까?

malloc을 이용하여 동적할당을 할 때 할당할 대상의 정보를 무조건 바이트 크기 단위로 전달해야 한다는 것과 반환형이 void형 포인터이기 때문에 적절한 형 변환을 거쳐야 한다는 불편사항이 존재했었다. 

그러나 new는 메모리 크기를 정하지 않는다. 이것이 바로 new를 사용하는 가장 도드라진 특징이다.

또한 new와 malloc의 다른 점을 하나 더 뽑으라면 '생성자 함수 호출'이라는 특징이 존재한다. 

new를 통해 객체를 동적으로 생성하면서 객체의 생성자를 호출하기 때문이다. 

new와 delete는 단순히 메모리 관리 이상의 일들을 수행한다. 또한 문법적으로 연산자이며 malloc과 free는 객체지향 프로그래밍을 방해하는 원인이 될 수 있다.

◎new

int *testInt = new int;

int *testArray = new int[10];

int **testArray2 = new int*[10]; // 이중배열 동적할당

float *testFloat = new float;

double *testDouble = new double;

위와 같은 형태로 선언하면 된다. 

◎delete

위와 같은 형태로 사용하면 되며 배열은 이름의 앞에 []를 붙여 준다. 

delete testInt;

delete []testArray;

delete testFloat;

delete testDouble;

참조자와 함수

Call-by-value와 Call-by-reference는 많이 들어봤을 것이다.

Call-by-value란 '값'을 인자로 전달하는 함수의 호출 방식, Call-by-reference란 '주소 값'을 인자로 전달하는 함수의 호출방식이다. 

int main()
{
	int a = 1;
	int b = 2;
    
	CallByValue(a,b);
	CallByReference(&a, &b);
	ReferenceFunction(a, b);
}

위와 같이 구성된 main함수가 있다고 가정하자. 

⊙ Call-by-value!

void CallByValue(int num1, int num2)
{
	num1 = 50;
	num2 = 30; 
}

CallByValue함수는 위와 같이 함수의 내부에서 a와 b의 값을 바꿔도 main함수의 a, b의 값은 바뀌지 않는다.

왜?

CallByValue함수의 인자값인 int num1와 int num2는 CallByValue라는 함수의 지역변수이다. 따라서 int num1과 int num2의 값을 바꿔도 해당 num1과 num2는 CallByValue함수가 끝나면 함께 사라지게 되는 것이다.

그래서 main함수의 a,b. 즉, 함수 외부에 선언된 변수에 접근이 불가하다. 

그래서 필요한 것이 주소 값을 인자로 전달하는 Call-By-Reference이다. 

⊙ Call-by-Reference

void CallByReference(int *num1, int *num2)
{
      *num1 = 30;
      *num2 = 50;
}

 이렇게 되면 int *num1과 int *num2가 주소 값을 넘겨받아서 a와 b의 주소 값에 저장된 값을 '직접' 변경하게 되므로 함수 외부에 선언된 변수의 값을 바꿀 수 있는 것이다. 

정리하자면 Call-by-Reference는 주소 값을 전달받아서, 함수 외부에 선언된 변수에 접근하는 형태의 함수 호출이다. 

주소 값이 전달되었다는 사실이 중요한 것이 아닌 주소 값이 참조의 도구로 사용되었다는 사실이 중요한 것이며 이것이 Call-by-Value와 Call-by-Reference를 구분하는 기준이 된다.

Call-by-Value와 Call-by-Reference를 구분하는 기준에 대한 추가 설명

int *Test(int *ptr)
{
	return ptr+1;
}

int *Test2(int *ptr)
{
	*ptr = 20;
	return ptr;
}

C++에서는 함수 외부에 선언된 변수의 접근 방법으로 두 가지가 존재한다. 

하나는 '주소 값'을, 다른 하나는 '참조자'를 이용하는 방식이다.

⊙ 참조자를 이용한 Call-By-Reference? 

Call-By-Reference의 가장 큰 핵심은 함수 내에서 함수 외부에 선언된 변수에 접근할 수 있다는 것이었다. 

void ReferenceFunction(int &num1, int &num2)
{
	num1 = 10;
	num2 = 20;
 }

매개변수로 참조자가 들어와 있다. 참조자는 선언과 동시에 변수로 초기화가 되어야 하지 않나?라고 생각할 수 있다.

하지만 매개변수는 함수가 호출되어야 초기화가 진행되는 변수들이다. 즉, 초기화가 이뤄지지 않은 것이 아니라 함수 호출 시 전달되는 인자로 초기화를 하겠다는 의미이다.

이와 같은 코드는 포인터로 주소값을 넘겨받는 Call-By-Reference 보다 함수의 특성이 한눈에 파악되지 않는다는 단점이 존재한다. 참조자로 넘겨줄 때 함수는 ReferenceFunction(a, b)로 Call-By-Value함수와 동일해 보인다.

그러나 실제 함수 외부의 변수 값에 영향을 끼칠 수 없는 CallByValue함수와 달리 이 함수는 함수 외부의 값을 변경할 수 있으므로 이 함수 내부에서 어떤 일이 일어날 지 직관적으로 파악이 불가능하기 때문에 단점이라고 하는 것이다.

이 단점은 const를 사용함으로써 극복이 가능하다. 함수의 매개 변수 선언 시 const를 붙여줌으로써 함수 내에서 참조자를 이용한 값의 변경을 하지 않겠다고 선언하는 것이다.

이렇게 하면 함수 내부에서 참조자에 값을 저장하는 경우 컴파일 에러가 발생하며 함수의 원형만 봐도 값의 변경이 이루어지지 않음을 확신할수 있다. 

참조자(Reference)

변수를 선언하면 해당 변수의 이름은 할당된 메모리 공간을 가리키는, 구분 짓는 이름이 된다. 

그래서 변수를 선언할 때 int a; 를 선언했다면?

이미 a라는 이름이 가리키고 있는 메모리 공간이 있으므로 해당 범위(scope, { })에서 동일한 이름의 변수를 선언할 수가 없다. 

그런데 이 상황에서 number가 가리키는 공간에 또 하나의 이름을 부여하고 싶다면

위와 같이 b앞에 &를 붙여 선언하면 된다.

이 의미는 b라는 이름도 a라는 메모리 공간을 가리키는 또 하나의 이름이 된 것이다. 

왜 그럴까? 

보통 & 연산자는 변수의 주소값을 반환하는 연산자이다. 그러나 변수를 선언할 때 &를 붙이게 되면 이는 참조자의 선언을 의미하게 된다. 

또한 참조자를 대상으로 참조자를 선언하는 것도 가능하지만 바람직하지는 않으며 딱히 크게 사용할 일이 없다.

int a;

int &b = a;

int &c = b;

참조자의 중요한 성질 중 하나는 변수에 대해서만 선언이 가능하다는 것과 선언됨과 동시에 참조할 대상이 있어야 한다는 것이다.

또한 NULL로 초기화하는 것도 불가능하다. 

단, 다음 게시글에 나올 const 참조자는 상수도 참조가 가능하다.

https://www.acmicpc.net/problem/7576

BFS로 풀면 되는 문제이다. 

우선 토마토에 대한 정보를 입력받고 

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 1) {
				check[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}

처음에 전체 토마토 상자를 보면서 안에 익은 토마토가 어느 위치에 있는지 찾고 queue에 넣어주었다.

그후 while문으로 들어가서 현재 queue의 size만큼 for문을 돌려주면서 해당 위치의 동, 서, 남, 북의 칸을 비교해서

익지 않은 토마토(arr[y][x] == 0)이며 방문하지 않았으면(check[y][x] == false) queue에 넣고 방문했다는 표시를 한다.

for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 0 && check[i][j] == false)
			{
				return -1;
			}
		}
	}

이 부분은 처음에 런타임 에러도 발생하고 채점 결과가 틀렸다고 계속 나와서

Visual studio에서 예제를 돌렸을 때는 문제가 없어서 뭐가 문제인지 한참 고민하다가 

예를 들면 3x3 에서

이렇게 예상치 못한 상황에서 익지 못하게 되는 토마토를 확인하기 위해서 추가하게 되었다. 

#include <iostream>
#include <queue>

using namespace std;
const int MAX_BOX = 1000;
int dirX[4] = { 1, -1, 0, 0 };
int dirY[4] = { 0,0,-1,1 };
bool check[MAX_BOX + 1][MAX_BOX + 1];

int tomato(int **arr, int w, int h)
{
	int day = 0;
	queue<pair<int, int>> q;

	// 처음에 넘겨받은 토마토 상자 안에 익은 토마토가 몇 개나 있는지 
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 1) {
				check[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}

	while (!q.empty())
	{
		int q_size = q.size();
		for (int j = 0; j < q_size; j++) {

			int y = q.front().first;
			int x = q.front().second;

			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int tempy = y + dirY[i];
				int tempx = x + dirX[i];

				if ((tempy < h && tempy >= 0) && (tempx >= 0 && tempx < w)) {
					if (arr[tempy][tempx] == 0 && check[tempy][tempx] == false)
					{
						check[tempy][tempx] = true;
						q.push(make_pair(tempy, tempx));
					}
				}
			}
		}
		day += 1;
	}

	// 다 돌아봤을 때 익지 않은 토마토가 존재하면서 그곳에 방문하지 않은 경우가 있는지 확인
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 0 && check[i][j] == false)
			{
				return -1;
			}
		}
	}
	return day - 1;
}

int main()
{
	int w, h;
	cin >> w >> h;

	// 배열
	int **box = new int*[h];
	for (int i = 0; i < h; i++)
	{
		box[i] = new int[w];
	}

	// 입력받기
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> box[i][j];
		}
	}
	cout << tomato(box, w, h);
	return 0;
}

https://www.acmicpc.net/problem/6359

문제

이렇게 감옥이 n개가 있는데 

첫 번째 잔을 마신 후에는 다 열고

두 번째 잔을 마신 후에는 2의 배수번 째 방을 다 잠그고

세 번째 잔을 마신 후에는 3의 배수 번 째 방을 확인하는데 잠겨있으면 열고 열려 있으면 잠근다.

즉, 두 번째 잔을 마신 후 잠궈놓은 2,4,6... 2의 배수 번째 방은 세 번 째 잔을 마신 후에는 겹치는 방인 6,12,18,24... 번째 방은 다시 열고 3,9,15,21... 번째의 방은 다 잠근다.

이렇게 n번째(=감옥의 방 개수) 잔까지 마신 후 끝난다.

생각보다 간단했다. 

일단 처음에 모든 방을 true로 바꿔준 후(첫 번째 방은 모두 다 열었으므로)

두 번째, 세 번째,... n번 째까지 돌면서 n의 배수번째 방을 확인하며 true이면 false로 false이면 true로 바꿔준 후 마지막에 true인 방의 갯수를 세었다. 

조금 비효율적으로 푼 것 같긴한데 차차 생각해볼 문제인 것 같다. 

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

const int MAX_ROOM = 100;


int Escape(int room)
{
	bool r[MAX_ROOM + 2];
	memset(r, true, sizeof(bool)*(room+2));
	for (int i = 2; i <= room; i++)
	{
		for (int j = 1; j <= room; j++) {
			if (j % i == 0) {			
				r[j] = !r[j];
			}
		}
	}

	int count = 0;
	for (int i = 1; i <= room; i++) {
		if (r[i]) {
			count += 1;
		}
	}
	return count;
}


int main()
{
	int T = 0;
	cin >> T;

	vector<int> TestCase(T + 1);

	for (int i = 1; i <= T; i++) {
		cin >> TestCase[i];
	}

	for (int i = 1; i <= T; i++) {

		cout << Escape(TestCase[i]) << endl;
	}

}

내가 처음 문제를 읽고는 감옥의 갯수로 주어지는 n개와 상범이가 마시고 취하는 횟수인 n을 서로 다른 조건으로 보고 취하는 횟수는 언제 주는지 의아해했다.

(그럴 리가 없다고 생각했던 게 제일 컸던 것 같다. ;;) 

그리고 나는 visual studio 2017을 사용하는데 백준 문제를 제출할 때 memset을 쓰는 경우 헤더에

#include <memory.h>를 추가해야 컴파일 에러가 나지 않는다. 

https://www.acmicpc.net/problem/11727

이 문제는 다이나믹 프로그래밍 방식으로 풀면 되는 문제로

제일 마지막에 올 타일이

2x2 의 타일과 1x2 타일을 가로로 두 개 두는 경우, 그리고 2x1의 타일을 세로로 한 개 두는 경우.

이렇게 세 가지 방법이 있다고 가정하고 풀면 된다.

재귀 호출 방식으로

2x1와 2x2 타일이 제일 마지막에 위치하는 경우는 solution(n-2)를 두 번 호출 하고

1x2 타일이 제일 마지막에 위치하는 경우 solution(n-1)을 더해줬다. 

#include <iostream>

using namespace std;
int d[1001];

int solution(int n)
{
	if (d[n] > 0)return d[n];
	if (n == 1 || n == 0) return 1;

	d[n] = (2 * solution(n - 2) + solution(n - 1)) % 10007;

	return d[n];
}

int main()
{
	int n;
	cin >> n;
	cout << solution(n) << endl;
}