이것 저것 &

문제링크: 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;
}

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

최장 공통 수열 (LCS)를 도출하는 문제.

문제에 대한 설명은.... https://yhwan.tistory.com/18

이분보다 잘할 자신이 없어서 이분꺼 참고

같은 논리로 작성하였는데, 정작 나는 이분탐색을 사용하지 않은 일반구현으로 제작했다.

아직까지 굳이 이분탐색으로 작성해야하는 이유를 못느끼고 있다.. (문제 검색에 올려놓음)

접근방식

1.  LCS 만큼의 전깃줄이 남아있을 수 있겠구나

2.  수의 범위가 커서 dp를 사용한 방식O(n^2)으로는 불가능 하겠구나 

문제풀이 

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

정답코드입니다.

아래 방식이 이분탐색을 사용하지 않아서 문제가 될 수 있을 것 같은데, 아직까지는 잘 모르겠습니다.

혹시 아시는 분은 댓글 부탁드립니다. 

--- ++ 추가 ---

아래방식은 해당 문제에서는 시간초과가 난다. 

최악의 경우에는 취약한 방법이기 때문이다. 따라서 이분탐색 방식을 권장한다.

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

단순 구현

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

int n = 0, temp;
vector <int> vec;
int lcs[100000];
int lcs_cnt = -1;


void low_bound(int num) {

	int val = vec[num];

	for (int i = 0; i <= lcs_cnt; i++) {
		if (val < lcs[i]) {
			lcs[i] = val;
			break;
		}

	}
}


int main() {

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}

	for (int i = 0; i < vec.size(); i++) {

		if (lcs_cnt == -1)
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] <= vec[i]) 
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] > vec[i]) 
			low_bound(i);
		

	}
	
	
	
	cout << n - (lcs_cnt + 1) << endl;

	return 0;
}

이분탐색 적용

#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 << n - v.size() << endl;
	return 0;
}

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

일반적인 투포인터 문제

주의할 점은 "입력은 여러 개의 테스트 케이스로 이루어져 있다."  라는 말...

테스트케이스에서는 테스트가 반복되지않는 예시를 주는데, 입력을 여러번 받을 수 있도록 구현해야하는 문제.

while(cin>>a>>b)

위 처럼 작성함으로서 해당 문제는 해결

접근방식

1. 투 포인터를 가지고 값을 하나씩 조정해 보면서 결과를 도출한다. 

2. " |ℓ1 - ℓ2|가 가장 큰 것 " 이라는 조건을 유념하면서 

문제풀이 

1. 배열을 정렬

2. 일반적인 투포인터 처럼 값을 하나씩 옮기면서 구현

3. |ℓ1 - ℓ2|가 가장 클려면 인덱스의 간격이 가장 클 때(정렬 상태에서) 이니까 

결과값이 도출되면 바로 break! 

구현자체 난이도는 상당히 쉬운 편이었습니다.

정답코드입니다.

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


int main() {

	int x, n;
	
	while (cin >> x >> n) {
		x *= 10000000;
		vector<int> vec;
		int temp;

		for (int i = 0; i < n; i++) {
			cin >> temp;
			vec.push_back(temp);
		}
		sort(vec.begin(), vec.end());

		int low = 0, high = vec.size() - 1;
		bool flag = false;

		while (low < high) {

			int sum = vec[low] + vec[high];
			if (sum == x) {
				flag = true;
				break;
			}
			if (sum < x) { //low를 이동시켜줘야지..
				low++;
			}
			else { //sum > x
				high--;
			}


		}

		if (flag)
			cout << "yes " << vec[low] << ' ' << +vec[high] << endl;
		else
			cout << "danger" << endl;

	}



	return 0;
}

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

이분탐색임을 인지했는데, 어떻게 풀어나가야 할지 고민했던 문제

처음에는 간격이 제일 넓은 구획을 찾고, 그 두 간격을 반토막씩 자르면 어떨까 생각함

하지만 아래 처럼 휴게소가 배치되어있고, m = 2인 경우라면 

이렇게 추가가 되어짐...

당연히 오답.. 

거리가 비례하게끔, 아래 그림처럼 구성이 되어져야함 

고민하다가 "거리"로 이분 탐색해야 한다는 것을 깨닫게 됨.

접근방식

1. 위 설명처럼 거리를 통한 이분탐색을 생각하게 됨

2. 이분탐색에서의 조건은 휴게소 간격들 사이 해당 거리(mid) 만큼 지정했을 때, 배치 가능한 갯수 

문제풀이 

주석을 자세하게 적어 놓아기 때문에 생략

정답 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, l;
vector <int> vec;

bool cmp(int& a, int& b) { // 없어도 되지만 간만에 짜보고 싶었어요ㅋㅋ
	if (a < b)
		return true;
	return false;
}

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

	cin >> n >> m >> l;
	int temp;
	vec.push_back(0), vec.push_back(l); //시작점과 끝점 추가 + 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 라는 조건 때문에
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}
	sort(vec.begin(), vec.end(), cmp);



	int low = 0, high = l;
	int mid, result = 0;

	while (low <= high) {
		mid = (low + high) / 2; 

		int val = 0; // 휴게소 사이에 배치 될 수있는 휴게소의 갯수
		for (int i = 1; i < vec.size(); i++) {
			int dist = vec[i] - vec[i - 1]; // 휴게소 a와 b 사이에 간격

			val += (dist / mid); // 휴게소 간격 / 현재 길이
			if (dist%mid == 0) //휴게소가 이미 있는 위치라면 
				val--; // 갯수를 하나 감소 시켜주어야지. 
		}
		if (val > m)  // 배치할 수 있는 휴게소가 m개 보다 많으면
			low = mid + 1; // 길이를 늘려주어 m개가 배치 되게끔 만들어주고 
		else {// 배치될 휴게소가 m개보다 작거나 같을 때 
			high = mid - 1;// 길이(mid)가 더 작아질 수 있을지 확인해야지  
			result = mid;  //결과값을 갱신해주기 
		}
	}

	cout << result << endl;

	return 0;
}

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

일반 반복탐색은 1000000000번 탐색을 반복해야하기 때문에 무조건 시간초과(대략 10초)

킹반적인 이분탐색문제입니다.

이분탐색 개념이 모호하시다면, 아래 링크를 참고하세요! 

https://cjh5414.github.io/binary-search/

접근방식

1. 일반적인 반복은 시초니까 이분탐색을 사용해보자

문제풀이 

1. result 를 -1로 저장한다. 만약 불가능하다면 result 값을 갱신하지 않아서 -1이 그대로 남게 된다.

2. 일반적인 이분탐색 방식으로 구현 코드를 보면 이해가 더 빠를듯

정답 코드입니다.

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

double x, y;
double z;
int result = -1;


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

	cin >> x >> y;
	z = (y * 100) / x;
	z = floor(z);

	int low = 1;
	int high = 1000000000;

	while (low <= high) {
		int mid = (low + high) / 2; // 범위 ㄱㅊ
		double val = (double)((y + mid) * 100) / (x + mid);
		val = floor(val);
		if (val > z) {
			result = mid;
			high = mid - 1;
		}
		if (val <= z) {
			low = mid + 1;
		}
	}


	cout << result << endl;

	return 0;
}

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

사소한 부분에서 틀렸던 문제...

4일 동안 반례를 못찾고 시름시름 앓고 있었는데, bamgoesn 님께서 반례를 찾아주셨다. ㅠㅠ

다시 한번 감사드립니다. ㅠㅠ

구현 + bfs 문제입니다. 

어떻게 보면 시뮬레이션이기도 하고, bfs 심화같기도 한 문제.

접근방식

1. 우선 빈칸들의 좌표별로 이동가능한 값들을 저장해야한다.

이때, 구획별로 번호를 매겨주어서 벽을 허물었을 때, 중복으로 구획을 세지 않도록 한다.

2. 벽을 하나씩 부서보면서 해당하는 좌표의 값을 도출한다. 

문제풀이 

1. bfs를 통해서 빈 좌표별로 이동가능한 최대한 값을 도출한다.

2. 다시 한번 bfs를 통해 이번엔 구획에 해당하는 모든 값들에 이동가능한 값과 구획번호를 저장

3. 벽 좌표를 vector에 저장하고 하나씩 부서보면서 결과를 도출

이때, 구획번호가 중복이 되지 않겠끔 vector에 구획번호를 저장하면서 4방향을 모두 확인 

정답코드입니다. 

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

int n, m;
int arr[1001][1001] = { 0, };
vector <pair<int, int>> block;
int result[1001][1001] = { 0, };

int visited[1001][1001][2] = { 0, }; // 첨에는 이동 가능한 개수를 저장할거고, 두번째에는 고유 영역 값을 저장할 예정
int vis_cnt = 1; // 구획의 첫 번호는 1부터 

bool temp_v[1001][1001] = { 0, }; //난 bfs로 구현할거야, 얘는 탐색을 위해 사용할 배열

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


void bfs(int ty, int tx) {

	// 1. temp_v를 사용해서 이동 가능한 개수 파악하기
	int maxed = 1;
	temp_v[ty][tx] = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(ty, tx));

	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 >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (temp_v[ny][nx] != 0)
				continue;
			temp_v[ny][nx] = 1;
			que.push(make_pair(ny, nx));
			maxed++;
		}
	}
	//cout << maxed << endl;

	// 2. visited에 이동가능한 개수와 자신의 구획번호를 입력하기 
	visited[ty][tx][0] = maxed;
	visited[ty][tx][1] = vis_cnt;
	que.push(make_pair(ty, tx));

	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 >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (visited[ny][nx][0] != 0)
				continue;
			visited[ny][nx][0] = maxed;
			visited[ny][nx][1] = vis_cnt;
			que.push(make_pair(ny, nx));
		}
	}



	vis_cnt++; //인덱스를 하나 올려준다.


}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 1)
				block.push_back(make_pair(i, j));
		}
	}

	//cout << block.size() << endl;

	//1. 영역별로 마킹하기!

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp_v[i][j] == 0 && arr[i][j] == 0) { // 벽이 아니고, 방문한 적이 없다면 탐색해야해!
				bfs(i, j);
			}

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

	//2. 벽을 하나씩 부수면서 이동가능한 결과값을 도출하는 과정 

	vector <int> index; // index 값들을 임시 저장할 친구 
	for (int i = 0; i < block.size(); i++) {
		index.clear();
		int val = 1; //자신을 포함해야 하니 1 부터 시작한다. 
		
		int y = block[i].first;
		int x = block[i].second;

		for (int j = 0; j < 4; j++) {
			bool flag2 = true;
			int ny = y + y_ar[j];
			int nx = x + x_ar[j];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 1)
				continue;
			for (int i = 0; i < index.size(); i++)
				if (visited[ny][nx][1] == index[i]) {
					flag2 = false;
					break;
				}
			if (flag2 == true) {
				val += visited[ny][nx][0];
				index.push_back(visited[ny][nx][1]);
			}
			
		}

		result[y][x] = val % 10;
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d", result[i][j]);
		printf("\n");
	}

}