중복 없는 난수 만들기, 혹은 카드 섞기 문제

출처 : http://conanoc.egloos.com/1046677

최 모 주임이 점심시간에 제기했던 재미있는 문제를 조금 찾아봤습니다.
문제는 "1에서 100까지의 숫자를 중복 없이 랜덤하게 뽑아내라" 이며, 이 문제는 "1에서 100까지 숫자를 잘 섞어라" 와 동일하기도 합니다.

인터넷에서 찾아보니 대략 밥먹을때 이야기나왔던 것들과 비슷하고, 정리하고 보니 현 선임이 이야기했던 방법이 가장 효율적인것 같네요.

1)
우선, 가장 쉽게 생각할 수 있는 잘못된(?) 방법은 이런 방법일 겁니다.
중복 안된 숫자가 나올때 까지 계속 랜덤을 돌리는 것이지요. 물론 MAX가 20정도면 이 방법도 유효할 수 있겠습니다만, 별을 다섯개 줄만한 답변은 아닌것 같네요.

2)
그 다음 생각할 수 있는 방법은 숫자들을 배열에 집어 넣고, 선택된 숫자들을 골라낸 후 랜덤값으로 배열의 인덱스를 선택하는 방식입니다. 다소 복잡하게 설명되어 있지만 이 방법.

3)
또 한가지 이야기된 방법은 중복된 숫자가 나오면, 중복되지 않은 숫자가 될때까지 단순 증가시키는 방법을 생각할 수 있는데, 이 방법은 잘 섞이지 않을 가능성이 있는것 같습니다. 그래서인지 이런 예제는 없더군요.

4)
가장 나이스한 방법은 "존나 간단하다"고 이야기하고 있는 이 방법인듯 합니다. 
기존에 나온 숫자들과 중복되는지 체크할 필요가 없고, 배열의 조작도 간편합니다.

1 /***********************************************
      2  중복되지 않는 랜덤프로그램                              
      3  작성일 : 03. 11. 12                                           
      4                                                                      
      5  설명:                                                             
      6  1~10까지의 숫자가 있다면 이것을 보통의 랜덤함  
      7  수를 사용해서 5개의 값을 뽑을때 중복되는 결과   
      8  를 볼수있다. 예를 들어서 5개의 결과값이 1,3,      
      9  1,9,10 이렇게 나왔을때 여기서의 중복된 값이      
     10  1이 2번이나 나오게된것이다. 우리가 원하는 결   
     11  과는 씨드값이 중복되지않는 랜덤값이다. 그것이 
     12  아래의 소스코드를 분석하면 나온다.                 

( 존나 간단하다... swap 을 이용해서 바뀌치기 하는건 단지 배열의 index 뿐이다...

왜냐면 중복 없는 값들의 배열 index 만 바뀌주기 때문~ ) 

1 2 3 4 5  라는 중복 되지 않는 값들을 배열 arr[5] 짜리에 순서대로 넣어놓는다.
그리고 rand() 함수를 써서 0 ~ 4 범위값을 구해서 1씩 증가하는 index 값과
rand()로 구한 값을 서로 바뀌치기 해준다. 

1 2 3 4 5
index = 0
rand_index = 3 

4 2 3 1 5 

index = 1
rand_index = 4 

4 5 3 1 2 

index = 2
rand_index = 1

 4 3 5 1 2

 

이런식으로 index = 4 일때 까지 1씩 증가하면서 rand_index 값과 바뀌치기 해준다.

void Random(int* pSrcBuf, int iStartRange, int iEndRange, int iCount)
{
 // pSrcBuf에 iStartRange에서 iEndRange만큼 범위의 값을 iCount갯수만큼 채워넣는다.  
 for(int iIdx=iStartRange; iIdx<iEndRange; iIdx++)
  pSrcBuf[iIdx] = iIdx;

 Sleep(1000);
 srand((unsigned)time(NULL)); 

 int rana;
 int iRange = iEndRange - iStartRange;
 for(int iIdx=0;iIdx<iRange; iIdx++)
 {
  rana = iIdx+(rand()%(iRange-iIdx));
  int prev;
  prev = pSrcBuf[iIdx];
  pSrcBuf[iIdx] = pSrcBuf[rana];
  pSrcBuf[rana] = prev;
 }
}

1 ~ 3번 방법은 자주 사용하던 방법이고 나같은 경우는 평균적으로 두가지 방식을 주로 사용한다.
하나는 소팅가능한 stl자료구조(list와 같은)에 1~100까지 넣고 렌덤으로 하나씩 가져 오는 것이다.
소팅되어 범위가 줄어드는데 줄어든 범위를 넘는 영역의 것을 가져오려 할 때만 첫번째걸로 대체해 주면 된다.

또다른 방법은 3번과 거의 흡사한 방식이다.
그래서 패스.

4번 방식은 ...흐음...좋군. (--)(__) 좋아~.