45개중 6개의 번호를 알려주는 알고리즘을 생각해 보자.
1. 6개의 빈칸을 만든다.
2. 6개의 칸 중 가장 처음 만난 빈칸에 1~45사이의 임의의 정수를 넣는다.
3. 6개의 칸에 중복된 것들이 있나 없나 검사하고, 중복된 것이 있으면 지운다.
4. 2번으로 돌아가서 반복. 6개의 칸이 모두 차 있으면 종료.
가장 간단한 알고리즘인데 2중 반복구문을 써야 하니까 아무래도 효율성이 떨어지지 싶다.
여기에 내가 제안한 알고리즘은 다음과 같다.
0. 1부터 45중 6개를 골라서 만들 수 있는 모든 패턴을 미리 생성해서 기록한다. 이건 26!과는 달리 약 100메가바이트 정도의 작은 용량을 차지하므로 미리 해둘 수 있다. 이 때 기록에 인덱스를 만드는데, 1부터 8145060이 적당할 것이다.
1. 1부터 8145060사이의 임의의 정수를 선택한다.
2. 선택된 정수에 해당하는 인덱스로 찾아가서 로또 번호를 고르면 된다.
이건 저장공간이 많이 필요해서 그렇지 일단 계산만 해두면 상수시간 내에 계산할 수 있는 알고리즘이 된다.
저장공간이 필요하지도 않은 매우 간단한 알고리즘이 있는데, 다음과 같다.
1. “2, 11, 21, 31, 41, 43″을 출력한다.
로또 번호는 뭘 고르더라도 당첨될 확률이 같으므로, 굳이 프로그램에서 난수를 생성할 필요 없이 로또 추첨을 기다리면 추첨할 때 난수가 생성되므로 알고리즘이 매우 간단해진다.
(https://kldp.org/node/118661
왜 그런지는 이 글을 참고바람.)
장난치지 말고 1~n의 정수중에서 k개를 겹치지 않게 선택해주는 그럴듯한 알고리즘을 만들어달라고 한다면 다음과 같다.
1. k개의 빈칸을 만든다.
2. 1과 n-k 사이에 있는 임의의 정수를 선택한다. 이것이 첫번째 수이고, n1이라고 하자.
3. (n1)+1과 n-k+1 사이에 있는 임의의 정수를 선택한다. 이것이 두번째 수이고 n2라고 한다.
…
이걸 k번 반복한다.
이 알고리즘은 결과물을 심지어 정렬된 상태로 출력시켜준다.
이런 알고리즘도 가능하다.
1. 1~7사이의 정수를 하나 선택한다. x라고 하자.
2. i=1~6까지 반복하여 i*x를 출력한다.
어차피 로또는 뭘 골라도 그게 그거라 별로 의미는 없다.
