이너의 Computer Library

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

vector<pair<int, int>> graph[20001];
int n,m;

vector<int> dijkstra(int start, int V) { 
	vector<int> dist(V, INT_MAX);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	
	while(!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		
		pq.pop();
		
		if(dist[here] < cost) continue;
		
		for(int i=0;i<graph[here].size();i++) {
			int nextPos = graph[here][i].first;
			int nextDist = cost + graph[here][i].second;
			
			if(dist[nextPos] > nextDist) {
				dist[nextPos] = nextDist;
				pq.push(make_pair(-nextDist, nextPos));
			}
		}
	}
	
	return dist;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n >> m;
	n++;
	
	while(m--) {
		int from, to;
		
		cin >> from >> to;
		graph[from].push_back(make_pair(to, 1));
		graph[to].push_back(make_pair(from, 1));
	}
	
	vector<int> vv = dijkstra(1, n);
	int ans = 0, ansNum = n, gaesu = 0;
	
	for(int i=n-1;i>=2;i--) {
		if(ans <= vv[i]) {
			ans = vv[i];
			ansNum = i;
		}
	}
	
	for(int i=2;i<n;i++) 
		if(ans == vv[i]) gaesu++;
	
	cout << ansNum << " " << ans << " " << gaesu;
}

다익스트라 문제입니다.

서로 연결된 정점들을 입력받고 그 간선의 길이를 1이라고 두고, 1번 정점으로부터 가장 먼 정점의 번호와 그 길이, 그리고 먼 정점으로터의 거리와 같은 다른 정점들을 출력하면 되겠습니다.

다익스트라 문제를 다시금 복습하게 해주는 문제였습니다.

#include <iostream>
#include <algorithm>
#define mod 9901
using namespace std;

int n;
int d1[100001], d2[100001]; // d1[i] : i번째 칸에 사자가 0마리 있을 때의 경우의 수, d2[i] : i번째 칸에 사자가 1마리 있을 때의 경우의 수 

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n;
	d1[1] = 1;
	d2[1] = 2;
	
	for(int i=2;i<=n;i++) {
		d1[i] = (d1[i-1] + d2[i-1]) % mod;
		d2[i] = (d1[i-1]*2 + d2[i-1]) % mod;
	} 
	
	cout << (d1[n] + d2[n]) % mod;
}

오랜만에 DP 문제로 돌아왔습니다.

2 x n 칸에 사자를 넣는 경우의 수를 구하기 위해 두가지 조건에 부합하도록 dp 배열을 두 개 선언해주었습니다.

2x1 직사각형에

사자가 0마리 있는 경우의 수는 1가지,

사자가 1마리 있는 경우의 수는 2가지로 초기화를 해줍니다.

i번째 줄에 사자가 0마리 있는 경우의 수는,

바로 전에 사자가 한마리도 없었던 경우의 수와 사자가 한마리 있었던 경우의 수를 합칩니다. (바로 전 칸에 사자가 있든 없든 사자가 0마리가 있는 경우의 수이기에 아무런 영향을 주지 않습니다)

i번째 줄에 사자가 1마리 있는 경우의 수는,

바로 전에 사자가 한마리도 없었던 경우의 수*2 (전 칸에 사자가 한 마리도 없었기 때문에 왼쪽 오른쪽 칸 어느 쪽에 넣어도 무방함)와 사자가 한마리 있었던 경우의 수를 합칩니다.

이 과정을 반복하여 경우의 수를 구할 수 있겠습니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 987654321;
using namespace std;

int t;
string n;
int cache[10002]; 

int classify(int a, int b) { 
	// 숫자 조각을 가져옴 
	string m = n.substr(a, b-a+1);
	
	// 난이도 1 검사 - 모두 같은 수 
	if(m == string(m.size(), m[0])) return 1;
	
	// 난이도 2 검사 - 등차수열이자 공차가 1 or -1 
	bool prog = true;
	for(int i=0;i<m.size()-1;i++) 
		if(m[i+1] - m[i] != m[1] - m[0]) prog = false;
		
	if(prog && abs(m[1] - m[0]) == 1) return 2;
	
	// 난이도 4 검사 - 두 수 번갈아가면서
	bool alter =  true;
	for(int i=0;i<m.size();i++) 
		if(m[i] != m[i%2]) alter = false;
	
	if(alter) return 4;
	
	// 난이도 5 검사 - 등차수열
	if(prog) return 5;
	
	// 이외 
	return 10;
}

int memorize(int begin) {
	if(begin == n.size()) return 0;
	
	int &ret = cache[begin];
	if(ret != -1) return ret;
	
	ret = INF;
	for(int L=3;L<=5;L++) {
		if(begin + L <= n.size())
			ret = min(ret, memorize(begin + L) + classify(begin, begin + L - 1));
	}
	
	return ret;
}

int main() {
	// cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> t;
	
	while(t--) {
		memset(cache, -1, sizeof(cache));
		cin >> n;
		cout << memorize(0) << "\n";
	}
}

문자열을 3조각 이상 5조각 이내로 쪼갤 때 만들 수 있는 최소 난이도를 구하는 문제입니다.

난이도를 검사해주는 classify 함수와 난이도의 조합을 메모이제이션으로 구현한 memorize 함수를 이용했습니다.

꽤 재미있었던 문제였습니다. 하단의 책을 참고하여 코드를 작성하였습니다.

[출처] 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만

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

int t,m,n,k;
int ans = 0;
int b[51][51], visited[51][51];
int moveX[4] = {-1, 1, 0, 0};
int moveY[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;

void bfs(int posX, int posY) {
	if(visited[posY][posX] || !b[posY][posX]) return;
	
	ans++;
	q.push(make_pair(posX, posY));
	visited[posY][posX] = 1;
	
	while(!q.empty()) {
		int hereX = q.front().first;
		int hereY = q.front().second;
		
		q.pop();
		
		for(int i=0;i<4;i++) {
			int nextX = hereX + moveX[i];
			int nextY = hereY + moveY[i];
			
			if(nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !visited[nextY][nextX] && b[nextY][nextX]) {
				q.push(make_pair(nextX, nextY));
				visited[nextY][nextX] = 1;		
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> t;
	
	while(t--) {
		cin >> m >> n >> k; // m : 가로의 길이, n : 세로의 길이 
		
		while(k--) {
			int x, y;
			cin >> x >> y;
			
			b[y][x] = 1;
		}
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				bfs(j, i);
				
		cout << ans << "\n";
		
		ans = 0;
		memset(b, 0, sizeof(b));
		memset(visited, 0, sizeof(visited));
	}
}

bfs로 배추밭에서 인접한 배추들의 그룹 개수를 세게 하였습니다.

bfs와 범위만 조심한다면 어렵지 않게 풀 수 있는 문제였습니다.

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

int n;
string name, goWork;
map<string, bool, greater<string>> mm;

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

	cin >> n;
	
	while(n--) {
		cin >> name >> goWork;
		
		bool b;
		if(goWork[0] == 'e') b = true;
		else b = false;
		
		mm[name] = b;
	}
	
	for(map<string, bool, greater<string>>::iterator iter = mm.begin();iter!=mm.end();iter++)
		if(iter -> second) cout << iter -> first << "\n";
}

map을 사용하여 간단하게 풀 수 있는 문제입니다.

map은 default로 오름차순으로 key가 정렬되는데, 사전 순의 역순이라고 하였으므로 내림차순으로 sort되기 위해 greater를 추가해주었습니다.

이후 입력을 받으면서 value에 출퇴근 여부를 담고 iterator로 map을 순회하면서 출근 상태인 사람들의 key를 출력하게끔 하였습니다.

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

int n, from, to, length;
int start_point, end_point, maxLen=0, ansDis[50001], ansDis2[50001], visited[50001];
vector<pair<int,int>> v[50001];

void dfs(int pos, int length) {
	if(visited[pos]) return;
	
	visited[pos] = 1;
	ansDis[pos] = length;
	
	if(maxLen < length) {
		end_point = pos;
		maxLen = length;
	}
	
	for(int i=0;i<v[pos].size();i++)
		dfs(v[pos][i].first, length + v[pos][i].second);
		
	visited[pos] = 0;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n;
	
	for(int i=0;i<n-1;i++) {
		cin >> from >> to >> length;
		v[from].push_back(make_pair(to, length));
		v[to].push_back(make_pair(from, length));
	}
	
	dfs(1,0);
	start_point = end_point;
	maxLen = 0;
	
	dfs(start_point,0);
	for(int i=1;i<=n;i++) {
		ansDis2[i] = ansDis[i];
		ansDis[i] = 0;
	}
	
	dfs(end_point,0);
	for(int i=1;i<=n;i++)
		cout << max(ansDis[i], ansDis2[i]) << "\n";
}

오랜만의 포스팅입니다! :D

N개의 노드에서 N-1개의 쌍방향으로 갈 수 있는 간선이 존재할 때 각각의 노드에서 가장 먼 노드까지의 거리를 구하는 문제입니다.

다익스트라로 문제를 해결하려 했으나 한 쪽으로 치우친 그래프가 생길 수 있기 때문에 시간 초과가 발생하여 어떻게 해결해야 하는지 고민을 하던 도중 간선의 개수가 노드의 개수가 작음을 깨닫고 트리 구조를 떠올리게 되었고, 이는 곧 트리에서 가장 긴 지름을 구하는 문제를 응용한 것임을 알게 되었습니다.

저는 이런 방식으로 풀이했습니다.

1. 트리의 지름이 되는 두개의 노드를 구하기 위해 3번의 순회를 거친다

2. 1번째 순회로 지름의 시작 노드를 구한다.

3. 2번째 순회로 지름의 끝 노드를 구하면서, 지름의 시작 노드로부터의 거리들(=ansDis)을 저장한다.

4. 3번째 순회로 지름의 끝 노드로부터의 거리들(=ansDis2)을 저장한다.

5. ansDis와 ansDis2를 비교하여 큰 값을 출력한다.

만약 제가 틀린 부분이 있다면 지적 부탁드리겠습니다. (꾸벅)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string s;
int sum = 0;

int main() {
	cin >> s;
	
	while(1) {
		string tmp;
		
		while(s[0] != ',') {
			tmp += s[0];
			s = s.substr(1);
			if(s.length() == 0) break;
		}
		sum += atoi(tmp.c_str());
		//cout << tmp << " " << s << endl;
		if(s.length() == 0) break;
		s = s.substr(1); // 콤마 삭제 
	}
	
	cout << sum;
}

string 클래스의 substr 사용법과 how to convert string to int만 알고있다면 쉽게 풀 수 있는 문제입니다.

<Convert string to int>

int n = atoi(str.c_str());

* string에 c_str()을 해주는 이유는 atoi 함수 안의 매개변수의 형식이 char*이여야 하기 때문에 변환해주어야 합니다.

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

int arr[100];
int n,m;
vector<int> v;
int maxSum = 0;

void comb(int n, int r, int index) {
	if(r == 0) {
		int sum = 0;
		for(int i=0;i<v.size();i++)
			sum += v[i];
		if(sum <= m && sum > maxSum) 
			maxSum = sum;
		
		return;
	}
	else if(n == r) {
		int sum = 0;
		for(int i=0;i<n;i++)
			v.push_back(arr[i+index]);
		for(int i=0;i<v.size();i++)
			sum += v[i];
		if(sum <= m && sum > maxSum) 
			maxSum = sum;
		for(int i=0;i<n;i++)
			v.pop_back();
			
		return;
	}
	
	v.push_back(arr[index]);
	comb(n-1,r-1,index+1);
	v.pop_back();
	comb(n-1,r,index+1);
	
	return;
}

int main() {
	scanf("%d %d",&n,&m);
	
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
		
	comb(n,3,0);
	printf("%d",maxSum);
}

N<=100이여서 조합으로 풀 수 있을것 같다고 생각하여 조합을 이용해 해결하였습니다.

풀이과정은 조합 알고리즘에서 합이 m 이하이고 maxSum을 두어 m과 가장 가까운 수가 되도록 하는 원리를 적용한 것이기에 자세한 설명은 생략하겠습니다.

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 100
using namespace std;

int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};
int map[MAX][MAX];
int visited[MAX][MAX];
int n,m;
queue<pair<int, int> > q;

bool isInside(int y, int x) {
	return (y >= 0 && x >= 0 && y < n && x < m);
}

int bfs(int startY, int startX) {
	int nowY = startY;
	int nowX = startX;
	
	q.push({nowY, nowX});
	visited[nowY][nowX] = 1;
	
	while(!q.empty()) {
		nowY = q.front().first;
		nowX = q.front().second;
		q.pop();
		
		if(!isInside(nowY,nowX)) continue;
		
		for(int i=0;i<4;i++) {
			int nextY = nowY + dy[i];
			int nextX = nowX + dx[i];
			
			if(isInside(nextY,nextX) && !visited[nextY][nextX] && map[nextY][nextX]) {
				visited[nextY][nextX] = visited[nowY][nowX] + 1;
				q.push({nextY, nextX});
			}
		}
	}
	
	return visited[n-1][m-1];
}

int main() {
	scanf("%d %d",&n,&m);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) 
			scanf("%1d",&map[i][j]);
	
	printf("%d",bfs(0,0));
}

BFS를 이용한 풀이입니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

string s;
vector<pair<char, int> > v;

bool cmp(const pair<char, int> &u, const pair<char, int> &v) {
	return u.second > v.second;
}

int main() {
	
	cin >> s;
	transform(s.begin(), s.end(), s.begin(), ::toupper);
	sort(s.begin(), s.end());
	
	for(int i=0;i<s.length();i++) {
		if(v.empty()) {
			v.push_back({s[i], 0});
			continue;
		}
		
		if(v.back().first == s[i]) {
			v.back().second++;
			continue;
		}
		
		v.push_back({s[i], 0});
	}
	
	sort(v.begin(), v.end(), cmp);
	
	if(v[0].second == v[1].second && v.size() > 1)
		printf("?");
	else
		printf("%c",v[0].first);
}

입력 받은 문자열들을 처음부터 대문자로 아예 변환시키고 sort한 다음 vector에 개수를 차곡차곡 쌓고 다시 second(=알파벳의 개수)를 중심으로 sort한 원리입니다. 주의해야 할점은 알파벳이 하나밖에 없을 경우 v[0].second == v[1].second 조건만 넣으면 ?가 뜰 수 있기 때문에 size 체크도 해주셔야 합니다.

문자열 모두 대문자/소문자 변환하는 함수 transform을 이번에 처음으로 공부해봤기에 남겨봅니다.

template <class InputIterator, class OutputIterator, class UnaryOperator>
  OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperator op)

op 파라미터 부분에 ::toupper가 올 시 대문자로, ::tolower가 올시 소문자로 변환