굳건하게

문제 : https://www.acmicpc.net/problem/1351

[ 알고리즘풀이 ]

 전형적인 DP 문제지만 N이 너무 크므로 모든 부분에 값을 저장해서 쌓아가면 안되고, 점화식을 보면 DP[N] 은 P, Q가 제일 작은 2라고 반씩 크기가 줄어드므로 적당한 범위까지만 수열 값을 저장하고 난 후 재귀식으로 DP[N] 값을 구하면 쉽게 해결할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std;

const long long MAX = 10000000;
long long N, P, Q, dp[MAX + 1];

long long DP(long long N) {
	if (N <= MAX)
		return dp[N];
	return DP(N / P) + DP(N / Q);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	dp[0] = 1;
	cin >> N >> P >> Q;

	long long k = min(N, MAX );

	for (long long i = 1; i <= k; i++)
		dp[i] = dp[i / P] + dp[i / Q];

	cout << DP(N);

	return 0;
}

문제 : https://www.acmicpc.net/problem/1167

[ 알고리즘 풀이 ]

가장 긴 트리의 지름을 정하는 두 노드는 리프 노드다. ( 리프 노드가 아니면, 더 갈 수 있으므로 최대 지름일 수가 없다. ) 따라서, 우리는 리프 노드 2개를 골라 탐색을 하며 거리를 계산해봐야 되는데 이때, 모든 리프 노드 쌍에 대해서 탐색을 진행하면  정점이 100,000 개라 최악의 경우 (100,000)^2 번에 가까운 탐색이 진행돼 시간초과 문제에 걸리게 된다. 따라서, 임의의 리프 노드에서 BFS 탐색을 진행해 거리가 최대가 되는 순간의 리프 노드를 하나 찾고( 가장 긴 트리의 지름 중 하나의 노드 ) 다시 찾은 노드에서 BFS 탐색을 진행하면 가장 긴 트리의 지름을 찾을 수 있다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int V, s, x, y;
vector<pair<int, int>> graph[100001];
bool visited[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V;
	for (int i = 0; i < V; i++) {
		cin >> s;
		while (1) {
			cin >> x;
			if (x == -1)
				break;
			cin >> y;
			graph[s].push_back({ x,y });
			graph[x].push_back({ s,y });
		}
	}

	int start = 1;
	for (int i = 1; i <= V; i++) {
		if (graph[i].size() == 2){
			start = i;
			break;
		}
	}
	
	int ans = 0;
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = 1;

	int endNode = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		if (ans < cur.second) {
			endNode = cur.first;
			ans = cur.second;
		}

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	memset(visited, 0, sizeof(visited));
	q.push({ endNode, 0 });
	visited[endNode] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		ans = max(ans, cur.second);

		for (int i = 0; i < graph[cur.first].size(); i++) {
			if (visited[graph[cur.first][i].first])
				continue;
			visited[graph[cur.first][i].first] = 1;
			q.push({ graph[cur.first][i].first, cur.second + graph[cur.first][i].second });
		}
	}

	cout << ans;
}

문제 : https://www.acmicpc.net/problem/1068

[ 알고리즘풀이 ]

- 정의)

graph[X][Y] := X가 Y의 부모 노드면 1, 아니면 0.

( 즉, 부모가 자식에게 간선을 이음. )

1. 지워야하는 노드(del) 을 입력받으면, del 에서 BFS 탐색을 이용해 가능한 모든 노드를 탐색한다. 즉, del 의 자식, 자손들을 모두 탐색하면서 지워지는 노드로 check하고 graph 를 갱신한다.

2. 갱신된 graph 를 탐색하면서 지워지지 않은 노드별로 자식의 개수를 카운트한다.

3. 지워지지않고, 자식이 없는 노드들만 카운트한다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, j, del, sub[50] = {};
	bool graph[50][50] = {};
	bool checkDel[50] = {};

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> j;
		if (j == -1)
			continue;
		graph[j][i] = 1;
	}
	cin >> del;

	queue<int> q;
	q.push(del);
	while (!q.empty()) {
		int s = q.front();
		checkDel[s] = 1;
		q.pop();
		for (int i = 0; i < N; i++)
			graph[i][s] = 0;
		for (int j = 0; j < N; j++)
			if (graph[s][j])
				q.push(j);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			if (graph[i][j])
				sub[i]++;
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (checkDel[i])
			continue;
		if (sub[i] == 0)
			ans++;
	}
	cout << ans;
}

안녕하세요, 여행벌입니다.

오늘은 자바 비트 연산자에 대해서 다뤄보겠습니다.

비트 연산자

 비트 연산자는 각각의 비트를 대상으로 연산을 진행하는 연산자이며 피연산자는 반드시 정수이어야 합니다. 실수를 대상으로 하는 비트 연산은 의미가 없기에 자바에서 지원하지 않습니다.

비트 연산자 : &, |, ^, ~

예제 1)

package Hello;

public class HelloWorld {
	public static void main(String args[]) {
		int a = 8; // 1000(2)
		int b = 4; //  100(2);
		System.out.printf("a & b : %d\n", a & b);
		System.out.printf("a | b : %d\n", a | b);
		System.out.printf("a ^ b : %d\n" , a ^ b);
		System.out.printf("~a : %d" , ~a);
	}
}

a는 8로 2진수로 표현하면 0000 0000 0000 0000 0000 0000 0000 1000(2)

b는 4로 2진수로 표현하면 0000 0000 0000 0000 0000 0000 0000 0100(2) 와 같습니다.

따라서, 비트 연산 & 를 진행하면 각 비트 별로 AND 연산이 진행되고,

0000 0000 0000 0000 0000 0000 0000 0000(2) 가 됩니다.

비트 연산 | 를 진행하면 각 비트 별로 OR 연산이 진행되고,

0000 0000 0000 0000 0000 0000 0000 1100(2) 가 됩니다.

비트 연산 ^ 를 진행하면 각 비트 별로 XOR 연산이 진행되므로

0000 0000 0000 0000 0000 0000 0000 1100(2) 가 됩니다.

비트 연산 ~ 를 진행하면 a의 각 비트를 0 이면 1, 1이면 0으로 바꾸므로

1111 1111 1111 1111 1111 1111 1111 0111(2) 가 됩니다.

따라서 결과는 0, 12, 12, -9가 됩니다.

a & b : 0
a | b : 12
a ^ b : 12
~a : -9

비트 쉬프트 연산자 : <<, >>, >>>

 비트 쉬프트 연산자는 피연산자의 비트 열을 왼쪽 또는 오른쪽으로 이동시킨 결과를 반환하는 연산자입니다. 두 개의 피연산자가 필요한 이항 연산자이며, 피연산자는 모두 정수여야 합니다.

예시 2)

package Hello;

public class HelloWorld {
	public static void main(String args[]) {
		byte num = 2; // 00000010 (2)
		System.out.println((byte)(num << 1)); //00000100(2)
		System.out.println((byte)(num << 2)); //00001000(2)
		System.out.println((byte)(num << 3)); //00010000(2)
		
		num = 13; // 00001101 (2)
		System.out.println((byte)(num >> 1)); // 00000110(2)
		System.out.println((byte)(num >> 2)); // 00000011(2)
		System.out.println((byte)(num >> 3)); // 00000001(2)
		
		num = -8; // 11111000 (2)
		System.out.println((byte)(num >> 1)); // 11111100(2)
		System.out.println((byte)(num >> 2)); // 11111110(2)
		System.out.println((byte)(num >> 3)); // 11111111(2)
	}
}

4
8
16
6
3
1
-4
-2
-1