머리쓰기/알고리즘

rand()사용, 그리고 중복되지 않게 뽑기(소스포함)

윈플. 2012. 2. 1. 14:49

흔히들 사용하는 랜덤함수.

1~25 사이의 수를 렌덤하게 꺼내려면            ----->    rand()%25 + 1   (+1의 차이)
0~24 사이                                                ----->    rand()%25

이렇게 사용을 합니다.

그렇다면 중복되지 않게, 중복되지 않게 하려면 어떻게 해야할까요??


보통 쓰는 방법은 rand()를 통해 나온 값을 지금까지 나온 값과 비교하여 이미 있는 값이라면... 다시 돌리는 방식입니다.

[순서도] 

1. rand() 사용
2. 비교              
-->(있을 경우) 다시 1로 
-->(없을 경우) 다음 단계
3.1 완료될 경우 종류.
3.2 아니라면 저장 후 다시 1로



이와 같은 경우, 실제로 소스로 구현해보면 아시겠지만.............. 무한루프에 걸릴 때도 생깁니다.


그래서 다음 방법을 소개합니다.
1 to 50, 또는 퍼즐 게임와 같이 중복되지 않게 배열에 집어넣거나 순서를 섞어야 되는 경우! 에 편하실겁니다.


순서대로 보시면..


(그림이 짤린 것 같지만 짤린게 아닙니다.)




[필요한 것들]
같은 크기의 배열.
배열의 크기를 저장하는 변수.
그리고 swap에 필요한 변수.


[C++ 소스]

(+) "greatest"님의 지적사항입니다. 
      그림으로 설명이 된 부분으로 코드가 매칭되지 않았습니다. 추후에 수정하겠습니다(__)

int main()
{
// 배열로 초기값(정렬 안 된 상태)
int temp_arr[25]={0,}, temp, index_size=24, n;
int i;

// 임시 배열 초기화
for(i=0; i<25; i++)
{
temp_arr[i] = i+1;
}
// rand()사용 중복되지 않게 만들기
for(i=0; i<25; i++)
{
n = rand()%(index_size+1);

// 마지막 index와 나온 index swap하기
temp = temp_arr[n];
temp_arr[n] = temp_arr[index_size];
temp_arr[index_size] = temp;
}
cout << "<rand()사용, 중복되지 않게 배열 초기화>" << endl;
// 결과 확인
for(i=0; i<25; i++)
{
cout << temp_arr[i] << " ";
}
cout << endl;

return 0;
}

혹시 잘못된 부분. 궁금점. 질문은 댓글로 피드백바랍니다.



'머리쓰기 > 알고리즘' 카테고리의 다른 글

마방진.  (0) 2011.12.23
백트랙킹(Backtracking) vs 욕심쟁이(Greedy)  (0) 2011.08.02
알고리즘 종류. (공부해야할 것들.)  (0) 2011.07.28
알고리즘.  (0) 2011.06.30