Mohand's code block

링크

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

해설

배열 내에서 두 개의 포인터를 가지고 이동하면 되는 문제입니다.

연속된 합이 S 이상인 것들 중 가장 길이가 짧은 것이니 오른쪽 포인터를 움직이다가

S이상이 되면 길이 체크 후 다시 왼쪽 포인터를 움직여서 줄이면 됩니다.

1. 현재 부분합이 S이상 - 더이상 늘려봤자 의미가 없으므로 다시 줄여야 함

 길이 짧은 것으로 교체

 합에서 TABLE[left] 빼기

 left++

2. 현재 부분합이 S 미만 - S이상이 되도록 늘려야 함

 right++

 합에 TABLE[right] 더하기

이렇게 두 포인터를 이용해서 부분합이 S이상인 것들 중 최소 길이만 다 확인해주면 됩니다.

코드

#include <iostream>
using namespace std;

int N, S, TABLE[100000];

int min(int _a, int _b) {
	if (_a < _b)
		return _a;
	return _b;
}

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

	cin >> N >> S;

	for (int i = 0; i < N; ++i)
		cin >> TABLE[i];
	
	int left = 0, right = 0, now = TABLE[0], ans = 100001;

	while (right != N) {
		if (now < S) {
			++right;
			now += TABLE[right];
		}
		else {
			ans = min(ans, right - left + 1);
			now -= TABLE[left];
			++left;
		}
	}

	cout << (ans == 100001 ? 0 : ans);

	return 0;
}

링크

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

해설

오큰수란 오른쪽의 수 중에 현재 수보다 크면서 가장 왼쪽에 있는 수를 말합니다.

우선 이 문제를 풀기위해선 스택을 사용해야 합니다.

각 숫자들을 모두 오른쪽 숫자와 비교해가면서 하면 최대 O(N ^ 2) 가 걸리므로 비효율적입니다.

그래서 스택을 이용해서 스택에는 현재수의 오큰수 후보들이 들어있고

오른쪽에서 왼쪽으로 가면서 스택을 pop push 합니다.

1. 자신보다 작거나 같으면 pop합니다.

2. 자신보다 크면 멈추고 해당 숫자가 오큰수가 됩니다.

3. 만약 스택이 비었을 경우 오큰수가 없는 것이므로 -1 입니다.

4. 최종적으로 스택이 자신을 push합니다.

위의 조건에 따라 오큰수가 정해지게 됩니다.

왜 이런 조건들이 되는지 설명해드리겠습니다.

1. 자신보다 작거나 같으면 pop합니다.

우선 x번째 수 보다 작거나 같으면 왼쪽의 x-1, x-2, ... 번째 수 들은 오큰수를 구할 때 어차피 x번째 수보다

작은 수이므로 x번째 수뿐만 아니라 왼쪽의 x-1, x-2, ... 번째 수 들의 오큰수 후보가 될 수 없습니다.

고로 pop합니다.

위의 그림과 같이 7과 8 사이의 2 3 1 4 는 더 이상 쓸모가 없습니다.

왼쪽에서 7보다 작은 수가 나올 경우 7이 오큰수 후보가 될 것이고

7보다 큰 수가 나오면 7의 오큰수인 즉 8과 그 뒤의 수가 오큰수가 되기 때문입니다.

2. 자신보다 크면 멈추고 해당 숫자가 오큰수가 됩니다.

자신보다 큰 수를 찾으면 그게 오큰수 이므로 멈추고 오큰수가 됩니다.

더 뒤에 있는 수들은 굳이 작은지 비교해서 빼내지 않습니다.

왜냐면 나중에 필요할 때 검사하면 되지 굳이 미리 다 검사해둘 필요는 없습니다.

3. 만약 스택이 비었을 경우 오큰수가 없는 것이므로 -1 입니다.

스택이 비었다는 것은 스택 내의 모든 수가 현재수보다 작다는 것이므로 오큰수는 없습니다.

4. 최종적으로 스택이 자신을 push합니다.

스택에서 본인보다 작거나 같은 수를 모두 삭제했으므로 본인이 push 되어 오큰수 후보가 됩니다.

백준 예시를 사용해서 풀어보겠습니다.

3 5 2 7

맨 오른쪽부터 순서대로 스택에 쌓아보겠습니다.

now : 7

스택이 비어있고 오큰수는 -1

현재수를 push합니다.

NGE(4) = -1

now : 2

현재수보다 큰 수를 찾았으므로 멈춥니다

현재수를 push합니다.

NGE(3) = 7

now : 5

2는 현재수보다 작으므로 pop

7은 현재수보다 크므로 멈춥니다.

현재수를 push합니다.

NGE(2) = 7

now : 3

5는 현재수보다 크므로 멈춥니다.

현재수를 push합니다.

NGE(1) = 5

코드

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

stack <int> STACK;
int N;
int NUM[1000000], TABLE[1000000];

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

	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> NUM[i];

	for (int i = N - 1; i >= 0; --i) {
		int now = NUM[i];
		while (!STACK.empty()) {
			if (STACK.top() <= now)
				STACK.pop();
			else
				break;
		}
		if (STACK.empty())
			TABLE[i] = -1;
		else
			TABLE[i] = STACK.top();
		STACK.push(now);
	}
	
	for (int i = 0; i < N; ++i) {
		cout << TABLE[i] << " ";
	}

	return 0;
}

링크

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

해설

DFS를 아신다면 간단한 문제입니다.

원래 이문제를 풀 때는 스택을 사용해야 하지만 딱히 경로를 저장해야 하는 문제는 아니라서

bool can_go[26];

을 이용해서 이미 지나간 알파벳인지 아닌지만 검사해서 DFS 를 실시하면 됩니다.

코드

#include <iostream>
using namespace std;

char table[20][20];

int R, C, MAX = 1, NOW = 1;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

bool can_go[26];

void DFS(int _x, int _y) {

	if (NOW > MAX)
		MAX = NOW;
	for (int i = 0; i < 4; ++i) {
		int nx = dx[i] + _x;
		int ny = dy[i] + _y;
		if (0 <= nx && nx < C && 0 <= ny && ny < R) {
			int alp = table[ny][nx] - 'A';
			if (can_go[alp]) {
				can_go[alp] = false;
				++NOW;
				DFS(nx, ny);
				--NOW;
				can_go[alp] = true;
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	char in[21];
	fill_n(can_go, 26, true);

	cin >> R >> C;
	for (int i = 0; i < R; ++i) {
		cin >> in;
		for (int j = 0; j < C; ++j) {
			table[i][j] = in[j];
		}
	}
	can_go[table[0][0] - 'A'] = false;
	DFS(0, 0);
	cout << MAX;
	return 0;
}

링크

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

해설

DP 중 Alignment 에 관한 문제이다.

당연히 문자열을 하나하나 다 대보면서 하면 시간제한이 걸린다.

백준 문제의 예시를 그대로 사용해보겠다.

ACAYKP 와 CAPCAK 인데 이걸 2차원 표로 만들어보면

위와 같은 표가 만들어지게 되는데

각 칸이 두 문자열의 해당 칸까지 만들 수 있는 LCS의 길이라고 생각하면 된다.

예를 들어 (1, 1) 의 위치는 당연히 A 와 C 만으로는 만들 수가 없으니 0이다.

그러면 (x, y) 의 LCS는 어떻게 될까?

우선 ( x, y ) 의 점화식을 써보면 아래와 같다.

우선 점화식대로 표를 채워보면

위와 같이 표가 만들어지게 된다.

그러면 왜 위와 같은 점화식이 될까?

위의 점화식은 top - down 방식인데 쉬운 이해를 위해 down - top 방식부터 생각해보겠다.

down - top 방식으로 생각해보면 만약 특정 (x, y) 의 값이 a 라면 그 뒤로는 어떤 문자열이 오던 최소한 a 이상일 것이다.

왜냐하면 이미 (x, y) 일 때 LCS 가 a 이므로 a값이 더 커지면 커졌지 작아지지는 않을 것이다.

그러면 이 LCS의 값이 언제 증가하는가? 바로 x 번째와 y 번째가 같을 경우에만 증가할 수 있다.

이제 top - down 방식으로 반대로 생각해보면 현재의 ( x, y )는 아무리 값이 작아도

( x - 1 , y ) 와 ( x , y - 1 ) 의 값 이상일 것이다. 왜냐면 down - top 방식에서 이미 증명되었기 때문이다.

그러면 LCS의 값은 왜 좌 대각선의 값에서만 +1 시키는가 하면

만약 x번째와 y번째가 같으면 LCS가 1 증가되는데 이 x번째 문자열과 y번째 문자열이 재사용되면 안 될 것이다.

바로 그렇기 때문에 좌대각의 값에서밖에 +1 을 못 시키는 것이다.

위의 해설이 이해가 되지 않는다면 dp alignment 에 대해 찾아보길 바란다.

해당 해설은 dp alignment 를 이미 알고 있다는 전재하에 적힌 해설이기 때문에 이해가 어려울 수 있다.

dp alignment 를 공부해보면 gap, match, mismatch 이 3가지 경우가 나오게 되는데

이 문제같은 경우 gap 과 mismatch 에 penalty 가 전혀 없는 문제라고 볼 수 있다.

코드

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

int table[1000][1000];
string A, B;

int max(int _a, int _b) {
	return _a > _b ? _a : _b;
}

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

	cin >> A >> B;
	
	if (A[0] == B[0])
		table[0][0] = 1;
	else
		table[0][0] = 0;

	for (int i = 1; i < A.size(); ++i)
		table[0][i] = A[i] == B[0] ? 1 : table[0][i-1];
	for (int i = 1; i < B.size(); ++i)
		table[i][0] = A[0] == B[i] ? 1 : table[i-1][0];

	for (int i = 1; i < B.size(); ++i) {
		for (int j = 1; j < A.size(); ++j) {
			if (A[j] == B[i])
				table[i][j] = table[i - 1][j - 1] + 1;
			else
				table[i][j] = max(table[i][j - 1], table[i - 1][j]);
		}
	}

	cout << table[B.size() - 1][A.size() - 1];
	

	return 0;
}

링크

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

해설

이 문제는 그래프 문제이고, 가중치가 없으므로 BFS를 이용해서 푸는 문제입니다.

다만 평범한 BFS 와는 조금 다르게 벽을 부수기를 실행한 그래프와 하지않은 그래프 두가지를 사용해야합니다.

그래서 queue 에도 현제 좌표 뿐만 아니라 벽을 부술 수 있는지 없는지 또한 같이 저장합니다.

table[ x위치 ][ y위치 ][ 벽부술수있는가 ]

로 table 을 만들고 시작은 table[0][0][1] 에서 시작합니다.

그후 매번 queue 에서 현제위치를 꺼내와서

1. 다음 위치가 배열을 안 벗어나는가?

2-1. 다음 위치가 아직 가지 않은 지점이면 그냥 queue 에 넣고 갑니다.

2-2. 벽이면 벽부수기를 실행하고 table[][][0] 으로 내려갑니다.

      (당연히 벽부수기를 이미 했다면 못갑니다)

계속 반복하다가 N-1 , M-1 지점에 도착하면 멈춥니다.

아래 코드에서는

-1 = 벽

0 = 아직 지나가지않은곳

1~ = 이미 지나간곳

으로 사용했습니다.

이렇게 코드를 짜면 벽을 부수지 않은 그래프, 벽을 부순 그래프 각자대로 최선을 다해 가다가

먼저 도착하면 끝이나겠죠?

코드

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

typedef struct _state {
	int x, y;
	bool bomb;
}state;

int N, M, table[1000][1000][2];
int dx[4] = { 1, -1, 0, 0 },
	dy[4] = { 0, 0, 1, -1 };

bool can_go(int _x, int _y) {
	return 0 <= _x && _x < N && 0 <= _y && _y < M;
}

int bfs() {

	table[0][0][1] = 1;
	queue<state> que;
	que.push({ 0, 0, true });

	while (!que.empty()) {
		state now = que.front();
		if (now.x == N - 1 && now.y == M - 1)
			return table[now.x][now.y][now.bomb];
		que.pop();
		int bomb = now.bomb;

		for (int i = 0; i < 4; ++i) {
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			
			if (can_go(nx, ny)) {
				if (table[nx][ny][bomb] == 0) {
					table[nx][ny][bomb] = table[now.x][now.y][bomb] + 1;
					que.push({ nx, ny, now.bomb });
				}
				else if (table[nx][ny][1] == -1 && now.bomb) {
					table[nx][ny][0] = table[now.x][now.y][1] + 1;
					que.push({ nx, ny, false });
				}
			}
		}

	}
	
	return -1;
}

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

	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			char ch;
			cin >> ch;
			int val;
			if (ch == '1')
				val = -1;
			else
				val = 0;
			table[i][j][0] = val;
			table[i][j][1] = val;
		}
	}
	cout << bfs();
	return 0;
}

백준 문제를 풀다가 알게 된 사실입니다.

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

해당 1753 문제를 풀던 도중이었죠.

해당 문제는 edge 가 최대 300000 개로 다른 문제들에 비해 입출력이 상당히 많은 문제입니다.

대충 코드를 작성하고 제출을 했는데 시간 초과가 발생했습니다.

그래서 내가 뭔가 알고리즘을 잘못 짠 건가 해서 구글링을 하던 중 코드가 구조상 거의 동일한데

저 코드는 되고 내 코드는 안 되는 이유를 찾았습니다.

결론부터 말하자면 바로 3줄의 차이였습니다.

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

우선 C/C++ 의 여러 가지 입출력의 수행 시간 차이를 알아보겠습니다.

위의 사진을 보면 getchar(*) 가 0.39초로 가장 빠르고

그다음으로 흔히 사용하는 scanf 가 0.798 ,  cin이 2.051로 2배가 넘는 속도 차이를  보여주고 있습니다.

이 느린 cin에 sync_with_stdio 를 사용하면 scanf 와 비슷한 속도를 보여줍니다.

그러면 왜 이런 현상이 일어나는 걸까요?

우선 C++는 기본적으로 입출력 시 자신만의 표준 스트림을 사용하지 않습니다.

그럼 어떻게 하느냐? 바로 C의 표준스트림을 사용합니다.

C++ 의 표준 스트림 cin, cout 등과 C의 표준스트림 stdin, stdout 이 다 연결돼있다는 소립니다.

그래서 cin 과 printf 를 혼합해서 사용해도 입출력의 순서가 보장되는 것입니다.

하지만 그 동기화를 끊어버리면? 입출력의 순서가 보장되지 않는 대신 속도가 빨라집니다.

또한 C++ 의 입출력은 쓰레드 안전성이 보장되지만 동기화를 끊어버리면 보장되지 않습니다.

아래의 두 코드는 동기화를 한 경우와 하지 않은 경우의 차이입니다.

ubuntu 환경에서 테스트하였고 (비주얼스튜디오에서는 다르게 나올 수 있습니다!!)

두 코드의 차이점은 동기화의 차이밖에 없습니다.

1. 동기화를 풀지 않을 경우

#include <iostream>
using namespace std;

int main()
{	
	for(int i = 0; i < 10; ++i) {
		cout << "cout\n";
		printf("printf\n");
	}
}

2. 동기화를 풀 경우

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);

	for (int i = 0; i < 10; ++i) {
		cout << "cout\n";
		printf("printf\n");
	}
}

위와 같이 같은 코드인데도 출력이 다릅니다.

다음으로

cin.tie(NULL);
cout.tie(NULL);

이 두줄은 cin 과 cout 의 묶음을 풀어버리는 코드입니다.

기본적으로 cin 과 cout은 묶여있고 묶여있으면 스트림이 각 입출력을 하기 전에 자동으로 버퍼를 비워줍니다.

코드를 예로 들어보겠습니다.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	int num;
	cout << "enter num : ";
	cin >> num;
}

위의 코드가 묶음을 풀었을 경우에 "enter num : " 이 출력되기도 전에 cin이 먼저 실행될 수도 있다는 것이다.

추가적으로 개행 시 보통 endl 을 많이 사용하게 되는데 이 endl 의 경우 버퍼를 비워주는 역할도 수행하므로 "\n"을 사용하는 것보다 속도가 느립니다. 따라서 알고리즘을 할 때는 극한의 속도(?)를 위해 "\n" 사용을 생활화합시다.

결론

보통 알고리즘 문제를 풀 경우 싱글 쓰레드 환경이므로 sync_with_stdio(false) 를 해도 cin, scanf  cout, printf 를 섞어 사용하지 않는 이상 결과에 영향이 없고 속도가 매우 빨라진다.

cin.tie(NULL) cout.tie(NULL) 또한 알고리즘 문제는 화면에 보이는 순서가 크게 중요하지 않으므로 크게 지장이 없다.

요약

1. sync_with_stdio 사용할 거면 cout 과 printf 혼용 금지와 싱글쓰레드에서만 사용

2. cin.tie(NULL) cin.tie(NULL) 시에 cin cout 을 빠르게 혼용 시 순서가 뒤죽박죽