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

안녕하세요 ㅎㅎ

문제를 재귀로 풀고 생각해보니 최악의 경우인 15000 * 15000이 될 수 없긴 한데
그래도 N^2의 시간 복잡도인데 어떻게 통과한 것인지 궁금하고

-> 정확히는 15000 곱하기 15000 / 2가 됩니다. 이렇게 계산하면 약 1억정도가 됩니다. 1억정도의 시간복잡도는 통과될 수 있는 시간복잡도입니다. 이부분은 1주차 개념교안내 가능한 시간복잡도의 기준  를 참고부탁드립니다.

이런 경우 대충?의 시간 복잡도를 어떻게 계산해서 -> 이중 for문으로도 풀어도 되겠다

-> 무식하게 생각 -> 2중 for문으로 해보자 -> 1억이네 가능하군 -> 시도 이렇게 했던것 같습니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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

starkshn님께서 질문하신 시간 복잡도와 문제 해결에 대한 접근 방식에 대해 자세히 설명해 드리겠습니다. 때로는 예상치 못한 방식으로 문제가 통과되기도 하는데, 이는 종종 테스트 케이스의 특성이나 입력값의 분포에 따라 달라질 수 있습니다. 일반적으로 코딩 테스트에서는 주어진 시간 내에 모든 경우의 수를 검토할 수 없기 때문에, 가장 흔히 경험적으로 주어진 시간 내에 실행될 것으로 예상되는 복잡도로 문제를 해결합니다.

비슷한 상황에서의 유사한 질문과 답변이 있었는데, 여러 사용자들이 “시간 복잡도가 O(n^2)이지만 왜 통과했을까?“와 같은 고민을 했던 사례가 있습니다. 이 문제는 사실 재귀보다 이중 for문으로 풀게 되면 예상보다 더 효율적으로 동작할 수 있는 경우가 있습니다.

관련 질문과 답변을 참고하시면 도움이 될 것입니다:
- 1-L 질문 있습니다!

위의 질문에서는 비슷한 방식의 고민이 있었고, 시간이 초과될 것 같은 코드도 때로는 효율적인 입력 분포나 특정 문제 구조 덕분에 통과할 수 있음을 설명하고 있습니다. 특히 코딩 테스트에서는 가장 단순한 방법을 시도해 보고, 필요한 경우 효율적인 방법으로 전환하는 전략이 유용할 수 있습니다.

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