[코딩 테스트 준비 - 기초] 1. 시간 복잡도와 언어별 유의사항

알고리즘을 체계적으로 접근해 보고자 코드플러스에서 코딩 테스트 준비 묶음을 구매했다. 해당 강의를 수강하고 기억할 만한 것들을 기록할 것이다. 유료 강의이기 때문에 모든 것을 남길 수는 없지만 시간이 흘러 기억이 희미해졌을 때 스스로 복기할 수 있을 정도는 정리할 것이다. 세부적인 내용이 궁금하면 강의를 구매하자!

 

1. 시간 복잡도

알고리즘 문제를 해결하는 데 있어 수행시간이 가장 중요하다.

코드를 작성하기 전에 문제의 크기를 먼저 확인하고 시간복잡도를 계산해보자.

 

각 시간 복잡도 별로 1초가 걸리는 입력의 크기는 다음과 같다.

시간 복잡도	입력의 크기
O(1)	상관 없음
O(logN)	대충 1억
O(N)	1억
O(NlogN)	5백만
O(N^2)	1만
O(N^3)	500
O(2^N)	20
O(N!)	10

 

2. C++ 입출력

• scanf/printf, cin/cout 사용 가능
• 하지만, cin/cout은 scanf/printf보다 느리다.
• 아래 두 줄을 추가하면 빠른 cin/cout 입출력을 할 수 있다. 이 경우 scanf/printf를 쓰면 안된다.

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

• endl은 flush가 내장되어 있어 속도가 느리다. '\n'을 사용하자!

 

3. C++ string 연산

• string의 .length()연산은 O(1)이다.
• string의 += 연산은 O(K)이고, + 연산은 O(N + K)이다.