Mohand's code block

링크

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;
}