이너의 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를 비교하여 큰 값을 출력한다.

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

Titlebar

상단바라고도 함. UI의 상단에 텍스트와 색을 넣어서 주로 앱의 이름을 보여줄때 사용. Android 2.0 앱들에서 주로 사용됨.

Actionbar

버튼(ex. 뒤로 가기) 을 가지는, 버튼들로서 어떠한 Action들을 취할 수 있게 해주는 상단 bar. Titlebar 대신 사용 가능.

Toolbar

Actionbar보다 더 많은 기능과 특성들을 지니고 있음. Actionbar와 다르게 View이기 때문에 많은 것들을 적용시키기에 용이하다. (ex 애니메이션)

참고 출처

https://stackoverflow.com/questions/19279222/android-whats-the-difference-between-a-title-bar-and-an-actionbar

https://developer.android.com/reference/android/app/ActionBar

https://developer.android.com/reference/android/widget/Toolbar

https://developer.android.com/training/appbar/

<item name="windowActionBar">false</item>
<item name="windowNoTitle">true</item>

values/styles.xml의 자신이 Manifest에서 사용하고 있는 theme에 추가

URL(Uniform Resource Locator) : 자원의 위치를 나타내는 문자열

URN(Uniform Resource Name) : uuid, isbn

URI(Uniform Resource Idenfier) : 통합 자원 식별 표기를 위함. URL과 URN의 상위 개념.

Activity : UI 화면 컴포넌트

Service : 백그라운드에서 실행되는 컴포넌트

Broadcast Receiver : 특정 브로드캐스트에 반응하는 컴포넌트. 배터리 부족 등등

Content Provider : 어플리케이션 간의 공유를 위한 인터페이스 제공 컴포넌트