아인스트라세의 SW 블로그

때는 백준 1920번 문제를 풀 때 겪은 일이었습니다.

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

문제를 보자 마자 C++ STL에 있는 unordered_set을 이용하면 풀리겠거니, 하고 풀었더니 시간초과가 났습니다.

그래서 풀이를 찾아보니 바이너리 서치를 이용해서 풀더군요. 그래서 C++ STL Algorithm 헤더에 있는 binary_search를 이용해서 푸니 똑같이 시간초과가 났습니다.

예전에 C++ STL에 있는 upper_bound와 lower_bound가 O(lgN)이 아니라 선형 시간복잡도를 갖는다는 이야기를 들은적이 있습니다.(틀린 이야기라라고 합니다.) (binary_search는 lower_bound를 이용해서 구현된 것으로 알고 있습니다.) 그래서 vector container에 대한 binary_search를 커스텀으로 구현한 뒤 다시 풀어보니 또 시간초과...

그래서 binary_search를 잘못 구현한 것인가 싶어서 vector<int>::iterator를 이용하지 않고, int형 인덱스로 다시 구현해도 시간초과가 났습니다. 그래서 미뤄두고 있다가 최근 코드포스에서 비슷한 현상을 겪었죠.

http://codeforces.com/contest/892/problem/B

C++로 구현하니 시간초과가 나는데 요즘 공부하는 파이썬으로 짜니 오히려 정답처리가 되는... 그래서 대회가 끝나고 C++로 정답판정을 받은 사람들의 코드를 보니 다음과 같은 코드가 눈에 띄었습니다

 
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin, cout이 scanf, printf에 비해서 속도가 많이 느리다고 하더군요. std::endl보다 '\n'가 훨씬 빠르다는 이야기도 많이 들었지만, 실제 프로그래밍 문제를 풀 때 이러한 것 때문에 애로사항을 겪은적이 없었기 때문에 크게 신경쓰지는 않았었는데 이렇게 겪게 되었습니다.

따지고 보면 입출력 속도 때문에 시간초과가 난 문제 둘 다 최대 입력값 개수가 100만개 이상이었습니다.

찾아보니 여러가지가 자료들이 많았는데 결론적으로는 편리함 때문에 cin, cout을 쓰기 보다는 scanf와 printf를 사용하면 해결될 문제입니다. 그리고 좀 더 빠르게 하겠다면 글자 하나씩 입출력하는 함수들이 더 빠릅니다.(getchar, putchar 등등)

cin, cout을 사용하더라도 sync_with_stdio(false)로 속도를 가속할 수는 있지만, 이는 정공법적인게 아니라 일종의 편법같은 방식이고, 이 방식도 통하지 않는 경우가 있습니다.(그래도 scanf, printf속도로만 정답이 나오는 경우) 그리고 sync_with_stdio를 false로 준 경우, scanf, printf와 같은 C 표준 입출력 함수와 cout, cin같은 C++ 입출력 객체를 섞어 사용하는 경우 오답처리가 날 수 있습니다. 입출력이 코드 작성자가 의도하지 않은 순서로 나타난다던가 하는 일이 일어날 수 있다는 것이죠. 특히 멀티 쓰레드 환경일 경우 sync 값이 true일 때는 Thread safe라서 예상치 못한 값이 나오지 않지만, false를 시킬 경우 Thread unsafe해지기 때문에 예상치 못한 값이 나타날 수 있습니다.

그러므로 굳이 sync_with_stdio(false); 를 이용해서  C++ 입출력 객채를 가속시켜서 사용할 것이라면, scanf와 printf와 섞어서 사용하지 말 것이며, 싱글 쓰레드 환경에서만 사용(알고리즘 문제만 풀 때는 무조건 싱글스레드이므로 상관없지만 실무에선 쓰지말것)하고, 그래도 시간초과가 난다면 C 표준입출력 함수들을 사용하는 것을 추천하는 바입니다.

더 참고할 수 있는 자료들

알고스팟 - 언어별 input method 비교

https://algospot.com/forum/read/2496/

백준저지 -  1920번 문제 질문

https://www.acmicpc.net/board/view/9022

cpp reference - sync_with_stdio

http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

stackoverflow - sync_with_stdio, cout.tie등에 대한 질문에 대한 답변

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

이번 코드포스 콘테스트는 Division 2만 개최되었다. Div1에 해당하는 사람도 참가는 가능하지만, competition은 Div2에 해당하는 사람만 이루어졌다.

풀지 못한 문제도 대회가 끝난 후 읽어보고 Editorial을 읽으면서 계속 공부하려고 해 보았는데, 오랜만에 제대로 공부하는 느낌이 드는 대회였다.

A번 문제

http://codeforces.com/contest/869/problem/A

하나하나 실제로 시뮬레이션 하면 된다. 이미 한번 나왔던 수 인지는 unordered_set으로 확인했다. 그런데 대회가 끝난 후 editorial을 읽어보니, 수학적 증명에 따라서 무조건 짝수개가 나온다고 한다. xor의 수학적 특징때문이다. A xor B = C라면 B xor C = A이라는 뭐 이런 특징때문이라고 한다. A번 문제 쉽다고 생각해서 그냥 풀어버리고 나왔는데, 생각보다 신박한 부분이 있다.

문제가 xi와 yi를 xor한 값이, 2n개의 배열, x1, x2, x3... xn, y1, y2, ... yn의 총 2n개의 배열 안에 들어있으면 카운트를 센다는 것인데, xor한 값이 2n보다 작은지라고 문제를 잘못 이해해서 hack 당한 사람들이 몇 명 있었다.

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

int arr[2002][2];
unordered_set<int> s;
int main() {
	int n;
	cin >> n;
	for (int i=0;i < 2; i ++) {
		for (int j=0; j< n; j++) {
			cin >> arr[j][i];
			s.insert(arr[j][i]);
		}
	}
	
	bool even = true;
	for (int i=0; i < n; i++) {
		for (int j=0; j < n; j++) {
			auto& xi = arr[i][0];
			auto& yi = arr[j][1];
			int val = (xi ^ yi);
			if (s.find(val) != s.end()) {
				even = !even;
			}
		}
	}
	
	cout << (even ? "Karen" : "Koyomi") << endl;
}

B번 문제

http://codeforces.com/contest/869/problem/B

죄다 곱해버리면 될 것 같은데, 수가 커서 TLE가 나온다. 그런데 여기서 어차피 마지막 decimal digit을 구할 것이므로, 1의자리수만 고려하면 될 것 같다. 10번마다 주기적으로 회전하므로, 이를 고려하면 된다는 것! 그런데 또 보면 10번을 돈다는 것은, 0이 포함되므로 그냥 0이 나온다는 것이다. 따라서 a와 b의 차이값이 10이상이면 무조건 0이다.    

코드를 잘못 내서 hack 당했다.. 중간에 주석처리한 부분을 주석을 해제하면 Hack당한 코드가 된다. 주석 처리해서 지금은 Accept 판정을 받은 코드이다.

#include <iostream>

typedef long long ll;
using namespace std;

int main() {
	ll a, b, ans;
	cin >> a >> b;
	if (b-a >= 10) {
		cout << 0 << endl;
		return 0;
	}
	ans = 1;
	// b %= 10;
	// a %= 10;
	for (ll k = b; k > a; k--) {
		ans *= k;
		ans %= 10;
	}
	cout << ans << endl;
}

C번 문제

http://codeforces.com/contest/869/problem/C

섬 a,b,c에 대하여, a-b, b-c, c-a 연결 시 다리 개수는 모두 독립적이다. a-b 연결 다리 개수는 다리가 0개일때, 1개일때, ... n개일때 모두 고려해서 더하면 된다. n개는 min(a,b) 개이며, a와 b의 섬 개수 중 최소값이다. 다리가 i개 일때는 aCi * bCi * i!의 개수가 나오게 된다. 연결에 참여할 섬들을 고른 뒤 어떻게 연결할 것인지를 곱한 값이다. 팩토리얼과 이항계수는 dp로 구현했다. 메모리가 아슬아슬하다.

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353

typedef long long ll;

int dp[5001][5001];
int bicof[5001][5001];
int facto[5001];

ll get_facto(int n) {
	if (n <= 1) {
		return 1;
	}
	if (facto[n]) return facto[n];
	ll ret = 1;
	return facto[n] = (n * get_facto(n-1)) % MOD;
}

ll pascal(int n, int r) {
	if (n==r) return 1;
	if (n==0 || r==0) return 1;
	if (bicof[n][r]) return bicof[n][r];
	return bicof[n][r] = ((ll)pascal(n-1, r) + (ll)pascal(n-1, r-1)) % MOD;
}
ll get(int a, int b) {
	if (dp[a][b]) return dp[a][b];
	ll ret = 1;
	int limit = min(a, b);
	for (int i=1; i <= limit; i++) {
		ret += (((pascal(a, i) * pascal(b, i)) % MOD) * get_facto(i)) % MOD;
		ret %= MOD;
	}
	return dp[a][b] = ret;
}
int main() {
	int a, b, c;
	dp[1][1] = 2;
	cin >> a >> b >> c;
	ll ans = 1;
	ans *= get(a,b);
	ans %= MOD;
	ans *= get(b,c);
	ans %= MOD;
	ans *= get(c,a);
	ans %= MOD;
	cout << ans << endl;
}

D번 문제

http://codeforces.com/contest/869/problem/D

실제 대회당시 맞춘사람이 5명인가 밖에 안된다. 등록한사람이 7천명이 가까이되는데 말이다. 출제자가 D번문제와 E번 문제를 바꾸는게 나았을거라고 인정했다. 맞춘 사람 풀이를 보니, 실제로 가능한 경로를 모두 세되, 중복일 경우 최적화를 잘 적용한 것으로 보인다. 나중에 다시 도전해볼 예정이다.

E번 문제

http://codeforces.com/contest/869/problem/E

뭔가 풀 수 있을 것 같은데 못 풀 것 같은 문제이다. 2차원 세그먼트 트리나 쿼드 트리를 사용해야 한다고 한다. 세그먼트 트리와 쿼드 트리를 공부한 뒤 다시 도전할 예정이다.

블로그에 소스코드를 넣어야 하는 경우가 있습니다. 이러할 경우 코드 하이라이터를 사용해주면 좋은데, 그 중에서도 꽤나 나이스한 디자인을 보여주는 prismjs를 티스토리 블로그에 적용해보도록 하겠습니다.

prismjs 홈페이지 주소입니다.

http://prismjs.com/index.html

공식 홈페이지에 가서 DOWNLOAD라는 버튼을 누릅니다.

다운로드 페이지로 가면, 필요한 구성요소를 직접 골라서 다운로드를 받을 수 있습니다. Compresion Level에는 개발버전과 Minified 버전이 있는데, 개발 버전은 prism.js의 소스코드를 변경해서 자신의 입맛대로 만들어 쓸 경우 필요한 버전입니다. 저희는 그냥 있는 버전을 사용하기만 할 것이므로 Minified version을 선택합니다.

테마의 경우 오른쪽에 있는 원들을 눌러서 하단에서 실제 적용된 테마의 모습을 확인할 수 있습니다. 저 같은 경우에는 Okaidia 테마가 마음에 드므로 해당 테마를 선택했습니다.

그 외에도 하이라이팅을 지원하는 언어들과, 다양한 플러그인들을 제공합니다. 저는 기본 제공하는 언어 외에 C++ 언어를 추가하였고, 플러그인은 줄 번호를 표시해주는 플러그인을 선택했습니다.

하단으로 내려가면 적용될 테마의 모습이 보입니다. 다운로드 JS와 다운로드 CSS를 한번씩 눌러서 prism.js와 prism.css 파일을 다운로드 받습니다.

그리고 티스토리 관리 페이지로 가서 꾸미기 탭의 HTML/CSS 편집으로 들어갑니다.

우측 상단에 보이는 파일 업로드를 누릅니다.

여기에 추가 버튼을 눌러서 prism.js 파일과 prism.css 파일을 업로드 해 줍니다.

파일들이 추가된 모습들이 보입니다. 이 파일들이 추가된 경로를 확인해놓습니다. 저의 경우에는 images/prism.js와 images/script.js 의 경로에 추가되었습니다.

그리고 다시 HTML을 눌러서 태그를 추가해야 합니다.

head 닫는 태그, 즉 </head> 바로 위에 위와 같이 추가해줍니다.

<script src="./images/prism.js"></script>
<link rel="stylesheet" href="./images/prism.css">

그리고 저장 버튼을 눌러서 적용해 주면 됩니다.

이후 코드 하이라이팅이 필요한 경우 에디터에서 HTML 모드를 활성화 한 뒤 다음 태그를 입력해주면 됩니다.

<pre class="line-numbers language-cpp"> 
<code class="language-cpp">
//여기에 소스코드를 작성하시면 됩니다.
</code>
</pre>

HTML 모드에서 코드를 작성하려고 하면 <나 >와 같은 문자들을 또 수동으로 &gt; &lt; 등으로 이스케이프 처리해주어야 합니다. 따라서 추천하는 방법은 HTML모드에서 pre와 code 태그만 작성한 뒤, 위지윅 모드에서 소스코드를 붙여넣기하는 방법입니다.