lhc101020   7년 전

1.merge sort로도 구현해보고

2.같은 숫자가 없어서 bool array만들어서도 구현해봤는데 둘다 시간초과네요 ㅠㅠ


1-1.merge sort같은 경우에는 merge가 O(n)이어야 전체 복잡도가 nlogn으로 나오는 걸로 알고있는데, 제 알고리즘이 잘못구현한건지 아니면 다른 곳에 문제있는지 봐주세요 ㅠㅠ

2-1. 이 알고리즘이 복잡도로 생각하면 sort보다 훨씬 빠를 것 같은데 아닌가요??




topology   7년 전

cin을 그냥 사용하시면 매우 느립니다. std::ios::sync_with_stdio(false); 를 한줄 입력하고 다시 시도해보세요.

lhc101020   7년 전

죄송한데... 정확히 어떤걸 하시라는 건지 잘 모르겠습니다 ㅠㅠ 저 statement를 어디다가 집어넣어야하나요??

topology   7년 전

main 함수 도입부에 넣으시면 됩니다. 예를 들면 아래와 같이요.

듣기로는 endl도 느리다고 합니다. endl 대신 '\n'을 사용하시는 것도 좋은 방법일 것 같네요.

lhc101020   7년 전

감사합니다. 가르쳐주신대로 바꾸니 맞았습니다. 혹시 저 statement가 어떤것을 의미하는지 가르쳐주실 수 있나요???

topology   7년 전

sync_with_stdio는 iostream 라이브러리와 stdio 라이브러리를 synchronize 해주는 함수입니다. 즉 cin, cout과 printf, scanf를 섞어 쓸 수 있습니다. 다만 이 경우 속도가 느려지게 되죠.

싱크로 옵션은 default가 true입니다. false 또는 0을 매개변수로 넘겨주면 싱크로를 꺼주게 되고 순수한 cin, cout의 속도로 입출력을 할 수 있게 됩니다. (몇몇 사람들의 실험에 따르면 오히려 이게 printf scanf보다 빠르다고 하네요) 이 경우 stdio 라이브러리의 입출력 함수들과 섞어 쓰면 좋지 않은 일(?)이 발생할 수 있습니다.

자세한 것은 다음 페이지를 참조해 보세요.

http://www.cplusplus.com/refer...

http://stackoverflow.com/quest...

lhc101020   7년 전

정말 감사합니다 많이 배우고갑니다

댓글을 작성하려면 로그인해야 합니다.