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

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

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

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


 0 1

이렇게 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

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

 0 1

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

 0 1 9 3

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

 0 1 9 3

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

 0 1 9 8 7 3

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

 0 1 9 8 7


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

 0 8 9 1 7 3

7. 이렇게 반복합니다.


코드로 나타내면 아래와 같습니다.

 


이 방식의 문제점은 무엇일까요?
바로 전체를 일단 섞은 후에야 랜덤한 값을 가져올 수 있다는 것입니다.

지금처럼 0~ 9가 아닌 0~ 100 이라면. 먼저 100개를 모두 셔플 하고나서 6개 숫자를 가져올 수 있다는 말입니다.
그럼 어떻게 하면 될까요?

간단합니다.
앞에서 6개가 아니라 뒤에서 6개를 가져오면 됩니다.
이렇게하면 처음부터 모두 셔플을 할 필요가 없어지죠. 
그때그때 필요할때마다 하나씩 꺼내서 셔플을 하면 됩니다.

자, 이제 음악 플레이어에서 사용할 셔플 알고리즘이 완성되었습니다.
더 이상의 설명은 필요가 없을것으로 생각하여, 코드로 대신하도록 하겠습니다.

random() 은 랜덤하게 음악을 선곡하며, sequence() 는 순차적으로 음악을 선곡한다고 생각하시면 됩니다.
예제에서는 처음 23개의 곡은 random 재생을 하고, 이후에 순차재생으로 사용자가 변경했다는 가정하에 재현한 것입니다.


[완성된 최종 알고리즘]
  





이상으로 포스팅을 마칩니다.




 

'개발관련' 카테고리의 다른 글

음악 랜덤재생에 유용한 셔플(suffle) 알고리즘  (2) 2011.10.08