Resolved2026-02-28T06:15:45.817Z

rbqls3914

8 asked

0

안녕하세요 재윤님 ㅎㅎ

C++ 교안에 'sort()의 시간 복잡도는 O(nlogn) 이다.' 이런식으로 각 함수별 시간복잡도가 기재되어있던데, 코테에서 사용하는 함수가 상당히 많은데, 각 함수마다 시간복잡도 얼마인지 전부 외워야
-> 네 그렇긴한데요. 교안 1회독 이후에 개념 + 문제풀이 하시다보면 자연스레 외워질거에요.

 

감사합니다.

0

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

코딩 테스트에서는 여러 가지 표준 라이브러리 함수의 시간 복잡도를 알고 있는 것이 매우 유용합니다. 특히 자주 사용되는 함수들에 대해서는 기본적으로 알고 계시는 것이 문제 해결에 큰 도움이 됩니다. 그러나 모든 함수의 시간 복잡도를 외우는 것보다는 핵심적인 몇 가지를 이해하고 있는 것이 더 중요합니다.

주요 함수와 시간복잡도

몇 가지 자주 사용되는 함수와 그 시간 복잡도를 말씀드리겠습니다:

1. sort(): 일반적인 C++ std::sort()의 시간 복잡도는 평균적으로 O(n log n)입니다. 이는 빠른 정렬 알고리즘인 퀵소트 기반으로 구현되어 있기 때문입니다.

2. binary_search(): 이진 탐색의 시간 복잡도는 O(log n)입니다. 정렬된 배열에서 특정 요소를 찾는 데 유용합니다.

3. unordered_map: 대부분의 연산에 대해 평균 O(1)의 시간 복잡도를 가지며, 이는 결합, 탐색, 삽입 작업에 매우 효율적입니다.

4. vector:

   • 요소 추가 및 제거: 끝에 원소를 추가 또는 제거하는 push_back()과 pop_back()은 평균 O(1)입니다.
     
   • 특정 위치에 원소를 삽입 또는 제거하는 작업은 O(n)입니다.
     

전체 암기는 비효율적

모든 함수를 외우는 것은 비효율적일 수 있습니다. 대신:

• 기본 함수: 자주 사용하는 함수와 알고리즘의 시간 복잡도는 기억합니다.
  
• 문서 활용: 문제가 생기면 공식 문서나 참고 문헌을 빠르게 체크할 수 있게 준비합니다.
  
• 연습 문제: 실제로 문제를 푸는 과정을 통해 자연스럽게 학습합니다.
  

관련 참고 자료:

• 10주완성 C++ 코딩테스트 중 시간복잡도 이해 - 시간복잡도에 대한 이해와 방법론 제시.
  

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