굳건하게

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

오늘은 자바 랜덤 난수 생성하는 2가지 방법에 대해서 포스팅해보겠습니다.

java.util.Random 클래스 이용

Random 클래스를 이용하면 여러 가지 자료형에 대해서 랜덤 난수를 생성할 수 있습니다.

( import를 해줘야 사용할 수 있습니다. )

random.nextBoolean(); // true 아니면 false를 생성
random.nextInt(); // Int 형 범위에서 정수를 랜덤하게 생성
random.nextInt(N); // 0 ~ N - 1 범위에서 정수를 랜덤하게 생성
random.nextLong(); // Long 형 범위에서 정수를 랜덤하게 생성
random.nextFloat(); // 0.0F ~ 1.0F 사이에서 실수를 랜덤하게 생성
random.nextDouble(); // 0.0D ~ 1.0D 사이에서 실수를 랜덤하게 생성

 가장 자주 쓰이는 메소드는 nextInt() 함수로 매개변수를 통해 범위를 지정할 수 있습니다.

 물론, 이 난수들은 유사 난수(Pseudo Random Number)입니다. 즉, 컴퓨터가 가지고 있는 랜덤 알고리즘에 의해서 생성되는 난수들이지 정말 랜덤하게 생성되는 수는 아닙니다. 

package Hello;
import java.util.Random;

public class randomTest {
	public static void main(String args[]) {
		Random random = new Random();
		System.out.println("nextBoolean : " + random.nextBoolean());
		System.out.println("nextInt : " + random.nextInt());
		System.out.println("nextInt : " + random.nextInt(100));
		System.out.println("nextLong: " + random.nextLong());
		System.out.println("nextFloat : " + random.nextFloat());
		System.out.println("nextDouble : " + random.nextDouble());
	}
}

// Console
nextBoolean : true
nextInt : 540532811
nextInt : 15
nextLong: -1389414493932819308
nextFloat : 0.20302159
nextDouble : 0.44444974642727286

java.lang.Math 클래스 이용

 Math 클래스는 java.lang 패키지에 있으므로 별도로 import 할 필요는 없습니다. 또, Math 클래스의 random() 메소드는 Static 메소드이므로 객체를 생성하지않고 사용할 수 있습니다.

 Math.random() 메소드는 0.0D ~ 1.0D 난수를 발생합니다.

package Hello;

public class randomTest {
	public static void main(String args[]) {
		System.out.println("Math 클래스 난수 : " + Math.random());
	}
}

Math 클래스 난수 : 0.9956712501922751

 그럼 Math.random() 함수를 이용해서 0 ~ 9 사이의 숫자를 랜덤하게 얻고 싶으면 어떻게 해야 할까요?

package Hello;

public class randomTest {
	public static void main(String args[]) {
		System.out.println("Math 클래스 난수(0~9사이 정수 난수발생) : " + (int)(10*Math.random()));
	}
}

 다음과 같이 10을 곱해주고 강제 형 변환을 통해 소수점 뒤의 숫자들을 날려주면 됩니다.

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

[ 알고리즘풀이 ]

 Union-Find 와 자료구조 Map을 이용하면 문제를 해결할 수 있습니다. 이름이 Input 으로 들어오면, Map에 없다면 <이름, 번호>를 Map에 Insert 해주고 이 번호를 이용해 Union-Find를 하면 된다. 집합의 크기를 출력해줘야되므로, 그냥 유파가 아닌 WeightedUnion-Find 기법을 활용했다.

#include<iostream>
#include<map>
#include<string>
#include<cstring>

using namespace std;

int p[100000];

int find(int num) {
	if (p[num] < 0)
		return num;
	return p[num] = find(p[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return;

	if (p[pNum1] < p[pNum2]) { // i 가 더 많음.
		p[pNum1] = p[pNum1] + p[pNum2];
		p[pNum2] = pNum1;
	}
	else{
		p[pNum2] = p[pNum1] + p[pNum2];
		p[pNum1] = pNum2;
	}
	return;
}

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

	int t;
	cin >> t;
	while (t--) {
		memset(p, -1, sizeof(p));

		int F;
		cin >> F;
		int count = 0;
		map<string, int> list;
		string input1, input2;
		for (int i = 0; i < F; i++) {
			cin >> input1 >> input2;
			if (list.count(input1) == 0) {
				list.insert({ input1, count });
				count++;
			}
			if (list.count(input2) == 0) {
				list.insert({ input2, count });
				count++;
			}
			merge(list.find(input1)->second, list.find(input2)->second);
			cout << -p[find(list.find(input1)->second)] << '\n';
		}
	}
	return 0;
}

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

[ 주접주접 ]

 처음에는 DFS 탐색을 통해서 startNode에서 시작해서 탐색을 진행하며 경로 중 가장 작은 cost를 매개변수로 넘겨주며 endNode까지 탐색이 끝나면 답을 갱신하는 방법으로 알고리즘을 구현했다. 당연히, 시간 초과에 직면했고 그 후 갱신된 답보다 작거나 같은 경우에는 탐색을 중간에 종료하며 DFS 컷팅을 시도했으나 이 알고리즘도 시간 초과에 직면했다... 그러다 Union-Find 기법으로 문제를 해결할 수 있다는 글을 보았고 Union-Find로 A노드에서 B노드로 경로가 있는지 없는지 바로 체크할 수 있다는 점을 이용해서 문제를 해결했다.

[ 알고리즘풀이 ]

 우리는 startNode에서 endNode로 경로를 만들면되는데, 어차피 cost가 작은 간선보다는 cost가 큰 간선들로 경로를 만들고 싶다. 따라서, cost가 큰 간선부터 탐색하며 startNode와 endNode 가 경로가 생긴 순간 탐색을 종료하면 된다. 이때, startNode와 endNode가 경로가 생겼는지 안생겼는지는 Union-Find를 이용해서 쉽게 해결할 수 있다.

[ 예시 ]

1)

 cost가 가장 큰 간선 4 - 5 를 가지고와 4와 5를 Merge 합니다. 즉, 4번 5번 노드 사이에는 경로가 존재합니다. { 4, 5 }

2)

 다음으로 큰 간선인 5 - 6 을 가지고와 5 와 6을 Merge 합니다. { 4, 5, 6 } 이 한 집합이 되므로 4, 5, 6 사이에는 서로 경로가 존재합니다.

3)

 그 다음으로는 1 - 3 을 가지고와 1과 3을 Merge 합니다. { 1, 3 } / { 4, 5, 6 }

4)

 그 다음으로는 0 - 2 를 가지고와 0과 2를 Merge 합니다. { 0, 2 }  / { 1, 3 } / { 4, 5, 6 }

5)

 그 다음으로는 2 - 6을 가지고와 2와 6을 Merge 합니다. { 0, 2, 4, 5, 6 } / { 1, 3 }

6)

 그 다음으로는 1 - 2를 가지고와 1과 2를 Merge 합니다. { 0, 1, 2, 3, 4, 5, 6 }

이때, 3과 5가 같은 집합으로 합쳐졌으므로 3 - 5 사이에 경로가 존재하게 되므로 함수를 종료하면 됩니다.

#include<iostream>
#include<queue>

using namespace std;

int p, w, root[1000], startNode, endNode, x, y, z;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1);
	int pNum2 = find(num2);
	if (pNum1 != pNum2) {
		root[pNum1] = pNum2;
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> p >> w >> startNode >> endNode;
	for (int i = 0; i < p; i++)
		root[i] = i;

	priority_queue<pair<int, pair<int, int>>> q;
	for (int i = 0; i < w; i++) {
		cin >> x >> y >> z;
		q.push({ z, {x, y} });
	}
	while (!q.empty()) {
		pair<int, pair<int, int>> cur = q.top();
		q.pop();

		merge(cur.second.first, cur.second.second);

		if (find(startNode) == find(endNode)) {
			cout << cur.first << '\n';
			break;
		}
	}
	return 0;
}

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

[ 알고리즘풀이 ]

 BFS 탐색과 Union-Find 로 문제를 해결할 수 있습니다.

1) 먼저, 입력 받은 문명지들마다 Numbering 을 해줍니다.

2) 입력 받은 문명지들을 순회하며 주변에 다른 문명이 있다면 Union-Find 를 통해 문명을 결합합니다. 처음에는 K개의 문명이 있지만, 문명을 결합할 때마다 문명의 개수를 K-- 를 통해 낮춰줍니다.

3) 문명의 개수가 1인지 체크하고, 1이라면 종료합니다.

4) 1이 아니라면, 문명지들을 다시 주변으로 전파해줍니다. 그 후, 2번부터 다시 반복합니다.

// 문제의 핵심은 문명을 먼저 결합하고, 그 뒤에 전파해야됩니다! 

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

int N, K, x, y, root[4000000];
int map[2000][2000];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

queue<pair<int, int>> q1, q2;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

bool merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return false;
	root[pNum1] = pNum2;
	return true;
}

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

	cin >> N >> K;

	for (int i = 0; i < N * N; i++)
		root[i] = i;

	for (int i = 1; i <= K; i++) {
		cin >> x >> y;
		x--, y--;
		map[x][y] = i;
		q1.push({ x, y });
	}

	int ans = 0, curCivil = K;
	while (1) {
		// 문명 결합
		int qSize = q1.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q1.front();
			q1.pop();
			q2.push(cur);
			int x = cur.first, y = cur.second;

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] != 0) {
					bool check = merge(map[x][y], map[nx][ny]);
					if (check)
						curCivil--;
				}
			}
		}
		if (curCivil == 1)
			break;
		// 문명전파
		qSize = q2.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q2.front();
			q2.pop();

			int x = cur.first, y = cur.second;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] == 0) {
					q1.push({ nx, ny });
					map[nx][ny] = map[x][y];
				}
			}
		}
		ans++;
	}
	cout << ans << '\n';
	return 0;
}