코딩 연습

배열 랜덤 순서로 섞기 (shuffle) 본문

알고리즘

배열 랜덤 순서로 섞기 (shuffle)

코딩중독 수악중독 2018.07.22 01:53

카드 게임을 만들려고 한다면 일단 카드를 섞어야 하는 기능이 있어야 하는데, 이것을 어떻게 할까 생각해 보았다.

처음엔 단순히 난수 생성을 해서 해결하면 되겠다는 막연한 생각을 했었는데, 막상 구체적인 방법에 대해서 생각해보니 난수 생성은 같은 수를 만들어 낼 수도 있기 때문에 기본의 배열의 순서만 랜덤하게 뒤바꾸는 작업에는 적절하지 않다는 것을 알게 되었다.

그래서 다음과 같은 방법을 생각하게 되었다.

1부터 10으로 이루어져 있는 길이 10의 배열 arr 의 순서를 임의로 바꾸는 경우를 생각해 보자.


1. 0부터 9까지의 정수들로 난수를 생성한다.

2. 생성된 난수에 해당하는 배열의 요소를 배열의 첫 번째 요소와 바꾼다.

    예를 들어, 난수에서 4가 생성되었다면, arr[4] 와 arr[0] 의 요소를 서로 바꾼다.

3. 1부터 9까지의 정수들로 난수를 생성한다.

4. 생성된 난수에 해당하는 배열의 요소를 배열의 두 번째 요소와 바꾼다.

     예를 들어, 난수에서 8이 생성되었다면 arr[8] 과 arr[1] 의 요소를 서로 바꾼다.

5. 2부터 9까지의 정수들로 난수를 생성한다.

6. 생성된 난수에 해당하는 배열의 요소를 배열의 세 번째 요소와 바꾼다.

    예를 들어, 난수에서 5가 생성되었다면 arr[5] 와 arr[2] 의 요소를 서로 바꾼다.

...


이렇게 해서 배열의 아홉번째 요소까지 바꾸게 되면 요소들이 임의로 바뀐 새로운 배열이 완성된다. 

이 과정을  C 언어로 구현하면 다음과 같다.

#include <stdio.h>
#include <time.h>    // time 함수가 포함되어 있는 헤더파일
#include <stdlib.h>  // srand, rand 함수가 포함되어 있는 헤더파일

// 배열을 프린트 해주는 함수
void printarr(int *arr, int num)
{
    for (int i=0; i < num; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 배열을 섞는 함수
void shuffle(int *arr, int num)
{
    srand(time(NULL));  
    int temp;
    int rn;
    for (int i=0; i < num-1; i++)
    {
        rn = rand() % (num - i) + i;    // i 부터 num-1 사이에 임의의 정수 생성
        temp = arr[i];
        arr[i] = arr[rn];
        arr[rn] = temp;
    }
}

int main(void)
{
    int num;
    int *arr;
    printf("Input size of array : ");
    scanf("%d", &num);    // 배열의 크기를 입력받음
    arr = (int *)malloc(sizeof(int) * num);    // 입력받은 배열의 크기만큼 메모리 할당
    for (int i=0; i < num; i++)
        arr[i] = i+1;    // 배열을 1부터 num 까지의 요소로 초기화
    shuffle(arr, num);
    printarr(arr, num);
    free(arr);
    return 0;
}


위 과정에서 srand 는 호출할 때 전달받는 인자를 기반으로 해서 난수를 초기화 시켜주는 역할을 한다.

rand 는 srand 로 잉해 생성된 값을 바탕으로 난수를 생성해 주는 역할을 한다.

time 함수는 인자값으로 NULL 을 넘기면 1970년 1월 1일 0시 이후부터 현재까지 흐른 시간을 초단위로 리턴해 준다.

rand() % (num - i) + i 라고 하면 생선된 난수를 num-i 로 나눈 나머지에 i 를 더해준 꼴이 되므로, 결과적으로 i 부터 num-1 까지의 임의의 정수를 생성하는 역할을 하게 된다. 


위와 같은 코드로 나온 결과는 다음과 같다.

Input size of array : 10
7 4 10 1 8 6 9 2 5 3