Feel Coding

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

이렇게 괄호의 짝이 맞는지를 알아보는 문제는 스택을 사용하면 된다.

우선 코드는 다음과 같이 짰다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;


int main() {
	while (true) {
		string s;
		getline(cin, s);
		bool flag = true;
		if (s == ".")
			break;
		stack<char> st;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '(') {
				st.push('(');
			}
			else if (s[i] == '[') {
				st.push('[');
			}
			else if (s[i] == ')') {
				if (st.empty()) {
					flag = false;
					break;
				}
				if (st.top() == '(') {
					st.pop();
				}
				else {
					flag = false;
					break;
				}
			}
			else if (s[i] == ']') {
				if (st.empty()) {
					flag = false;
					break;
				}
				if (st.top() == '[') {
					st.pop();
				}
				else {
					flag = false;
					break;
				}
			}
		}
		if (!flag)
			cout << "no\n";
		else {
			if(!st.empty())
				cout << "no\n";
			else
				cout << "yes\n";
		}
	}
	return 0;
}

'('를 만나면 스택에 push하고 ')'를 만나면 스택에서 pop하고 그 pop된게 '('가 아니라면 짝이 맞지 않는 것이다.

'['도 마찬가지로 '['를 만나면 스택에 push하고 ']'를 만나면 스택에서 pop하고 그 pop된게 '['가 아니라면 짝이 맞지 않는 것이다.

짝이 맞지 않다는 것을 발견했다면 굳이 문자열의 끝까지 돌 필요가 없으므로 break를 해서 for문을 빠져나온다.

그 전에 짝이 맞지 않는 문자열이라는 것을 표시하기 위해 flag 변수를 false로 바꿔준다.

for문 바깥에서 flag가 true인지 false인지 확인해보고 false라면 no를 출력한다.

하지만 flag가 true라고 해서 무조건 yes를 출력하면 안 된다.

주의할 점은 문자열의 끝까지 다 잘 돌고 나서도 스택이 비어있는지를 반드시 확인해야 한다.

이 코드로 따졌을 때 flag가 true라고 하더라도 스택이 비어있지 않으면 no를 출력해야 한다.

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

최단경로를 구하는 것이기 때문에 BFS(너비 우선 탐색)로 풀면 된다. 가중치가 없는 그래프에서 최단경로를 구하라고 하면 무조건 BFS이다. 이 지도에서는 상하좌우 어디든 비용이 1이므로 가중치가 없다고 할 수 있다.

일단 코드는 다음과 같다.

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


int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<char>> map(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	int maxDistance = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'L') {
				queue<tuple<int, int, int>> q;
				vector<vector<bool>> visited(n, vector<bool>(m));
				q.push(make_tuple(i, j, 0));
				while (!q.empty()) {
					tuple<int, int, int> cur = q.front();
					q.pop();
					int row = get<0>(cur);
					int col = get<1>(cur);
					if (!visited[row][col]) {
						if (get<2>(cur) > maxDistance)
							maxDistance = get<2>(cur);
						visited[row][col] = true;
						if (row + 1 < n && map[row + 1][col] == 'L' && !visited[row + 1][col]) {
							q.push(make_tuple(row + 1, col, get<2>(cur) + 1));
						}
						if (row - 1 >= 0 && map[row - 1][col] == 'L' && !visited[row - 1][col]) {
							q.push(make_tuple(row - 1, col, get<2>(cur) + 1));
						}
						if (col + 1 < m && map[row][col + 1] == 'L' && !visited[row][col + 1]) {
							q.push(make_tuple(row, col + 1, get<2>(cur) + 1));
						}
						if (col - 1 >= 0 && map[row][col - 1] == 'L' && !visited[row][col - 1]) {
							q.push(make_tuple(row, col - 1, get<2>(cur) + 1));
						}
					}
				}
			}
		}
	}
	cout << maxDistance;
	return 0;
}

육지인 칸이라면 매 칸마다 BFS를 하면 된다. BFS를 하기 위해 큐를 사용했고 큐에는 tuple 객체를 만들어 넣어주었다.

튜플의 첫 번째 원소는 행, 두 번째 원소는 열, 세 번째 원소에는 BFS를 시작한 그 칸에서 여기까지의 거리를 저장해주었다. 그리고 최대 거리를 maxDistance에 저장하며 갱신해주었다.

상하좌우를 탐색하기만 하면 된다. 다른 BFS와 조금 다른 점은 보통 BFS는 특정 지점에서 특정 지점으로 가는 최단경로를 구하는 것이기 때문에 visited 배열도 하나만 필요했고 다 공유했다. 하지만 이 문제에서는 특정 지점에서 특정 지점으로 가는 것이 아니라 어느 지점인지 모르는 지점에서 어느 지점인지 모르는 지점까지의 최단경로 중 최장경로를 찾는 것이기 때문에 모든 육지에서 나머지 육지로 가는 모든 경우의 수를 구해야 한다. 따라서 한 칸마다 BFS를 새로 시작하기 때문에 매 칸마다 그 칸을 위한 visited 배열도 새로 만들고 queue도 새로 만들어줘야 한다.

지난 번에 올린 이 글에 이어지는 내용이다. (링크↓)

https://breakcoding.tistory.com/294

이전 포스팅의 마지막 부분에 함수의 리턴값으로 배열을 반환할 수는 없지만 배열의 주소 즉 포인터를 리턴할 수는 있다고 말했었다.

그러면 한 번 실험해보자.

이 함수는 반환값으로 포인터를 return하므로 반환타입은 int*이다.

#include <iostream>
using namespace std;

int* makeArray() {
	int arr[5] = { 1, 2, 3, 4, 5 };
	return arr; //배열의 주소 반환
}

int main() {
	int* myArray = makeArray(); //myArray라는 포인터변수에 배열의 주소를 받음
	for (int i = 0; i < 5; i++) {
		cout << myArray[i] << endl;
	}
	return 0;
}

이 코드를 실행하면

1, 2, 3, 4, 5가 아니라 엉뚱한 쓰레기값을 출력하는 것을 볼 수 있다.

이런 결과가 나오는 이유는 함수가 호출될 때 메모리의 스택이 어떻게 동작하는지를 알면 알 수 있다.

#include <iostream>
using namespace std;

int add(int num1, int num2) {
	int sum = num1 + num2;
	return sum;
}

int main() {
	int a = 5;
	int b = 2;
	int aPlusB = add(a, b);
	return 0;
}

이런 코드가 있다고 하자.

이 코드가 실행될 때 스택의 모습은 다음과 같다.

이것과 마찬가지로 위에서 본 이 코드는

#include <iostream>
using namespace std;

int* makeArray() {
	int arr[5] = { 1, 2, 3, 4, 5 };
	return arr; //배열의 주소 반환
}

int main() {
	int* myArray = makeArray(); //myArray라는 포인터변수에 배열의 주소를 받음
	for (int i = 0; i < 5; i++) {
		cout << myArray[i] << endl;
	}
	return 0;
}

이 그림에서 4번째 스택 모습에서 문제가 생기는 것이다.

바로 이 상태이다.

makeArray() 함수가 종료되면서 배열 arr의 시작 주소인 1000번지만 넘겨주고 배열 arr은 스택에서 사라졌는데 1000번지에 가서 1000번지에 있는 쓰레기 값, 1004번지에 있는 쓰레기 값, 1008번지에 있는 쓰레기 값, 1012번지에 있는 쓰레기 값, 1016번지에 있는 쓰레기 값을 출력하고 종료하는 것이다.

바로 이렇게 말이다.

1은 우연히 스택에서 makeArray 함수가 끝나도 그 메모리가 쓰던 곳은 손상되지 않고 남아있어서 아주 운 좋게 1이 출력된 것이다.

일반적으로 프로그램을 실행하면서 필요한 변수들은 대부분 메모리의 스택 영역에 할당된다. 이것을 활성레코드라고 한다. 프로그램이 실행될 때에는 활성레코드 부분이 늘었다 줄었다 하면서 실행되는 것이다. 위에서 본 스택 그림처럼 말이다. 이 문제는 배열이 이러한 스택 영역에 할당되었기 때문에 생기는 문제이다.

이러한 문제를 해결할 수 있는 것이 바로 동적할당이다. 이게 바로 동적 할당이 필요한 이유이다.

스택에 저장된 활성레코드는 그 부분이 실행되고 나면 사라진다. 하지만 메모리에는 스택 영역 말고 힙(heap)이라는 영구 저장소가 있다. 동적 할당을 하면 힙(heap)에 저장이 된다. 힙(heap)에 저장된 것들은 delete를 사용하여 명시적으로 제거하지 않는 이상 프로그램이 종료될 때까지 존재한다.

동적할당은 다음과 같이 new 연산자를 사용하여 한다.

int* p = new int;

new 연산자를 사용하여 동적 배열을 생성하고 싶다면

int* list = new int[SIZE];

이렇게 하면 된다.

동적할당은 포인터 없이는 할 수 없다.

변수에는 동적으로 할당되는 변수가 있고 정적으로 할당되는 변수가 있다. 컴파일러는 컴파일을 할 때 이 프로그램에서 사용할 메모리를 대충 계산한다. 그 다음에 이거를 운영체제에게 알려준다. 예를 들어 컴파일러가 대충 계산했을 때 800바이트가 필요하다 하면 OS는 800바이트 이상을 스택에 여유있게 잡아놓는다. 이게 정적으로 할당하는 것이다.

그렇기 때문에 다음과 같은 코드는 컴파일 에러가 나는 것이다.

#include <iostream>
using namespace std;

int main() {
	int size;
	cin >> size;
	int arr[size];
	return 0;
}

사용자에게 size를 입력받아서 그 크기만큼 배열을 잡고 싶은 건데 이러한 코드는 불가능하다. 컴파일 할 때 필요한 메모리를 계산을 해야 하는데 size는 사용자에게 입력받는 것이기 때문에 컴파일 할 때에는 알 수가 없고 실행될 때 값이 결정된다. 따라서 컴파일러는 arr 배열을 메모리에 얼만큼 잡아야 하는지 모르므로 컴파일 에러가 나는 것이다. 따라서 배열의 크기를 정하는 변수는 반드시 const 변수여야 한다.

#include <iostream>
using namespace std;

int main() {
	int size = 5;
	int arr[size];
	return 0;
}

이 코드를 실행해도 컴파일에러가 난다.

배열의 크기를 정하는 저 자리에는 상수 혹은 const 변수(상수 변수)만 들어갈 수 있다.

#include <iostream>
using namespace std;

int main() {
	const int size = 5;
	int arr[size];
	return 0;
}

이렇게 const를 써줘야만 컴파일 에러가 나지 않는다.

그러면 사용자에게 크기를 입력 받아 그 크기 만큼의 배열을 생성하고 싶다면 어떻게 해야 할까?

동적할당을 사용하면 된다.

#include <iostream>
using namespace std;

int main() {
	int size;
	cin >> size;
	int* arr = new int[size];
	return 0;
}

동적할당으로 배열을 생성하면 이렇게 메모리를 얼만큼 잡을지 메모리의 크기를 실행 도중에 정할 수가 있다.

(컴퓨터에서 '동적'이라는 단어가 나오면 실행 도중이라는 뜻이고 '정적'이라는 것은 프로그램 실행 전을 말한다.)

위에서 봤던 코드를 다시 보자.

int* p = new int;

여기에서 포인터변수 p는 정적으로 할당된 변수이다. 포인터변수이므로 컴파일러가 4바이트 만큼을 메모리의 스택 부분에 잡는다. (int라서 4바이트를 잡는 것이 아니다. 이 부분이 헷갈리면 포인터 글을 다시 참고하면 된다.)

하지만 포인터변수 p가 가리키는 int는 동적으로 실행 중에 메모리의 힙(heap) 영역에 잡히게 된다.

.

.

곧 이어서 쓰겠습니다.

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

분할 정복 문제로, 재귀로 풀면 된다.

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

int white = 0;
int blue = 0;

void divide(int startRow, int startCol, int endRow, int endCol) {
	//cout << startRow << "~" << endRow << "행 " << startCol << "~" << endCol << "열" << endl;
	int color = v[startRow][startCol];
	bool flag = true;
	for (int i = startRow; i <= endRow; i++) {
		for (int j = startCol; j <= endCol; j++) {
			if (v[i][j] != color) {
				flag = false;
				break;
			}
		}
		if(!flag)
			break;
	}
	if (!flag) {
		//cout << "한 덩어리로 안 됨" << endl;
		divide(startRow, startCol, startRow + (endRow - startRow) / 2, startCol + (endCol - startCol) / 2);
		divide(startRow, startCol + (endCol - startCol) / 2 + 1, startRow + (endRow - startRow) / 2, endCol);
		divide(startRow + (endRow - startRow) / 2 + 1, startCol, endRow, startCol + (endCol - startCol) / 2);
		divide(startRow + (endRow - startRow) / 2 + 1, startCol + (endCol - startCol) / 2 + 1, endRow, endCol);
	}
	else {
		if (v[startRow][startCol] == 0) {
			//cout << "흰 종이" << endl;
			white++;
		}
		else {
			//cout << "파란 종이" << endl;
			blue++;
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	v = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	divide(0, 0, n - 1, n - 1);
	cout << white << endl;
	cout << blue << endl;
	return 0;
}

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

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	while (true) {
		int a, b;
		cin >> a >> b;
		if (a == 0 && b == 0) {
			break;
		}
		if (a % b == 0) {
			cout << "multiple\n";
		}
		else if (b % a == 0) {
			cout << "factor\n";
		}
		else {
			cout << "neither\n";
		}
	}
	return 0;
}

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

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	if (n == 1) {
		cout << '*';
	}
	else {
		for (int i = 0; i < 2 * n; i++) {
			for (int j = 0; j < n; j++) {
				if (i % 2 == 0) {
					if (j % 2 == 0) {
						cout << '*';
					}
					else {
						cout << " ";
					}
				}
				else {
					if (j % 2 == 0) {
						cout << " ";
					}
					else {
						cout << '*';
					}
				}
			}
			cout << '\n';
		}
	}
	return 0;
}

카누로도 해보고 맥심 화이트골드로도 해봤는데 카누보다 맥심이 훨씬 더 잘 만들어지고 금방 만들어진다.

기계로도 해보고 손으로도 해봤는데

맥심 화이트골드 기계로 하면 1분

맥심 화이트골드 손으로 하면 5분

카누 기계로 하면 7분

카누 손으로는 안 해봄

다들 카누가 제일 잘 된다고 하는데 그건 설탕이나 프림이 없어서 편하다는거고 잘 되는거는 맥심 화이트골드가 최고다.

제일 빨리 완성된다.

준비물: 맥심 화이트 골드 믹스커피 2개, 설탕, 뜨거운 물, 체(거름망), 큰 컵이나 그릇 (반드시 커야 한다. 이왕이면 플라스틱이 좋다.)

1. 맥심 화이트골드 2개를 뜯어서 커피만 남도록 체에 거른다.

이렇게 하면 계량스푼 티스푼으로 1스푼과 1/4스푼 정도 나온다.

2. 준비한 컵이나 그릇에 커피 한 티스푼을 넣는다.

3. 설탕 한 티스푼을 넣는다.

4. 뜨거운 물 한 티스푼을 넣는다.

5. 잘 녹여준다. (커피가루가 잘 녹지 않으면 볼에 뜨거운 물을 받아서 중탕으로 녹여준다)

중탕을 하면 이렇게 5초만에 잘 녹는다.

6. 미친듯이 섞어준다.

이렇게 미친듯이 섞다보면 5분만에 이렇게 된다. 굳이 원을 그려가면서 저을 필요 없고 한 방향으로만 할 필요도 없고 저렇게만 해도 된다. 아주 빨리 하면 된다. 큰 그릇이고 플라스틱 그릇일수록 좋다. 유리컵은 깨질까봐 조심하게 되는 경향이 있는 것 같다. 그리고 작은 컵에도 해봤는데 세 배 더 오래걸렸다. 큰 컵에 하자.

7. 완성

정말 부드럽고 맛있다.

전동 거품기(휘핑기)로 하면 1분만에 완성할 수 있다.

카누로 하면 전동 거품기를 써도 맥심 화이트골드를 손으로 한 것보다 오래 걸린다. 카누로 했을 때 좋은 점은 설탕과 프림이 없어서 체에 거를 필요가 없다는 장점밖에 없는 것 같다.

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

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		cin >> arr[i];
		if (arr[i] < 40)
			arr[i] = 40;
	}
	int sum = 0;
	for (int i = 0; i < 5; i++) {
		sum += arr[i];
	}
	cout << sum / 5;
	return 0;
}

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

#include <iostream>
using namespace std;

int main() {
	int x, y; 
	cin >> x >> y;
	if (x > 0 && y > 0) {
		cout << 1;
	}
	else if (x > 0 && y < 0) {
		cout << 4;
	}
	else if (x < 0 && y > 0) {
		cout << 2;
	}
	else {
		cout << 3;
	}
	return 0;
}

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

Ai - b (각 시험장에 있는 응시자의 수 - 총감독관이 한 시험장에서 감시할 수 있는 응시자의 수) 이렇게 뺄셈할 때 주의할 점이 있다. 총감독관이 한 시험장에서 감시할 수 있는 응시자의 수가 각 시험장의 응시자 수보다 클 수 있다. 따라서 이렇게 빼면 음수가 될 수도 있다.

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

int main() {
	long long n;
	cin >> n;
	vector<int> numOfPeople(n);
	for (int i = 0; i < n; i++) {
		cin >> numOfPeople[i];
	}
	long long b, c;
	cin >> b >> c;
	long long total = n;
	for (int i = 0; i < n; i++) {
		if ((numOfPeople[i] - b) % c == 0) {
			if (numOfPeople[i] - b > 0)
				total += (numOfPeople[i] - b) / c;
		}
		else {
			if (numOfPeople[i] - b > 0)
				total += (numOfPeople[i] - b) / c + 1;
		}
	}
	cout << total;
	return 0;
}