1655번 - 가운데를 말해요
해당 작업의 필요성을 설명하는 빠른 A+B 문제가 있습니다. 이 문제에 설명이 있으니 푸실 것을 권장합니다.
공통적으로 시간복잡도 면에서 핵심 로직이 따라준다 하더라도 입력을 받는 작업은 기본적으로 연산이 비싸며, 이에 따라 주어지는 데이터의 양이 너무 많으면 입력을 받는 과정 그 자체에서 시간을 너무 많이 소모해 시간 초과로 이어지기도 합니다. 그렇기 때문에 입력량이 많으면 해당 코드가 필요하며, 입력량이 적으면 해당 코드가 대체로 필요하지 않습니다. 경험상 입력으로 주어지는 항목의 개수가 몇 만개 이상이라면 웬만해서 필요합니다.
시간복잡도와 연산 횟수를 따져보는 것도 중요하지만 때로는 연산 하나하나가 비쌀 수 있다는 점 역시 유의해주셔야 할 것 같습니다.
풀이가 극단적으로 복잡하고 긴 다이아, 루비 문제가 아니라면 알고리즘 문제를 푸는 코드에서 가장 시간이 많이 걸리는 부분은 거의 무조건 실제 로직이 아닌 입출력입니다. 입출력에 구애받지 않고 로직에만 집중하며 코딩을 하려면 fast I/O 처리는 일단 해놓고 본다(인터랙티브 제외)는 생각이 맞습니다.
그런데, fast I/O 처리를 하지 않았을 때 주로 문제가 되는 상황은 cin과 cout이 빈번하게 교차하여 버퍼를 과도하게 flush시킬 때입니다. cin과 cout이 교차하는 횟수를 줄일 수 있다면 fast I/O 처리를 하지 않아도 괜찮은 경우도 많습니다. 가령 이 문제에서는 매번 즉각적으로 답을 출력하지 말고 vector에 담아놨다가 마지막에 몰아서 출력하면 fast I/O 처리를 하지 않아도 됩니다.
댓글을 작성하려면 로그인해야 합니다.
jhwon1009 5달 전 0
주로 C++ 사용해서 알고리즘 문제를 풀고 있는데요
그동안 알고리즘 문제를 풀면서 어차피 로직만 올바르다면 cin, cout 속도를 굳이 높이지 않더라도 충분히 정답을 낼 수 있다고 생각했고, 또 시간 초과로 틀렸을 때 cin, cout 속도를 높인다고 통과된 경험이 없었기에 일절 사용하지 않고 있었습니다
그런데 이 문제는 한참을 고민하다가 도저히 더 나은 방식이 떠오르지 않아서 시험 삼아 적용해봤더니 통과가 되네요
혹시 우연히 통과된 것뿐이고 C++로 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 없이도 이 문제를 맞출 수 있다면 가르쳐주셨으면 좋겠습니다!