인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다.

AA66님께서 질문하신 시간 복잡도와 문제 풀이 접근 전략에 관해, 이전에 비슷한 내용의 질문과 답변이 있었습니다. 해당 답변에서는 시간 복잡도가 높아 시간 초과가 발생할 것으로 예상되어 다른 방법을 모색하는 경우에 대해 설명되어 있습니다.

당시 질문에 대한 답변은 시간 복잡도가 (O(n^2))일 경우 (n = 15000)이면 연산 횟수가 대략 225,000,000회로 시간 초과가 날 가능성이 높다고 예상하고, 그러나 무식하게 푸는 방법을 먼저 시도한 뒤 최적화를 고려하는 접근법을 권장했습니다. 특히 코딩 테스트 문제를 해결할 때는 가장 단순한 방법으로 먼저 접근한 뒤, 시간 초과 문제가 확인되면 더 효율적인 방법을 찾는 과정을 거치는 것이 일반적인 전략입니다.

이와 관련하여 유사한 질문에 대한 지식공유자의 답변을 참조하시면 유익할 것 같습니다:

• 1-L 질문 있습니다!
  

해당 답변에서는 비슷한 상황에서 출발하여, 처음에는 너무 큰 시간 복잡도를 가진 접근법을 피하나, 문제 해결 과정에서 때때로 예상보다 효율적으로 문제를 해결할 수 있는 방법을 제시하고 있습니다. 무식하게 접근하는 것이 처음에는 도움이 될 수 있지만, 실제 적용시에는 다양한 테스트 케이스와 시간 제한을 고려하여 최적화 접근법을 찾는 것이 중요합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

안녕하세요 ㅎㅎ

저는 n의 최대값이 15000이기 때문에 15000*15000을 하면 2억이 넘어버려 시간 초과가 날것이라고 생각하여 저렇게 접근을 하였습니다.

그런데 저렇게 더 간단하게 풀리는걸 보니 시간초과가 날 거 같더라도 일단은 먼저 간단한 방법으로 풀어본 뒤 시간초과가 나면 그때서야 다른 방법으로 접근을 하는 것이 맞을까요?

>> 문제마다 다르지만 보통 100억 -> 절대 안됨, 10억 초과 -> 거의 안됨. 1억 -> 어느정도는 됨.

이렇게 생각하시면서 접근하시면 됩니다.

감사합니다.