중복 없는 랜덤 정수 최적화 ( O(N) )

1학년 때 프로그래밍을 처음 배우면 꼭 한번씩 로또 번호 추첨기를 만들어본다.

이 때 보통 이미 뽑은 번호를 추첨하면 다시 추첨하는 식으로 코드를 짜는데 사실 이 코드는 정말 최악의 경우는 무한대이다.

 

이에 대해 최적화하는 경우를 생각해보았는데 인터넷에는 대부분 O(N^2)이어서 O(N) 알고리즘을 한번 소개해볼까 한다.

파이썬에는 random.sample() 이 이미 있으므로 C 기준으로 설명해보겠다.

 

알고리즘은 간단하다.

 

원래 배열이 1 2 3 4 5 6 7 8 9 10 이고, 0 ~ 9 의 정수 중 하나를 랜덤으로 뽑아 4를 얻었다고 가정하자.

그럼 arr[4] = 5 이므로 5를 추출하는 것인데

이 때 배열의 마지막 성분 10을 5 자리에 넣고 다시 랜덤 추출하고 이와 같은 방법을 매번 반복하는 것이다.

 

이렇게 하면 매 과정의 랜덤추출을 O(1)로 할 수 있으므로 N개의 랜덤 추출을 O(N)으로 할 수 있다.

 

아래의 코드가 이를 구현한 코드인데 C언어에서의 random추출 코드에 대한 이해를 위해 조금 더 부연설명을 하겠다.

stdlib.h 에 정의된 rand함수를 쓰면 된다.

rand함수는 0 ~ 32767 의 정수를 random으로 생성하기 때문에

rand() % x 를 하면 0 ~ (x - 1)의 정수를 랜덤으로 얻을 수 있다.

 

그러나 그냥 rand()를 하면 늘 일정한 수들을 뽑아낸다.

따라서 무작위의 시드값을 주기위해 코드의 시작에 srand(time(NULL)을 해주어야 한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
	int random = 0;
	int lotto[45] = { 0 };
	srand(time(NULL)); // 매번 다른 시드값 생성

	for (int i = 0; i < 45; i++)
	{
		lotto[i] = i + 1;
	}
	
	for (int i = 0; i < 6; i++)
	{
		random = rand() % (45 - i);
		printf("%d ", lotto[random]);
		lotto[random] = lotto[44 - i];  // 현재 범위의 마지막 값을 추출된 값으로
	}

	return 0;
}