유리상자 속 이야기

음악 플레이어를 보면 대부분 랜덤재생 항목이 있습니다.

이때 모두 알고있듯이 random 함수를 사용해서 임의의 음악을 재생시킵니다.
그런데 이 랜덤 함수를 어떻게 써야 가장 효율적일까요?

먼저 가장 단순한 순서섞기(셔플) 알고리즘에 대해서 생각해 봅시다.
한때 유행하던 로또번호 추출기를 만들어 보죠.

본래 로또번호가 1~45 까지 있지만, 편의를 위해 0~9 까지 10개가 있다고 가정하겠습니다.

0

1

2

3

4

5

6

7

8

9

이렇게 int 배열이 있습니다.

[가장 단순한 알고리즘]
1. rand() % 10 를 통하여 0~ 9 사이 임의의 값을 추출합니다.
2. rand() % 10 을 통하여 0~ 9 사이 임의의 값을 추출합니다. 
3. 이렇게 6번을 합니다.

이게 과연 올바른 방법일까요?
문제가 있습니다. 중복된 숫자가 나올 확률이 있다는 사실입니다.

 
자, 그럼 수정해 봅시다.

[수정된 알고리즘]
1. rand() % 10 를 통하여 0~ 9 사이 임의의 값을 추출합니다.
2. rand() % 10 를 통하여 0~ 9 사이 임의의 값을 추출합니다. 만약 1에서 추출한 값과 동일하면 다시 뽑습니다.
3. 이렇게 6번을 합니다.

이 방법에도 문제가 있습니다.
가장 큰 문제는 비효율 적입니다.
중복된 숫자가 나오지 않을 때까지 6번을 반복해야 합니다.
만약 정말 운이 좋지 않다면, 6개의 숫자를 뽑기 위해서 10번을 넘게 rand() 를 해야 할지도 모릅니다.
정말정말 운이 없다면(미칠듯하게 재수가 없으면), 영원히 끝나지 않을지도 모릅니다.(무한히 계속 같은 숫자가 나온다는 가정)

사실 프로그래밍에 있어서 이렇게 시간을 예측할 수 없는 알고리즘은 좋지 않습니다.
6번만에 끝날지 1만번 만에 끝날지 전혀 예측할 수 없거든요.


자, 이제 제대로 된 알고리즘을 만들어 봅시다.

[재대로 된 알고리즘]

1. rand() % 10 을 통해서 0~ 9 사이의 값을 추출합니다.
2. 1에서 추출된 숫자와 10번째 숫자(위에서는 9)의 순서를 바꿉니다.
3. rand() % 9 를 통해서 0~ 8 사이의 값을 추출합니다.
4. 3에서 추출된 숫자와 9번째 숫자(위에서는 8)의 숫자를 바꿉니다.
5. 이렇게 rand() % 2 까지 반복합니다.
6. 앞에서부터 6개의 숫자를 읽습니다.

그림으로 설명드리면 아래와 같습니다.


0. 초기상태

0

1

2

3

4

5

6

7

8

9

1. rand() % 10 을 통해서 0~ 9 사이의 값을 추출합니다.
 ->3 이 나왔다고 가정합니다.

0

1

2

3

4

5

6

7

8

9

 2. 1에서 추출된 숫자와 10번째 숫자(위에서는 9)의 순서를 바꿉니다.
 -> 즉 3과 9의 자리를 교체합니다.

0

1

2

9

4

5

6

7

8

3

4. 3에서 추출된 숫자와 9번째 숫자(위에서는 8)의 숫자를 바꿉니다.
 -> 즉 7과 8의 자리를 변경합니다.

0

1

2

9

4

5

6

8

7

3

5. rand() % 8 를 통해서 0~ 7 사이의 값을 추출합니다.
 -> 1이 나왔다고 가정합니다.

0

1

2

9

4

5

6

8

7

3

6. 5에서 추출된 숫자와 8번째 숫자(위에서는 8)의 숫자를 바꿉니다.
 -> 즉 8과 1의 자리를 변경합니다.

0

8

2

9

4

5

6

1

7

3