이것 저것 &

문제링크: https://www.acmicpc.net/problem/15924

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  모든 좌표에서 도달 가능한 좌표를 탐색

이때, dp에 값을 저장해두었다가 같은 좌표를 탐색할때는 곧바로 반환해주는 형태로 구현

정답코드

#include <iostream>

using namespace std;

int n, m;
char arr[3001][3001];
long long dp[3001][3001];
long long result = 0;

long long solved(int y, int x) {
	if (y == n && x == m)
		return 1;

	long long& ret = dp[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (arr[y][x] == 'B') {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else if (arr[y][x] == 'E') {
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
	}

	ret %= 1000000009;

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			result += solved(i, j);

	cout << result % 1000000009 << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/13703

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  높이 수면에 닿는 경우는 항상 배제시켜주고, 

시간이 다 될때 까지 수면에 닿지 않았다면 + 1 을 추가해주는 형태로 진행함

정답코드

#include <iostream>
using namespace std;

long long dp[64 * 2][64];
int n, k;

long long solved(int kk, int nn) {
	
	if (kk == 0)
		return 0;
	if (nn == 0)
		return 1;

	long long& ret = dp[kk][nn];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(kk-1, nn-1);
	ret += solved(kk+1, nn-1);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> k >> n;

	for (int i = 0; i < 64*2; i++)
		for (int j = 0; j < 64; j++)
			dp[i][j] = -1;

	cout << solved(k, n) << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1715

문제 접근에 대해서 이해하면 쉽게 구현한 문제이다.

우선, 그리디한 방식으로 문제를 도출할 수 있다는 것을 이해해야 한다!

접근방식

1. 생각해보면, 항상 작은수를 먼저 처리해주면 최소값이 도출이 된다는 것을 알수 있다.

2. 그렇다면 새로 추가되는 수는 어떻게 관리해주어야 할까? 

새로 수를 넣어줄때 마다 정렬을 해야하나? 

아니다!

그냥 편하게 우선순위 큐를 사용하면 될 일이다. 

자동으로 lgn번의 탐색으로 수를 정렬된 상태로 보관해주기 때문에

해당 문제에 가장 적합한 자료구조이다.

문제풀이 

1.  구현 자체는 너무나도 단순하다.

priority_queue를 사용하여 문제를 해결하자.

정답코드입니다.

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

int n = 0;
priority_queue <int> que;
long long result = 0;

int main() {
	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		que.push(temp * -1);
	}

	while (que.size() != 1) {

		int a = que.top() * -1;
		que.pop();
		int b = que.top() * -1;
		que.pop();

		result += (a + b);

		que.push( (a + b) * -1);


	}

	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1339

간만에 풀어보는 그리디 알고리즘!

접근방식

1. 일반적인 접근방식으로 숫자 자릿수가 큰 경우에 높은 숫자를 배정해주면 될거라고 생각함

ex) accc + bbb일때,

a가 9가 되어야 하지요!

2.  다만 자릿수가 동일한 경우에 우선순위 배정을 신경써주야 한다!

ex) abbb + acdd

이때, a =9 는 당연하고 c와 b 중에서 b에 8을 배정해야 하는 부분!

이부분을 처리하기 위해서, 각 자릿수를 더해주는 형식으로 진행했다.

a = 1000 + 1000 = 2000b = 111 c = 100d = 22

숫자가 더 큰 친구가 높은 우선순위에 속하도록 구현하면 끝!~

문제풀이 

1.  문제 접근 2번에 설명한 것처럼 구현을 진행함

이때, 내림차순으로 정렬을 진행해두어야 함

2. 정렬된 값들을 순서대로 탐색하며 수를 배정해줌으로서 문제 해결

정답코드입니다.

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

int arr[26] = { 0, };
int n = 0;
int result = 0;

bool cmp(int& a, int& b) {
	if (a > b)
		return true;
	else
		return false;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;

		int cnt = 1;
		for (int j = temp.size() - 1; j >= 0; j--) {
			arr[temp[j] - 'A'] += cnt;

			cnt *= 10;
		}
	}

	sort(arr, arr + 26, cmp);
	int cnt = 9;
	for (int i = 0; i < 26; i++) {
		if (arr[i] == 0)
			break;

		result += arr[i] * cnt;
		cnt--;
	}

	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/2758

Top-down 방식의 dp로 해결했습니다. 

접근방식

1. 문제를 보면서 일반적인 dfs로는 구현이 불가능한 것을 이해하였고, dp로 구현하기로 함

2.  top-down방식을 통해서 구현

문제풀이 

1.  일반적인 top-down방식으로 구현 

주의점은 숫자 범위때문에 long long으로 선언해야한다는점?

아래는 정답 코드

#include <iostream>
using namespace std;
int t;
int n, m;
long long dp[2001][11];

long long solved(int currentN, int currentM) {

	if (currentN == 1)
		return 1;

	long long& ret = dp[currentM][currentN];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = currentM/2; i >= 1; i--) {
		ret += solved(currentN - 1, i);
	}

	return ret;
}

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

	cin >> t;
	while (t--) {
		cin >> n >> m;

		for (int i = 1; i <= 2000; i++)
			for (int j = 1; j <= 10; j++)
				dp[i][j] = -1;

		long long result = 0;
		for (int i = m; i >= 1; i--)
			result += solved(n, i);

		cout << result  << "\n";

	}


	return 0;
}

문제링크: https://www.acmicpc.net/problem/3108

전형적인 한붓그리기 문제라고 하는데 어려움을 겪었습니다.

마이너스 좌표는 +500을 더해줌으로 해결했는데,

아래와 같은 그림에서 멘붕이 왔습니다.

위 처럼 네모가 둘이 붙어있으면 일반  탐색으로는 붙어 있는 걸로 처리 되었기 때문입니다.

이를 해결하기 위해서  동서남북 4방향을 저장하는 배열을 작성하면서 제작하려 해보았지만, 

실패...

얍문님 티스토리를 통해서 좌표값에 2배를 곱해줌으로서 쉽게 이러한 문제를 해결할 수 있단 걸 

알게되었습니다. (감사함다.)

접근방식

1. 좌표값을 (a + 500) * 2로 만든후 직사각형들을 색칠

2. 일반 bfs를 통해서 연결된 도형들을 탐색하면서 갯수를 세어주자

문제풀이 

1. 좌표값에 (a + 500) * 2 를 해주기

2. (0,0) 좌표인 arr[1000][1000]을 미리 bfs로 탐색해주기.

( 제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다. )

3. 0,0부터 2000,2000까지 bfs로 탐색하면서 뭉쳐진 도형들을 색칠해주며 갯수 세기

아래는 정답 코드

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

int n, result ;
int x1, y11, x2, y2;

bool arr[2001][2001] = { 0, };
bool visited[2001][2001] = { 0, };

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };


void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny > 2000 || nx < 0 || nx > 2000)
				continue;
			if (visited[ny][nx] != 0 || arr[ny][nx] != 1)
				continue;
			visited[ny][nx] = 1;
			que.push(make_pair(ny, nx));

		}



	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {

		cin >> x1 >> y11 >> x2 >> y2;
		x1 = (x1 + 500) * 2;
		y11 = (y11 + 500) * 2;
		x2 = (x2 + 500) * 2;
		y2 = (y2 + 500) * 2;

		for (int i = x1; i <= x2; i++) {
			arr[y11][i] = 1;
			arr[y2][i] = 1;
		}
		for (int i = y11; i <= y2; i++) {
			arr[i][x1] = 1;
			arr[i][x2] = 1;
		}
	}

	
	if(arr[1000][1000] == 1)
		bfs(1000, 1000);

	for (int i = 0; i <= 2000; i++)
		for (int j = 0; j <= 2000; j++)
			if (arr[i][j] == 1 && visited[i][j] == 0) {
				bfs(i, j);
				result++;
			}

	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/2186

top-down방식의 dp를 사용해서 해결하는 문제였습니다.

문제 예시에서는 k가 1이라 break는 총 3가지 경우가 포함이 됩니다.

모든 그래프에 대해서 단순 dfs나 bfs로는 시간문제때문에 해결을 할 수 없습니다.

dp를 통해서 탐색했던 내용을 복사해두고 다음번 탐색에서 사용할 수 있도록 구현해야 합니다.

접근방식

1. 그래프 탐색을 통해서 문제를 해결하자.

2. 속도적인 문제 때문에 dp를 통해서 문제를 해결하자.

문제풀이 

1. dp[100][100][81]로 생성 좌표와 몇번째 단어인지를 나타내는 인덱스들이다.

2. k가 늘어남에 따라서 이동할 수 있는 칸이 늘어나는데, while문을 사용해서 이러한 문제를 해결했다.

아래는 정답 코드

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

int dp[100][100][81]; // 0 base
char arr[100][100];
string word;

int n, m, k;

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

int result = 0;

int solved(int y, int x, int cnt) {

	
	if (cnt == word.size())
		return 1;

	int& ret = dp[y][x][cnt];
	if (ret != -1)
		return ret;

	ret = 0;

	for (int i = 0; i < 4; i++) {
		int  c = k;
		int ny = y;
		int nx = x;
		while (c--) {
			ny +=  y_ar[i];
			nx +=  x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (arr[ny][nx] != word[cnt])
				continue;
			ret += solved(ny, nx, cnt + 1);
		}
	}

	return ret;
}

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

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	cin >> word;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int u = 0; u <= word.size(); u++)
				dp[i][j][u] = -1;



	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == word[0]) {
				result += solved(i, j, 1);
			}


	cout << result << endl;

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << dp[i][j][1] << ' ';
		cout << endl;
	}*/

	return 0;
}

문제링크: https://www.acmicpc.net/problem/12738

대표적인 이분탐색 LCS문제입니다.

아래 문제와 동일하여 설명은 대체합니다.

https://gusdnr69.tistory.com/279

문제풀이 

1.  일반적인 구현방식으로 해결

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

int n;
int arr[1000000];
vector <int> v;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++) {
		if (v.size() == 0 || v[v.size() - 1] < arr[i]) v.push_back(arr[i]);
		else {
			int left = 0;
			int right = v.size();

			while (left <= right) {
				int mid = (left + right) / 2;
				if (v[mid] >= arr[i]) right = mid - 1;
				else left = mid + 1;
			}
			v[left] = arr[i];

		}


	}
	cout << v.size() << endl;
	return 0;
}