jyh305   4년 전

2493 탑 문제를 상단에 있는 코드대로 풀었는데 계속 시간초과가 나서 고민하다가

정답을 검색해 보았습니다. 거기서는 다른 부분이 벡터에 값을 미리 다 받아놓고 처리를 하는 것을 보고

제가 작성했던 코드에 탑의 높이에 해당하는 부분만 벡터에 미리 받아놓고 처리를 했더니 통과가 되네요

(참고로 처음 작성한 코드에 cin, cout 대신 scanf, printf도 사용해 보았으나 똑같이 시간초과가 났습니다.)

저는 오히려 처음에 벡터나 다른 배열에 받아서 처리를 하면 일단 기본적으로 두번 순회하기 때문에 더 걸릴 것이라 생각하여 윗부분의 코드로 작성했습니다.

그런데 오히려 시간초과가 나서 N의 최대수임 500,000 을 가정하여 최악이 아니라 난수 발생으로 시간을 쟀더니

윗 코드는 1700ms 가 나오고 아래 코드는 1380ms 정도가 나옵니다.

실질적으로 처리하는 부분인 for(while) 문은 두 코드 모두 동일하다고 생각합니다. 다른 점은 단순히 미리 배열을 받아 놓았는지의 차이라고 생각하는데 정확히 무엇 때문인지 알 수 있을까요??

+ 질문 수정 

cin, cout대신 scanf, printf로 하면 처음 코드도 통과되는것은 확인했습니다만

아래코드는 제가 생각했을 때 시간이 더 걸릴것 같은데 아래코드는 cin, cout을 사용했는데도 불구하고 통과가 되는데 이 부분이 궁금합니다.

결론: cin/cout 번갈아가면서 사용하면서 일어난 현상.

제가 이전에 테스트를 잘못 했었습니다.

cin / cout을 없애고 난수를 발생시켜서 테스트 했을 때 첫번째 코드가 더 빠른 것을 확인할 수 있었습니다. 

답변 달아주신 분 말대로 cin 과 cout을 번갈아 가면서 사용한 부분이 병목지점인 것 같습니다. 감사합니다.

pichulia   4년 전

scanf printf 사용하니까 150ms로 맞았습니다

jyh305   4년 전

아 그러네요 질문 수정했습니다.

cin, cout대신 scanf, printf로 하면 처음 코드도 통과되는것은 확인했습니다만

아래코드는 제가 생각했을 때 시간이 더 걸릴것 같은데 아래코드는 cin, cout을 사용했는데도 불구하고 통과가 되는데 이 부분이 궁금합니다.

pichulia   4년 전

당장 떠오르는 차이점은 cin 1번과 cout 1번씩을 N번 수행한 것과 cin N번 후에 cout N번이 더 빠르다는 점인데.. 

자세히는 모르겠지만 현재 코드에서 제일 병목인 부분인 cin/cout을 번갈아가면서 사용함으로 인해서 발생하는 cache miss 현상이지 않을까 싶습니다. 자세한건 구글아죠씨한테 물어보는게 좋지만.. 뭐라고 물어봐야할지 모르겠네요ㅠ

jyh305   4년 전

@pichulia님 감사합니다.

cin 과 cout을 번갈아 사용하는 것이 병목 지점이 될 수 있군요.

이후 내용은 더 찾아 보도록 하겠습니다. 감사합니다!

jyh305   4년 전

cin / cout을 번갈아 사용한 부분이 문제가 확실한 것 같습니다.

이전에 잘못 테스트를 했었고 다시 테스트를 해보니

두 코드 모두 cin을 난수 발생해서 값을 주는 것으로 바꾸고

cout을 생략했더니 확실히 처음 코드가 더 빠른 것을 확인했습니다.

감사합니다.

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