Feel Coding

2020년 2월 29일에 토익스피킹 시험을 신청해놓고 방학동안 토익스피킹을 준비하고 있었다.

2월 25, 26일을 제외하고 토익스피킹을 하루에 30분 넘게 공부한 적은 없는 것 같은데 그래도 하루도 거르지 않고 매일 토익스피킹 공부를 했다.

고작 1분짜리 mp3 듣고 한 문장씩 따라하는 거라도 매일 했다.

정말 실전처럼 11문제를 15분 동안 쭉 해본 것은 2월 24일이 처음이었다. 

실전을 해보니까 정말 정말 달랐다.

파트5는 그냥 거의 아무런 말도 못 했다. 이거는 영어 실력의 문제가 아니라 정말 해결책이 생각이 안 났다. 해결책이 생각이라도 나면 영어로 더듬더듬이라도 말할 텐데 정말 어려운 상황을 주어주고 해결책을 제시하라고 하니 정말 너무나도 어려웠다.

파트5 문제를 예를 들자면

신입사원 교육을 해야 하는데 공간이 생각보다 좁다. 두 팀으로 나눠서 다른 공간에서 진행하기에는 교육을 해줄 인력을 더 채용해야 하므로 비용이 더 들어서 안 되고 꼭 모든 신입사원들을 같이 교육시켜야 한다. 해결책을 제시해라.

아니면

공원에 사람들이 쓰레기를 너무 많이 버린다. 쓰레기통도 많이 있는데 사람들이 그냥 길거리에 버린다. 길에 버리지 말라는 표지판도 여기저기 설치해놨지만 효과가 없었다. 해결책을 제시해라.

뭐 이런 문제들이다.

정말 한국어로도 해결책이 생각이 안 나는 문제다.

그래서 정말 거짓말이 아니라 실전 8회까지 하는 동안 파트 5는 제대로 한 적이 단 한번도 없었다.

그리고 파트4는 항상 답변을 다 하기 전에 시간이 끝났다. 파트6는 1분동안 내 의견을 말하는건데 사교육을 왜 반대하는지 한국어로도 이유를 제대로 못 말하는데 영어로 1분동안 말하라고 하니 정말 너무나도 어려웠다. 수업 정원을 줄이면 학습에 효과가 있을지 좋은 전자기기를 이용하면 어떻게 수업이 효율적으로 진행될 수 있는지 한국어로도 어려운 것을 영어로 당연히 못 말했다.

그래서 토익은 레벨5 정도만 나와도 감사하게 생각하면서 제발 레벨5만 나와라 하고 있었다. (내가 지원하고 싶은 인턴의 최소 지원 자격이 토스 레벨5 또는 오픽 IL이었기 때문)

그래도 시험 4일 전에 실전 15회 모의고사 책까지 사면서 나름 열심히 벼락치기를 하고 있었다.

그런데

시험 이틀 전인 2월 27일 아침에 눈을 떴더니 토익스피킹 취소가 되었다는 문자가 와 있었다.

정말 허무했다. 뭐 엄청나게 열심히 준비한건 아니지만 3월에 토익스피킹 자격증이 꼭 필요할 것 같아서 2월 중에 꼭 따놓으려고 했던건데 너무 아쉬웠다. 이게 취소되면 나는 인턴에 지원할 기회조차 얻지 못하는 것이라서 너무 억울했다. 시험 일주일 전도 아니고 시험 이틀전에 취소하는 것은 정말 너무한다고 생각한다.

그래도 한 편으로는 '이제 자유를 얻었다 이제 그냥 놀자' 하고 2월 27, 28일은 그냥 아무것도 안 하고 놀았다.

그런데 2월 28일 저녁에 문득 오픽 시험은 취소 안 됐나? 하는 생각이 들어서 오픽 홈페이지에 들어가보았다.

그랬더니 3월 1일 시험 접수가 2월 28일 11시 59분까지였다. 시험장을 확인해봤더니 역삼센터에 자리가 있었다.

그래서 정말 즉흥적으로, 정말 아무 생각없이 오픽을 신청해버리고 말았다.

사실 나도 그 때 무슨 생각으로 그런 짓을 했는지 모르겠다. 당장 48시간도 안 남은 시험을 신청해버렸으니 말이다.

정말 최소지원자격인 IL을 목표등급으로 설정해놓았었다. 나는 성적이 잘 나오는 게 목표가 아니라 인턴에 지원할 자격이라도 갖추고 싶어서 지원한 것이니까 정말 진심으로 목표가 그랬었나보다.

그래도 8만원이나 하는 시험인데 노하우나 팁이라도 알아야겠다 싶어서 유튜브에 오픽노잼 영상을 2~3개 정도 보고 시험장에 갔다. 정말 너무 당황스러운 질문들이 많아서 막 지어내기도 하고 Um~도 꽤 했고 내가 봐도 너무 어이없게 답변한 것 같아서 돌아오는 길에 엄마한테 전화해서 흑역사 만들었다며 얘기했는데 엄마가 뭐 잘 보러 간것도 아닌데 뭐 하시면서 그 김에 잠실역 삼송빵집에서 옥수수빵이나 사오라고 해서 맛있는 빵을 사서 집에 돌아왔다.

그리고 4일 뒤 3월 5일...

성적발표날

12시 정도에 깼는데 성적발표가 1시간이나 남아있어서 아침 먹는 동안 계속 떨렸다. 내심 기대했나보다.

그리고 한 시가 되어서 확인하는데

최고등급인 AL이 떴다. 기분이 너무 좋았다.

2월 동안 미드 쉐도잉을 한 게 효과가 있었나?

영어를 못 하는건 절대 아니었고 리딩 리스닝은 솔직히 잘하는 편이었지만 스피킹은 정말 자신이 없었는데 시험장에서 생각보다 술술 나와서 나 자신에게 놀라긴 했다. 이 참에 영어 스피킹 공부 좀 열심히 해봐야겠다.

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

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

int main() {
	while (true) {
		string s;
		cin >> s;
		if (s == "#") {
			break;
		}
		int count = 0;
		for (int i = 0; i < s.size() - 1; i++) {
			if (s[i] == '1')
				count++;
		}
		if (s[s.size() - 1] == 'e') {
			if (count % 2 == 0) {
				s[s.size() - 1] = '0';
			}
			else {
				s[s.size() - 1] = '1';
			}
		}
		else {
			if (count % 2 == 0) {
				s[s.size() - 1] = '1';
			}
			else {
				s[s.size() - 1] = '0';
			}
		}
		cout << s << '\n';
	}
	return 0;
}

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

동적계획법 문제이다. 동적계획법 문제는 점화식만 잘 세우면 된다.

나는 일단 4까지는 노가다로 구한 뒤 규칙을 찾았다.

점화식은

dp[i] = 2 * dp[i - 1] + dp[i - 2]

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

int main() {
	int n;
	cin >> n;
	vector<int> dp(n + 1);
	dp[0] = 1;
	dp[1] = 3;
	for (int i = 2; i <= n; i++) {
		dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
	}
	cout << dp[n];
	return 0;
}

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

동적계획법으로 풀 수 있다.

아래 표 dp의 k행 n열은 숫자 k개를 가지고 n을 만들 수 있는 경우의 수이다.

3행 4열을 예로 들면

dp[3][4]는 3가지 수로 4를 만들 수 있는 방법의 개수인데 4는 0+4, 1+3, 2+2, 3+1, 4+0으로 나타낼 수 있다.

그런데 3행을 채울 당시에는 2행까지만 채워있으니 2행까지 구해놓은 것들을 가지고 3행을 구하면 된다.

0+4는 dp[1][0]*dp[2][4]로 표현 가능하고

(dp[1][0]은 1가지 수로 0을 만들 수 있는 방법의 개수, dp[2][4]는 2가지 수로 4를 만들 수 있는 방법의 개수)

1+3은 dp[1][1]*dp[2][3]으로 표현 가능하고

(dp[1][1]은 1가지 수로 1을 만들 수 있는 방법의 개수, dp[2][3]은 2가지 수로 3을 만들 수 있는 방법의 개수)

2+2는 dp[1][2]*dp[2][2]로 표현 가능하고

(dp[1][2]는 1가지 수로 2를 만들 수 있는 방법의 개수, dp[2][2]는 2가지 수로 2를 만들 수 있는 방법의 개수)

3+1은 dp[1][3]*dp[2][1]으로 표현 가능하고

(dp[1][3]은 1가지 수로 3을 만들 수 있는 방법의 개수, dp[2][1]는 2가지 수로 1을 만들 수 있는 방법의 개수)

4+0은 dp[1][4]*dp[2][0]으로 표현 가능하다.

(dp[1][4]는 1가지 수로 4를 만들 수 있는 방법의 개수, dp[2][0]는 2가지 수로 0를 만들 수 있는 방법의 개수)

즉, dp[3][4] = dp[1][0]*dp[2][4] + dp[1][1]*dp[2][3] + dp[1][2]*dp[2][2] + dp[1][3]*dp[2][1] + dp[1][4]*dp[2][0] 이다.

그런데 1행 즉 K가 1일 때에는 항상 값이 1이므로 1행의 1은 굳이 안 곱해줘도 된다.

따라서  dp[3][4] = dp[2][4] + dp[2][3] + dp[2][2] + dp[2][1] + dp[2][0] 이다.

점화식은 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j - 2] + dp[i - 1][j - 3] + ... + dp[i - 1][0] 으로 표현할 수 있다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> dp(k + 1, vector<int>(n + 1));
	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= k; i++) {
		dp[i][0] = 1;
	}
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int c = 0; c <= j; c++) {
				dp[i][j] = (dp[i][j] + dp[i - 1][c]) % 1000000000;
			}
		}
	}
	cout << dp[k][n];
	return 0;
}

오버플로우가 나지 않게 중간중간 1000000000으로 나눠줘야 한다.

이 코드를 제출하니 12ms가 나왔다.

다음은 개선된 코드이다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> dp(n + 1, 1);
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
				dp[j] = (dp[j - 1] + dp[j]) % 1000000000;
		}
	}
	cout << dp[n];
	return 0;
}

이렇게 일차원 배열로도 풀 수 있다.

여기에서 쓰는 점화식은 더 간단하다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다. 그런데 이것을 일차원 배열로 바꾼 코드이다.

이 방법으로 제출하니 0ms가 걸렸다.

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

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

int main() {
	int n;
	cin >> n;
	vector<int> v(3);
	vector<int> minDp(3);
	vector<int> maxDp(3);
	for (int i = 0; i < 3; i++) {
		cin >> v[i];
		minDp[i] = v[i];
		maxDp[i] = v[i];
	}
	
	for (int i = 1; i < n; i++) {
		cin >> v[0] >> v[1] >> v[2];
		int a1 = minDp[0];
		int b1 = minDp[1];
		int c1 = minDp[2];
		int a2 = maxDp[0];
		int b2 = maxDp[1];
		int c2 = maxDp[2];
		minDp[0] = (min(a1 + v[0], b1 + v[0]));
		minDp[1] = (min(min(a1 + v[1], b1 + v[1]), c1 + v[1]));
		minDp[2] = (min(b1 + v[2], c1 + v[2]));
		maxDp[0] = (max(a2 + v[0], b2 + v[0]));
		maxDp[1] = (max(max(a2 + v[1], b2 + v[1]), c2 + v[1]));
		maxDp[2] = (max(b2 + v[2], c2 + v[2]));
	}
	
	int minSum = min(min(minDp[0], minDp[1]), minDp[2]);
	int maxSum = max(max(maxDp[0], maxDp[1]), maxDp[2]);
	cout << maxSum << " " << minSum;
	return 0;
}

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

LIS(Longest Increasing Sequence)를 구하고 N에서 LIS를 빼주면 된다.

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

int main() {
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<int> dp(n);
	dp[0] = 1;
	int lis = 0;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && v[j] < v[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > lis)
			lis = dp[i];
	}
	cout << n - lis;
	return 0;
}

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

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n, cost;
		cin >> n;
		vector<int> coin(n);
		for (int i = 0; i < n; i++) {
			cin >> coin[i];
		}
		cin >> cost;
		vector<vector<int>> dp(n, vector<int>(cost + 1));
		for (int i = 0; i <= cost; i++) {
			if (i % coin[0] == 0)
				dp[0][i] = 1;
		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= cost; j++) {
				for (int c = 0; c <= j; c += coin[i]) {
						dp[i][j] += dp[i - 1][j - c];	
				}
			}
		}
		cout << dp[n - 1][cost] << '\n';
	}
	return 0;
}

C++에서 배열을 선언하고 초기화를 해주지 않으면 배열은 쓰레기 값으로 채워져있다.

아래의 코드를 실행해보면

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 쓰레기 값으로 채워져있는 것을 볼 수 있다.

따라서 배열을 선언하면 초기화를 꼭 해주는 것이 좋다.

배열 arr의 원소를 모두 0으로 초기화하고 싶다면

int arr[5] = {};

이렇게 해주면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = {};
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

배열 arr의 원소 5개가 모두 0으로 초기화된 것을 볼 수 있다.

만약에 배열의 0번째 원소만 10으로 초기화하고 나머지는 다 0으로 초기화하고 싶다면?

int arr[5] = { 10 };

또는

int arr[5] = { 10, };

이렇게 해주면 된다.

여기에서 주의할 점은 위 코드는 모든 원소를 10으로 초기화하는 것이 아니라 첫 번째 원소만 10으로 초기화하는 것이라는 것이다. 이 부분을 잘못 알고 있기 쉬우므로 꼭 기억하자.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 10 };
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

첫 번째 원소만 10으로 초기화된 것을 볼 수 있다.

첫 번째 원소를 10으로, 두 번째 원소를 3으로, 나머지는 0으로 초기화하고 싶다면

int arr[5] = { 10, 3 }

이렇게 하면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 10, 3 };
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

첫 번째 원소가 10, 두 번째 원소가 3으로, 나머지는 0으로 초기화 된 것을 볼 수 있다.

그런데 만약 모든 원소를 0이 아닌 특정 값으로 초기화하고 싶다면?

배열의 크기가 5 정도로 작다면

int arr[5] = { 10, 10, 10, 10, 10 }

이렇게 직접 초기화 해줄 수 있지만 배열의 크기가 1000, 10000, 100000 등 큰 수라면 이렇게 직접 초기화 하기에는 무리가 있다.

그럴 때 일반적으로 이렇게 반복문으로 초기화를 시킨다.

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		arr[i] = 10;
	}
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 10으로 초기화된 것을 볼 수 있다.

하지만 함수를 이용해서 더 편리하게 초기화할 수 있는 방법이 있다.

바로 <algorithm> 헤더에 있는 fill 함수이다.

http://www.cplusplus.com/reference/algorithm/fill/

fill 함수를 사용하려면 일단 <algorithm> 헤더를 포함해줘야 한다.

사용 방법은

fill(초기화 시키고 싶은 부분의 시작 주소, 초기화시키고 싶은 부분의 끝 주소, 초기화할 값);

이렇게 사용하면 된다.

배열이라면

fill(arr, arr + 5, 10);

이렇게 하면 되고

벡터라면

fill(v.begin(), v.end(), 10);

이렇게 해주면 된다.

아래 코드를 실행하면

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

int main() {
	int arr[5];
	fill(arr, arr + 5, 10);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

이렇게 모든 원소가 10으로 초기화되어 있는 것을 볼 수 있다.

즉

for(int i = 0; i < 5; i++) {
	arr[i] = 10;
}

이 for문을 사용한 코드와

fill(arr, arr + 5, 10);

이 한 줄은 같은 역할을 한다.

fill(arr, arr + 2, 10);
fill(arr + 2, arr + 5, 20);

이렇게 부분 부분씩 초기화시켜줄 수도 있다.

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

int main() {
	int arr[5];
	fill(arr, arr + 2, 10);
	fill(arr + 2, arr + 5, 20);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

전체 코드이다.

벡터도 마찬가지이다.

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

int main() {
	vector<int> v(5);
	fill(v.begin(), v.end(), 10);
	for (int i = 0; i < 5; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	return 0;
}

이 코드를 실행하면

이렇게 10으로 초기화된다.

하지만 벡터는 굳이 fill 함수를 안 쓰고

vector<int> v(5, 10);

이렇게 선언과 동시에 10으로 초기화하는 것이 더 편할 것이다.

(벡터 초기화 및 사용법↓)

https://breakcoding.tistory.com/139

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

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

vector<vector<int>> v;
vector<vector<int>> dp;
int n;

int dfs(int i, int j) {
	bool flag = false;
	if (dp[i][j] != 0) return dp[i][j];
	int maximum = 0;
	if (i + 1 < n && v[i][j] < v[i + 1][j]) {
		int temp = 1 + dfs(i + 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (i - 1 >= 0 && v[i][j] < v[i - 1][j]) {
		int temp = 1 + dfs(i - 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j + 1 < n && v[i][j] < v[i][j + 1]) {
		int temp = 1 + dfs(i, j + 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j - 1 >= 0 && v[i][j] < v[i][j - 1]) {
		int temp = 1 + dfs(i, j - 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (!flag) {
		dp[i][j] = 1;
	}
	return dp[i][j];
}

int main() {
	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];
		}
	}
	int maxDp = 0;
	dp = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] > maxDp) maxDp = dp[i][j];
		}
	}
	cout << maxDp;
	return 0;
}

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

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

int main() {
	int n;
	cin >> n;
	int ring;
	cin >> ring;
	vector<int> v(n - 1);
	for (int i = 0; i < n - 1; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < n - 1; i++) {
		int gcd;
		for (int j = min(v[i], ring); j >= 1; j--) {
			if (v[i] % j == 0 && ring % j == 0) {
				gcd = j;
				break;
			}
		}
		cout << ring / gcd << "/" << v[i] / gcd << '\n';
	}
	return 0;
}