작은시작

문제

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

풀이

이분 탐색을 바로 생각해내야만 하는 문제였다. 이분 탐색 기본 유형

조건을 만족하면서(Possible) 조건 내 최댓값을 이분 탐색을 통해 찾아내야 한다.

이분 탐색시 랜선길이 개수를 보면 2^32-1 이다. 이를 전부 탐색하려면 이분탐색 방법뿐만 아니라 자료형 또한

long long 이 필요함을 잊지 말자. 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N; //필요한 랜선 개수
int K; //보유한 랜선 개수
vector<long long> kk; //랜선길이개수가 2^32-1 보다 작거나 같은 자연수이므로 longlong 선언
bool Possible(int mid) {
	long long cnt = 0;
	for (int i = 0; i < K; i++) {

		cnt += kk[i] / mid;

	}
	if (cnt >= N) {
    
		return true;
	}
	return false;

}
int main() {
	cin >> K >> N;
	//항상 K <= N

	for (int i = 0; i < K; i++) {
		int a; 
		cin >> a;
		kk.push_back(a);
	}

	//이분탐색
	long long low = 1;
	long long result = 0;
	//high찾기
	long long high = 0;
	for (int i = 0; i < K; i++) {
		
		high = max(kk[i], high);

	}

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

			if (result < mid)  result = mid;

			low = mid + 1;
		
		}
		else {
			high = mid - 1;
		}

	}

	cout << result;

	return 0; 
}

문제

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

풀이

스택을 안 쓰고, NO과정을 생각하다가 괜히 복잡하게 풀고 있었다. 그냥 스택 생성 후 , cnt 변수를 지정해서 스택 쌓고, 빼고 하면 되는 간단한 문제였다. 

이런 쉬운문제는 쉽고 빠르게 푸는 연습이 코딩 테스트에서 더 중요하다고 생각한다....

코드

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int N;
vector<char> result;
int main() {
	cin >> N;
	stack<int> st; //스택만들어서 되는지 안되는지 확인
	bool flag = false;
	int cnt = 1; // 스택 1부터 시작


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

		while (cnt <= a) { // 지정된 수 까지 cnt 쌓기 
			st.push(cnt); 
			cnt++;
			result.push_back('+');
		}
		if (st.top() == a) {
			st.pop();
			result.push_back('-');

		}
		else {

			flag = true;
			break;
		}

	}
	if (flag == true) cout << "NO" << endl;
	else {
		for (int k = 0; k < result.size(); k++) {
			cout << result[k] << '\n';

		}
	}




	return 0;
}

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

코드 설명

sort 연습 및 이중조건시 해결법에 대해 다시 복습할 수 있는 문제였다. 

(+추가로 중복제거도 까먹지말자)

코드 

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

bool cmp(string a, string b) {
	if (a.size() == b.size()) {

		return a < b;
	}

	return a.size() < b.size();

}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string abc;
		cin >> abc;
		arr.push_back(abc);



	}
	sort(arr.begin(), arr.end(),cmp);
	arr.erase(unique(arr.begin(), arr.end()), arr.end());

	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << endl;

	}

	return 0;
}

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

코드 설명

BFS 기본문제 입니다.

BFS를 반복적으로 사용하여 거리가 가장 긴 구간을 완전탐색하여 구하는 문제였습니다.

가장 긴 거리를 재기위해 result라는 또하나의 map을 만들어주어서 거리를 기록하였습니다.

코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int N, M;
char map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int result[51][51];
int maxx;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && map[ny][nx]=='L') {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				result[ny][nx] = result[y][x] + 1;
			}

		}



	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (maxx < result[y][x]) maxx = result[y][x];

		}
	}

}
int main() {
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];


		}


	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 'L'){
				memset(result, 0, sizeof(result));
				memset(visited, false , sizeof(visited));
				bfs(y, x);
			}
		}
	}
	cout << maxx;
	return 0;
}