[기초] 시간 복잡도와 언어별 유의사항

효율성

1. 수행 시간
2. 사용한 메모리
3. 코드의 길이

수행 시간이 짧은 것이 메모리 보다 중요하며, 간결한 코드가 가장 중요하다.

문제의 크기

문제를 해결할 때는 문제의 크기 를 먼저 보고 방법을 생각하여 시간을 예측한다.

시간 복잡도

1. 코드를 보고 구현하는 방법
2. 코드를 작성 전에 구현하는 방법

2번을 이용해서 미리 시간 복잡도를 계산해보고 시간이 가능할 것 같다면 구현한다.

Big O Notation 을 사용한다. 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

시간 복잡도에 N 을 대입하여 1억이 나오면 대략 1초가 걸린다고 추측해 볼 수 있다.

사용한 메모리

배열이 가장 많은 공간을 사용하므로, 배열이 사용한 공간을 본다.

배열이 사용한 공간 : 배열의 크기 * 자료형의 크기 B

메모리 사용량에 대하여는 크게 걱정하지 않아도 된다. 시간에 더 신경쓰어라.

불필요한 공간이 없다면, 대부분 메모리 제한은 알아서 지켜진다.

언어별 유의사항

C++ 입출력

cin / cout 은 scanf / printf 보다 느리기 때문에 입/출력이 많다면 후자를 쓴다.

cin / cout 쓸 때

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

을 추가하면 scanf / printf 만큼 빨라진다.

대신, 이 경우에는 printf 와 cout cin과 scanf 를 섞어 쓰면 안되며
endl 대신에 \n 를 사용해야한다.

T 개의 테스트 케이스를 입력으로 받을 때,

입력을 전부 받고 출력을 한 번에 하는 것이 아니라,

테스트 케이스 한 개를 입력 받고 출력하고.. 반복하는 것이다.

매우 큰 크기의 배열을 필요하게 될 수 있기 때문에 이렇게 한다. (공간 활용성)

입력이 몇 개인지 주어지지 않는 경우에는

입력을 EOF 까지 받으면 된다.

while(cin >> a >> b)

이런 느낌이다.

시간 초과

C++ string 의 .length() 는 O(1) 이다.

각 연산마다 걸리는 시간 복잡도가 다를 수 있다.

c++ 에서 문자열과 문자열을 더하는 과정은 A+B 의 길이 만큼이기에 고려해야한다.