인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
해결된 질문
작성
·
14
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
Q1. 다른 질문글을 확인한 결과
1. cnt를 찍으며 여러가지 케이스를 도출한 다음 -> 2. (시간이 있다면) 점화식 만들고 / 일반적으로는 어림 잡아서 -> 3. 규칙을 찾아 식으로 만든 후 빅 오 표기법으로 표시한다
이런 식으로 진행해야하는 것 같은데, 실제 코딩테스트에 들어가서도 이렇게 cnt를 찍어보며 실행 횟수를 측정할 수 있는건가요??
또한 실제 코딩테스트 시험 치면서도 위의 과정으로 시간 복잡도를 구하는건가요??
백준에선 출력을 확인해볼 수 없기도하고, 코딩테스트를 아직 한 번도 응시해보지않아 환경을 몰라서 여쭤봅니다.
Q2.
만약 n=30인 경우 while문이 5번 실행됩니다. 위의 식에 30을 대입하면 5.906 이라는 소수가 나오길래, 의문이 생겨 여쭤봅니다.
원래는 시간 복잡도가
인데 시간 복잡도는 얼마나 더 빨리 증가하냐 가 중요하니 내림 을 하든, 안하든 그 증가 속도는 동일하니까 위의 식을
으로 볼 수 있고, 이게 빅 오 표기법을 적용하면
이렇게 된다. 이 논리가 맞을까요??
답변 2
0
안녕하세요 재윤님 ㅎㅎ
또한 실제 코딩테스트 시험 치면서도 위의 과정으로 시간 복잡도를 구하는건가요??
-> 아닙니다. 이건 기본을 배우는거라 쉽게 저렇게 한거구용. 문제 풀면서 문제범위기반으로 시간복잡도 구하는 방법을 알려드릴거에요. ㅎㅎ
Q2. 네 맞습니다. 잘 하셨습니다. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 재윤님, 질문 주셔서 감사합니다.
시간 복잡도 분석과 관련된 코딩 테스트 환경에 대한 궁금증을 가지셨군요. 코딩 테스트에서 실행 횟수를 직접 출력하여 확인하는 것은 일반적으로 허용되지 않습니다. 특히 백준 같은 온라인 저지에서는 출력 형식에 맞지 않는 출력은 결과에 반영되지 않기 때문에 주의가 필요합니다.
코딩 테스트 환경
출력 제한: 대부분의 코딩 테스트 플랫폼에서는 제출한 코드의 출력이 문제에서 요구하는 형식과 맞아야만 정답으로 인정됩니다. 따라서 디버그 및 로그용 출력(cout 같은 것)은 실제 제출 시 포함되면 안 됩니다.
시간 복잡도 추정: 따라서 코드를 작성하면서 시간 복잡도를 이론적으로 추정하고 코드를 최적화하는 것이 중요합니다. 실행 횟수나 시간 복잡도를 감으로 예상해야 하며, 주어진 제한 내에서 해결해야 합니다.
로컬 환경에서 디버깅: 코드를 테스트하기 위해서는 자신의 개발 환경에서 테스트 케이스를 돌려보는 방법을 사용해야 합니다. 예를 들어, 자신의 컴퓨터에서 다양한 입력을 시도해보고 실행 시간을 간접적으로 측정해 보는 것이 가능합니다.
도움되는 자료
아래 유사한 질문들에서 제공하는 내용이 실제 환경에서 유용한 팁을 포함하고 있을 수 있습니다:
1. 문제로 해결하는 시간복잡도 4번 질문이 있습니다. - 코딩 테스트에서의 시간 복잡도 이해와 해결 방안에 대한 논의.
2. 2-S 질문있습니다! - 시간 복잡도와 수행 시간에 대한 논의.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.