[ C++ 알고리즘 ] Shuffle algorithm

2023. 3. 11. 07:40ㆍ알고리즘

무작위로 요소를 여러 개 뽑을 때 같은 요소가 안 뽑히도록 할 수 있는 알고리즘을 알아보자

( 중복 제외 랜덤 요소 뽑기 )

 

 Shuffle 알고리즘

간단한 방법

 

1 ~ 10까지의 수 중에서 중복 없이 3개의 값을 출력해보자

[ 코드 ]

더보기

간단한 예제

#include <iostream>

using namespace std;

int main()
{
    srand((unsigned int)time(NULL));
	
    int nums[10];
    
    // 배열 안에 1~10까지의 값을 넣어준다
    for(int i = 0; i < 10; i++) {
        nums[i] = i + 1;
    }
    
    // 배열을 섞어준다
    for(int i = 0; i < 100; i++) {
        int randomIndex = rand() % 100;
        int randomIndex2 = rand() % 100;
        
        int temp = nums[randomIndex];
        nums[randomIndex] = nums[randomIndex2];
        nums[randomIndex2] = temp;
    }
    
    // 3개의 값 출력
    for(int i = 0; i < 3; i++) {
    	cout << nums[i] << "\n";
    }
}

 

이렇게 하면 1 ~ 10의 값 중에서 3개의 값을 출력할 수 있다.

 

 

 Fisher-Yates Shuffle 알고리즘

방법

  1. 1~n 까지의 숫자를 쓴다
  2. 지워지지 않은 숫자 중 임의 수 k를 고른다
  3. 낮은 쪽부터 세면서 아직 지워지지 않은 k 번째 숫자를 지우고 별도의 목록 끝에 넣습니다.
  4. 모든 숫자가 지워질 때까지 2번을 반복
  5. 3번에서 수를 넣어둔 별도의 목록이 최종 무작위 순열 결과가 된다

시간 복잡도 : O(n^2)

 

전과 같이 1 ~ 10의 값 중에서 3개의 값을 출력해보자

 

[ 코드 ]

더보기

방법 설명 밖에 없고 예제 코드가 없어서 임의로 적어봤다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    srand((unsigned int)time(NULL));

    vector<int> numList;
    vector<int> randomNums;

    // 배열 안에 1~10까지의 값을 넣어준다
    for (int i = 0; i < 10; i++) {
        numList.push_back(i + 1);
    }

    while (!numList.empty()) {
        int randomNum = numList[rand() % numList.size()];
        for (int i = 0; i < numList.size(); i++) {
            if (numList[i] == randomNum)
                numList.erase(numList.begin() + i);
        }
        randomNums.push_back(randomNum);
    }

    // 3개의 값 출력
    for (int i = 0; i < 3; i++) {
        cout << randomNums[i] << "\n";
    }
}

[ 코드2 ]

더보기

비슷한 느낌의 코드

피셔-예이츠 설명과는 다르지만 이게 더 나을 거 같다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    srand((unsigned int)time(NULL));

    vector<int> numList;
    vector<int> randomNums;

    // 배열 안에 1~10까지의 값을 넣어준다
    for (int i = 0; i < 10; i++) {
        numList.push_back(i + 1);
    }

    // 배열의 값중에서 무작위 수를 선택해서 다른 배열에 넣어준다.
    // 무작위 수를 지워준다.
    while (!numList.empty()) {
        int randomIndex = rand() % numList.size();
        randomNums.push_back(numList[randomIndex]);
        numList.erase(numList.begin() + randomIndex);
    }

    // 3개의 값 출력
    for (int i = 0; i < 3; i++) {
        cout << randomNums[i] << "\n";
    }
}

위의 코드는 위에서 설명한 피셔 에이츠 알고리즘과는 살짝 다르지만 내맘대로 적어봤다.

 

 Knuth Shuffle 알고리즘

피셔 에이츠 알고리즘의 최신버젼이라고 한다.

시간 복잡도 : O(n)

 

핵심 개념

  • 한쪽 끝(앞 혹은 뒤)부터 한자리씩 이동하면서 각 자리에 들어갈 요소를 랜덤하게 뽑음
  • 뽑는 요소는 전에 뽑히지 않았던 요소들
  • 랜덤하게 뽑힐 요소가 있는 목록을 줄여가면서, 기존에 뽑힌 요소를 배제함
  • 랜덤 함수가 O(1) 의 시간복잡도를 가지면, 전체 알고리즘은 O(n)

 

전과 같이 1 ~ 10의 값 중에서 3개의 값을 출력해보자

 

[ 코드 ]

더보기

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    srand((unsigned int)time(NULL));

    vector<int> numList;

    // 배열 안에 1~10까지의 값을 넣어준다
    for (int i = 0; i < 10; i++) {
        numList.push_back(i + 1);
    }

    // Knuth shuffle
    for (int i = 0; i < numList.size(); i++) {
        int randomIndex = rand() % (numList.size() - i) + i;

        int temp = numList[i];
        numList[i] = numList[randomIndex];
        numList[randomIndex] = temp;
    }

    for (int i = 0; i < 3; i++) {
        cout << numList[i] << "\n";
    }

}

 

 

Fisher-Yates Shuffle algorithm, Knuth Shuffle algorithm 둘 다 찾아보면서 봤는데

Fisher-Yates Shuffle algorithm을 Knuth Shuffle algoithm이라고 부르기도 한다는데

Knuth Shuffle algorithm도 Fisher-Yates Shuffle algorithm이라고 부르기도 한다고 함.

 

참고 자료

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

https://rosettacode.org/wiki/knuth_shuffle

https://github.com/SetCodesToFire/KnuthShuffle

https://m.blog.naver.com/PostView.naver?blogId=kiminhovator&logNo=220342175756&proxyReferer=

 

티스토리툴바