Mohand's code block

링크

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

해설

반드시 포함되는 anta tica 에 대한 예외처리를 안 하면 시간 초과가 납니다.

혹시 시관 초과가 나서 보러 오셨다면 위의 예외처리를 해보시고 그래도 안되면 보시기 바랍니다.

간단한 백트래킹 문제입니다.

다만 반드시 포함되는 a c i n t 이 다섯 글자에 대한 예외처리만 하고 백트래킹을 하면 됩니다.

해결방법은 다음과 같습니다.

1. a c i n t 가 반드시 포함되어야 하므로 K 가 5 미만이면 0개입니다.

2. 5 이상이면 체크리스트에 a c i n t 를 입력하고 배울 수 있는 개수도 5개 줄입니다.

3. 각 알파벳에 대해 백트래킹을 하면서 브루트포스 알고리즘을 적용시킵니다.

저는 시간을 조금이라도 더 줄이려고 비트 마스킹을 이용해서 풀었습니다.

코드에 대한 약간의 설명을 드리자면

MASK : 이제껏 배운 알파벳들의 위치만 0 입니다.

SELECT : 단어들 중 한 번이라도 나온 알파벳들만 1입니다. (즉 배울 필요가 없는 걸 걸러 내는 용도)

TABLE은 기본적으로 모두 0으로 초기화돼있고 각 단어별로 해당 알파벳을 배워야 할 경우 해당 자리만 1로 바뀝니다.

DFS를 실시하기 전에 a c i n t 을 먼저 다 배우고 실시하는 조건이므로 MASK 에 0 처리

그리고 SELECT 에 이미 배웠으므로 0으로 빼줍니다.

그 후 백트래킹을 더 이상 할 수 없다고 판단되면 ( 더 배울 수 있는 단어의 수가 0 이거나 알파벳 끝까지 다 배운 경우)

각 테이블의 단어들과 지금까지 배운 알파벳 (MASK) 를 and 연산 후 ! 하면 읽을 수 있는지 나옵니다.

코드

#include <iostream>
using namespace std;

int N, K, BEST = 0;
unsigned int MASK = -1, SELECT = 0;
unsigned int TABLE[50] = { 0, };

void DFS(int _num) {
	for (; _num < 26; ++_num) {
		if (SELECT & 1 << _num)
			break;
	}
	if (K == 0 || _num == 26) {
		int now = 0;
		for (int i = 0; i < N; ++i) {
			if (!(TABLE[i] & MASK)) {
				++now;
			}
		}
		BEST = BEST > now ? BEST : now;
		return;
	}
	--K;
	MASK &= ~(1 << _num);
	DFS(_num + 1);
	MASK |= 1 << _num;
	++K;
	DFS(_num + 1);
}

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

	cin >> N >> K;

	for (int i = 0; i < N; ++i) {
		char inp[16];
		cin >> inp;
		int j = 0;
		while (inp[j]) {
			TABLE[i] |= 1 << inp[j] - 'a';
			++j;
		}
		SELECT |= TABLE[i];
	}

	if (K < 5) {
		cout << '0';
	}
	else {
		unsigned int temp = 532741;
		SELECT &= ~temp;
		MASK &= ~temp;
		K -= 5;
		DFS(0);
		cout << BEST;
	}
	return 0;
}

링크

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

해설

사실 이문제는 세그먼트 트리를 이용하거나 펜윅 트리를 이용하면 더욱 빠르게 구할 수 있습니다.

세그먼트 트리를 이용한 방법과 펜윅 트리를 이용한 방법 둘 다 나중에 올리겠습니다.

근데 제가 배우질 않아서 일단 full binary tree 를 이용해서 풀었습니다.

코드는 간단합니다.

입력수만큼 받고 2^n 까지 나머지를 0으로 채우고 full binary tree 로 만들면 됩니다.

그 후 각 노드들은 하위 2개노드의 합을 적어두고

만약 값이 바뀔경우 해당 노드와 상위 노드의 갑만 수정해주면 됩니다.

a ~ b 까지의 합을 구하는 방법은

1. 쪼개고 쪼개다가 최소 단위가 되었을 경우

2. 쪼개던 중 쪼개진 범위가 구해야 하는 범위 안에 다 들어갈 경우

위의 2가지 경우를 모두 더해주면 a ~ b 까지 합을 구할 수 있습니다.

코드

#include <iostream>
using namespace std;

int N, M, K, NUM = 1;
long long TABLE[2097152];

long long sum(int _l, int _r, int _a, int _b, int _num) {
	if ((_l == _a && _r == _b) || _a == _b)
		return TABLE[_num];
	
	int mid_left = (_a + _b - 1) / 2, list_num_left = _num * 2 + 1;

	if (_r <= mid_left)
		return sum(_l, _r, _a, mid_left, list_num_left);
	else if (mid_left < _l)
		return sum(_l, _r, mid_left + 1, _b, list_num_left + 1);
	else
		return sum(_l, mid_left, _a, mid_left, list_num_left) + 
		       sum(mid_left + 1, _r, mid_left + 1, _b, list_num_left + 1);
}

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

	cin >> N >> M >> K;

	int finish, start;
	while (NUM < N) NUM *= 2;
	start = NUM - 1;
	finish = start * 2;
	
	for (int i = start; i < start + N; ++i)
		cin >> TABLE[i];
	
	for (int i = start + N; i <= finish; ++i) {
		TABLE[i] = 0;
	}

	for (int i = start - 1; i >= 0; --i) {
		int num = i * 2 + 1;
		TABLE[i] = TABLE[num] + TABLE[num + 1];
	}

	for (int i = 0; i < M + K; ++i) {
		int first, second;
		cin >> first >> second;

		if (first == 1) {
			long long third;
			cin >> third;
			int number = start + second - 1;
			long long gap = third - TABLE[number];
			while (true) {
				TABLE[number] += gap;
				if (number == 0)
					break;
				number = (number - 1) / 2;
			}
		}
		else {
			int third;
			cin >> third;
			cout << sum(second, third, 1, NUM, 0) << "\n";
		}
	}

	return 0;
}

링크

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

해설

백트래킹을 이용한 간단한 문제입니다.

방법 자체를 생각하는 건 어렵지 않으나 코드를 어떻게 짤지를 고민하는 게 더 중요해 보입니다.

제가 짠 코드는 각 행, 열, 사각형 에 대한 bool 배열을 만들어두고 3개다 true 이면 넣고 다음으로 넘어가는 방식입니다.

그 후 TABLE 에서 0인 칸을 찾아서 1~9 까지 다 넣어보고 하나도 안되면 false 로 뒤로 돌아가고 가능하면 더 가봅니다.

81번째까지 다 검사했는데도 0이 없으면 완성된 것이므로 해결!

코드

#include <iostream>
using namespace std;

int TABLE[81];
bool Y[9][9], X[9][9], square[9][9];

bool sudoku(int _n) {
	for (int i = _n; i < 81; ++i) {
		if (TABLE[i] == 0) {
			int x = i % 9, y = i / 9;
			for (int j = 0; j < 9; ++j) {
				if (X[x][j] && Y[y][j] && square[(y / 3) * 3 + x / 3][j]) {
					TABLE[i] = j + 1;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = false;
					if (sudoku(i + 1))
						return true;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = true;
				}
			}
			TABLE[i] = 0;
			return false;
		}
	}
	return true;
}

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

	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j)
			Y[i][j] = X[i][j] = square[i][j] = true;
	

	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			int inp;
			cin >> inp;
			TABLE[9 * i + j] = inp;
			if (inp != 0) {
				--inp;
				Y[i][inp] = false;
				X[j][inp] = false;
				square[(i / 3) * 3 + j / 3][inp] = false;
			}
		}
	}



	sudoku(0);

	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			cout << TABLE[i * 9 + j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

링크

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