여러분께서는 중복되지 않는 숫자를 어떻게 생성하시나요?

효율은 잘 모르겠구요.

말씀대로 어떤 것을 뽑았는지 표시할 수도 있지만, 한 번 뽑은 것을 배열의 가장 끝과 바꾸는 방법도 있죠.

1. 범위가 1~N이라면 N개의 배열을 잡고,
2. 차례로 숫자 넣어둔 뒤에,
3. 임의로 뽑고
4. 뽑은 수는 가장 뒤에 수(index N에 위치한)와 바꾸고,

다시 3으로 가서 뽑되, N-1의 범위에서만 뽑는거죠. 한 번 뽑은 수는 무시하고요. 혹시 연속으로 같은 index를 집더라도 다른 수를 얻겠죠. 마지막 index에 있었던 녀석과 바꾸었으니까요.

이 말이 위에 있는 알고리즘과 본질적으로 같은 의미입니다. 즉, 1부터 N까지의 숫자 중 겹치지 않는 것을 뽑는다면 1부터 N까지의 숫자가 차 있는 배열을 뒤섞은 다음에 순서대로 뽑는데, j0nguk 님께서 소개하신 것은 뒤섞으면서 바로 바로 뽑는 방법이 되겠지요.

위와 같이 O(N)의 시간 복잡도로 배열을 뒤섞는 방법을 Knuth shuffle이라고 합니다. Donald Knuth의 이름이 여기서도 등장하는 군요.

- 토끼군

중복된 수가 있는지 검사하는 루틴이 들어간다면 효율이 굉장히 떨어지게 됩니다. 애초에 중복해서 뽑지 않는것이 가장 바람직하죠. 극단적인 확률로 영원히 수를 뽑아내지 못할수도 있습니다. 0에 가까운 확률이지만요. 무조건 뽑을수 있다와 확률적으로 뽑을수 있다의 차이랄까요?

처음에 올리신 방법으로 한번만에 4자리 정수를 뽑아낼 확률은 0.5입니다. 한번만에 뽑아낸다고 해도 다른 알고리즘보다 4번의 비교연산이 들어가기 때문에 느립니다. 물론, 간단한 프로그램이라면 체감할정도는 아닙니다. 토끼군님께서 올리신건 처음 올리신것과 같은 문제를 해결하는 방법입니다. (0~9에서 중복하지 않고 무작위로 4개를 뽑아낸 순열, N=10일때의 특정한경우)

저... 죄송합니다만. 섞은다음에 필요한만큼 뽑아내는것에서 섞는건 어떻게 구현하나요?? 알고리즘 자체는 굉장히 쉽게 이해되는데.. 의사코드로 어찌 구현해야할지 모르겠네요.

10개의 숫자를 가질수 있는 배열에 0 ~ 9를 넣는다.
임의의 개수만큼 섞는다.(아래 반복)
	0~9중 임의의 수 2개를 구한다.
	구한 두 숫자에 해당하는 2개의 배열을 바꾼다.
필요한 개수의 수를 배열에서 차례대로 가져온다.

int	aRanderm[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int	loop_cnt = rand() % MAX_LOOP;
for(int i = 0; i<loop_cnt ; ++i)
{
	int	first = rand() % 10;
	int	second = rand() % 10;
	swap(aRanderm[first], aRanderm[second]);
}

for(int i = 0; i<NUMVER_CNT ; ++i)
{
	cout << aRanderm[i] ;
}

cout << endl;

조인시 위키: article_random
를 참고해 보시면 도움이 될 것 같네요.
random(), srandom(), /dev/random 등에 대해서.. 상당히 충실히 설명하고 있는 문서 입니다.

0~9999 정수를 1개를 생산하든 1만개를 생산하든 필요한 배열의 크기는 10입니다.(10진수이기 때문에)
제가 배열의 크기와 메모리 관계를 잘 몰라서 그러는데 위에서 하신것처럼 공간 하나의 크기가 4바이트라면 총 필요한 공간은 40바이트입니다.

주제와 같은 문제들은 보통 이번주에 사야할 로또복권의 번호를 알려주는 프로그램에 많이 사용됩니다. espoirgod 님께서 내주신 문제는 로또의 번호가 1~10번(10번은 0과 같습니다.)까지 있을때, 4개를 고르는 방법의 가지수.
즉, 로또 4/10 게임에서 구매자가 OMR카드를 칠하는 방법을 구하는 것과 동일합니다.

임의의 수를 랜덤하게 뽑아서 이미 나온것과 비교하는 것은 실제로 4개 이런것을 추출할때는 별로 문제가 되지 않습니다.

그러나, 골라야할 번호와 고르는 개수가 똑같을때는 문제가 생깁니다. 즉, 로또 45/45와 같은 경우에는 번호를 골라가면 골라갈수록(45번째 번호를 고르는것에 가까워질수록) 뽑지않은 번호를 고를 확률이 내려갑니다. 즉, 마지막 번호를 고를 확률은 1/45입니다.

만약 로또 10000/10000을 해야한다면? 마지막 확률은 1/10000 이고, 그 직전은 2/10000 이고... 무한루프에 빠지게 될 가능성이 짙습니다.
그래서 위와 같은 알고리즘은 사용하지 않는것이 좋습니다.

메모리 부족이 문제되신다면 M$社처럼 사용자에게 시스템 업그레이드를 권장하시면됩니다;; 털썩;;