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

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

이때 모두 알고있듯이 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

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

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

7. 이렇게 반복합니다.


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

int array[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int max = 10; int temp; int randValue; for(int i = max; i > 1; i--) { // 임의 숫자 추출 randValue = rand() % i; // 값 교체 temp = array[randValue]; array[randValue] = array[i-1]; array[max-1] = temp; }

 


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

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

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

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

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


[완성된 최종 알고리즘]

#include <iostream> #include <time.h> using namespace std; char * music_array[10] = { "1. 애국가", "2. 인생", "3. 소주한잔", "4. 밥만 잘 먹더라", "5. GEE", "6. 태양을 피하는 법", "7. 하루하루", "8. 너 말야", "9. 어쩌라고", "10. 비밀" }; char randIndex[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int currentPos; char* random() { static int suffle_pos = 10; // 한번 전체가 재생되었으면, 다시 처음부터. if(suffle_pos < 1) { printf("\n[전체 1회 재생완료]\n\n"); suffle_pos = 10; } // 랜덤하게 하나씩 뽑는다. int randValue = rand() % suffle_pos; currentPos = randIndex[randValue]; randIndex[randValue] = randIndex[suffle_pos-1]; randIndex[suffle_pos-1] = currentPos; suffle_pos--; return music_array[currentPos]; } char* sequence() { if(++currentPos > 9) { currentPos = 0; } return music_array[currentPos]; } int main(void) { srand((unsigned)time(NULL)); printf("=============== 랜덤 재생 ============\n"); for(int i = 0; i < 23; i++) { printf("%s\n", random()); } printf("=============== 순차 재생 ============\n"); for(int i = 0; i < 10; i++) { printf("%s\n", sequence()); } return 0; }

  





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