C++ 학습/C++ 코딩인터뷰[5장]
[5. 배열] 5.16 균등하지 않은 임의의 숫자 생성하기
msugi
2025. 1. 22. 16:31
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include "Q5.h"
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
os << "[";
for (size_t i = 0; i < vec.size(); i++)
{
os << vec[i];
if (i != vec.size() - 1)
{
os << ", ";
}
}
os << "]";
return os;
}
|
cs |
|
|
// main에서 vector 형태로 출력하기위한 기본 셋팅
|
5.16 균등하지 않은 임의의 숫자 생성하기
n개의 숫자와 각 숫자의 확률 p0,p1,....p(n-1)이 주어지고, (단 확률의 모든 합은 1)
[0,1]사이의 숫자를 균등하게 생성하는 임의의 숫자 생성기가 주어졌을때, 주어진 확률에 따라 숫자 n개를 생성하시오.
이 문제는 실제로 어떤 숫자가 생성되는지는 중요하지 않다.
n개의 결과를 각각의 확률로 선택하고 싶을 뿐이다. 숫자의 확률이 다르다고 가정하면
[p0, p0 + p1], [p0 + p1, p0 + p1 + p2], [p0 + p1 + p2 , p0 + p1 + p2 + p3] [p0+... , ...+p(n-1)] 과 같이 구간을 잡고 문제를 풀면 된다.
일반적으로 n개의 구간값이 들어 있는 배열을 탐색하는데 걸리는 시간은 O(n)이다. 하지만 배열이 정렬이 되어있는 형태이므로 이진탐색을 사용하여 O(log n)의 시간복잡도로 나타낼 수 있다.
해당내용의 소스코드와 결과는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include<vector>
#include<random>
#include<numeric>
#include<algorithm>
int NonUniformRandomNumberGeneration(const std::vector<int>& values,
const std::vector<double>& probabilities)
{
std::vector<double> prefix_sums_of_probabilities;
std::partial_sum(cbegin(probabilities), cend(probabilities),
back_inserter(prefix_sums_of_probabilities));
std::default_random_engine seed((std::random_device())());
const double uniform_0_1 = std::generate_canonical<double,
std::numeric_limits<double>::digits>(seed);
const int interval_idx = std::distance(cbegin(prefix_sums_of_probabilities),
upper_bound(cbegin(prefix_sums_of_probabilities),
cend(prefix_sums_of_probabilities), uniform_0_1));
return values[interval_idx];
}
|
cs |
|
|
// 5.16 균등하지 않은 임의의 숫자 생성하기.cpp
|
|
1
2
3
4
|
std::vector<int>TestVec14 = { 10,20,30,40,50,60 };
std::vector<double>TestVec15 = { 0.9,0.02,0.02,0.02,0.02,0.02 };
std::cout << "5-16 " << NonUniformRandomNumberGeneration(TestVec14, TestVec15) << std::endl; //5-16
|
cs |
|
|
// main.cpp
|
