#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void printRandRange(int N){
int i, tmp, *memo;
srand(time(NULL));
memo = (int*)malloc(sizeof(int)*N);
for(i=0;i<N;i++){
memo[i] = 0;
}
for(i=0;i<N;i++){
do{
tmp = rand()%N;
}while(memo[tmp]);
memo[tmp] = 1;
printf("%d : -> %d\n", i+1, tmp+1);
}
free(memo);
}
int main(void){
int N;
scanf("%d", &N);
printRandRange(N);
return 0;
}
//나왔던 수 저장 안하고 하는 방법 존재?
질문자체가 개십병신임. 무슨마법을 원하는것도아니고
코드보면 랜덤으로 N개의 숫자를출력하는데 이떄 랜덤한방식이라서 재수가없으면 이미출력햇는데(memo에기록되잇는데) 연속으로게속나오는경우 시간복잡도가 여기서늘어나서 프로그램의 속도가 안좋아질수있음. 따라서 질문은 다음과같이바뀌어야된다고봄 -> 어떻게해야 충돌을줄여서 평균시간복잡도를 줄일수있을까요?
파이썬엔 s = random.sample(range(1, N+1), N) 이런게 있으니까 뭐...
이거 비슷한거 예전에 100만개인가 까지 돌려 봤는데 바로 됐던걸로 기억남.
니가말하는파이썬함수가 뭔진모르겟지만, 그건 그냥 랜덤한수를 100만개생성해주는거같은데? 시발 너 내말이해못함?
니가말한함수찾아보니까 랜덤한수를 1번만출력해주는거맞네 ㅋㅋ 근데 100만개너엇는데 바로나왓다매? 그럼 내가위에서말한거처럼 충돌을줄여서 시간복잡도를 높인거라고볼수잇음
uniform shuffle 알고리즘 찾아보셈. 간단함
저새끼 낙값하네 ㄹㅇ. 1~N까지의 랜덤한 수를 한번씩 출력하는 방법을 물어보길래 이러한 c 코드가 있다고 적어 줬고 파이썬엔 random.sample(range(1, N+1), N)을 이용해서 한라인으로 할 수 있다 그리고 100만 이하의 수에서 작업시간이 신경 써줄 필요가 없다 말했는데 시발 너 내말이해못함? 이지랄 하고 있네 내가 니한테 욕먹어 가면서 까지 코드 올려야 하냐 병신새꺄
진짜개병신이내;; 니가저파이썬함수코드 까봣냐?? 까보고말한거?? 저안에서 충돌검사해서 100만개이하가 바로나온건지, 아니면충돌검사안햇는데도 100만개이하가나온건지 니가코드까봣냐고 ㅋㅋ 아니면 저코드로 100만개돌려서 시간체크해보던가ㅅㅂ아;; 그리고 저걸개선하고싶다면 내가말한거처럼 충돌이덜나게끔하면서 + 랜덤하게유지되야함(충돌피하려고 랜덤의 의미가꺠지면안됨)
세상 참 힘들게 사네. 표준함수에 shuffle이란게 있음. 정확히 "병신아"가 원하는걸 최적으로 구현해 냄. shuffle로 100만개 돌려보니 내 후진컴으로 0.01초 밑으로 돌아가네.
memo가 과거에 등장했는지 기록하기때문에 bool을 이용해서 메모리 사용량을 1/8로 줄여줄수 있고, 초기화는 memset을 쓰는게 좋음. 하지만 이런 접근보다는 1~N까지 숫자를 저장하고 셔플한다음 출력하는게 더 좋은 방법이긴 하지만 rand()함수를 호출하기때문에 N이 큰 수라도 비교적 빨리 끝날수 있음. 왜냐하면 rand()함수 자체가 이미 수학적으로 상당히 최적화 되어있기 때문임.