알고리즘 초보자입니다. 코드 실행 시간 관련하여 질문 드려도 될까요?

Question

안녕하세요 최근에 막 알고리즘 공부를 시작한 한 학생입니다.최근에 제가 문제를 풀면서 드는 고민은 제가 푼 풀이의 걸린 시간이 좀 큰 것 같다는 것입니다. 주로 백준에서 문제를 풀고 문제를 다 풀고 나면 다른 분들이 푼 풀이를 참고하는데 보통 걸린 시간이 두배정도 차이가 나는 것 같더라구요. 하지만 초보의 입장에서 걸린 시간까지 고려하며 문제를 풀자니 복기하는 시간까지해서 한 문제당 시간이 너무 많이 걸리는 것 같아 고민입니다. 지금 제가 주로 푸는 문제는 큐 스택 힙 등 기본 자료구조 관련 문제와 이제 막 DFS, BFS 문제 조금 풀기 시작했습니다. 제가 문제 하나하나를 풀며 이렇게 걸린 시간까지 고려하며 문제를 푸는 것이 장기적으로 좋을까요? 아니면 우선 많은 양의 문제들을 풀어보고 그 후 다시 최적화하는 연습을 하는게 좋을까요?그리고 번외로 제가 이번에 문제를 분석해보면서 제 풀이의 걸린 시간을 약 1초 정도 줄여보았습니다. 제가 궁금한 것은 알고리즘 문제 풀이에서 1초 정도면 얼마나 큰 차이인가요? 저는 지금 주로 파이썬 사용해서 풀고 있습니다.답변 주시면 정말 감사하겠습니다!

kiel · Answer

물리적인 실제 실행 시간 측정은 프로그램 언어, CPU, Memory, Disk 등의 영향을 많이 받습니다. 그래서 실행 시간을 측정하는 벤치마크의 경우 이런 실행 환경을 명시 합니다. 또한 실행 시 매번 동일한 결과가 나오지 않기에 평균값과 최대/최소 값을 명시합니다.즉 1초를 줄였다고 하셨는데, 그게 다른 컴퓨터에서는 2초가 줄어든 것일 수도 있고, 또 다른 실행 환경에서는 3초가 늘어날 수도 있습니다.특히 파이썬의 경우, 다른 언어보다 실행 시간이 상대적으로 느립니다. 파이썬으로 코딩테스트 문제를 풀면서 실행 시간에 신경 쓰는건 의미 없다고 보시면 됩니다.문제 풀이 서비스에서 Timeout 으로 Fail 이 나지 않는한 허용 범위의 해결 방식이라고 생각하시면 됩니다.

배고프고가난한백수 · Answer

실행시간도 당연히 신경쓰면서 푸셔야 합니다. 알고리즘 앞 부분에 계산복잡도 내용이 나오지 않나요? 알고리즘과 계산복잡도는 뗄 수가 없습니다. 채점할 때 언어의 실행시간 차이는 다 감안해서 채점합니다. 중요한 건 계산복잡도가 얼마가 나오느냐지 몇 초 나오냐가 아닙니다(언어마다 실행시간이 다르기 때문). 계산복잡도를 잘 잡으면 실행시간은 그에 따라서 나옵니다.계산복잡도를 무시하고서 진행한 풀이는 단지 중간과정에서 나온 산물일 뿐 장기적으로 보면 쓸모가 없습니다. 결론은 계산복잡도를 계속 고려하시면서 문제를 푸셔야 합니다.

알고리즘 초보자입니다. 코드 실행 시간 관련하여 질문 드려도 될까요?

2개의 답변

기술 목록