알고리즘 문제풀기 전 필독!! - c++

복잡도와 STL의 값 복사 주의와 입출력 속도 상승법을 알고가자.



시간, 공간복잡도

반드시 알고리즘을 작성하기 전에 복잡도를 초과하지 않는지 확인해야 하며, 넘는다면 그것은 잘못된 풀이법이므로 빠르게 다른 풀이법을 생각해내야 한다.

아래 기준표는 정확한 기준은 아니고, 대략적으로 이렇다는 것.


시간복잡도

  • 컴퓨터가 대략 1억 번의 계산이 1초 내에 가능하다고 기억(실제로는 더 많은 계산 가능)image-20230428154114290


공간복잡도

  • 512MB = 1.2억개의 int



STL과 함수인자(값 복사 주의)

C++에서 STL을 인자로 넘길때는 int num 같은 변수를 인자로 넘길때처럼 값이 복사가 되어 넘어간다.

문제점 : STL을 함수 인자로 넘길 때 복제한다. 즉, O(N)

bool cmp1(vector<int> v1, vector<int> v2, int idx){
    return v1[idx] > v2[idx];
}


해결방안 : STL을 주소로 넘긴다. 즉, O(1)

bool cmp1(vector<int>& v1, vector<int>& v2, int idx){
    return v1[idx] > v2[idx];
}



STL vector

매우 주의해야할 점이 있다.

첫번째로 vector처럼 STL은 분명 함수 인자에서처럼 값이 복사되는 형태로 int num 같은 변수처럼 동작한다고 했다. 따라서 = 을 입력하면 깊은복사가 발생한다.

vector<int> v3 = {1,2,3,4};
vector<int v4;
v4 = v3; // deep복사 (깊은복사) 발생 즉, O(N)


두번째로 vector의 size메소드는 unsigned int를 반환한다.(음수가 없는 양수 범위의미)
따라서 size값이 0일때 -1을 하는순간 에러가 발생한다.

for(int i=0; i<v1.size(); i++) cout << v1[i] << ' '; // 정상
for(int i=0; i<v1.size()-1; i++) cout << v1[i] << ' '; // 언더플로



표준 입출력(속도UP)

ios::sync_with_stdio(0), cin.tie(0) 을 사용할 것.

  • 0은 false를 의미한다.
  • 백준 사이트에서는 채점을 할 때 순서는 상관 없이 출력 글자만 확인하므로 cin.tie(0) 를 써서 버퍼에 값을 모아서 한 번에 출력하자.
    즉, 버퍼에 넣었다 뺏다가 하면서 매번 낭비하지 말고 버퍼에 값을 한 번에 모아서 출력!!! (순서가 엉망이 되는 문제가 있지만 백준 사이트에서는 상관없다)
  • c++은 printf와 cin이 같이 사용되게 허용하므로 낭비가 발생한다. 따라서 ios::sync_with_stdio(0) 를 써서 cin만 사용하게끔 변경한다. 즉, 이 명령어와 함께 C++의 입출력만 반드시 사용하자!



코드 작성 팁

지금 우리는 문제를 빨리 푸는데 중점을 둬야지 유지보수를 위해 가독성 좋은 코드나 이런걸 짜는게 아니다.
즉, 개발과 코딩테스트는 다르다.

  • 당장의 코딩테스트는 using namespace std 를 활용해서 std 없이 빠르게 작성하는데, 개발할 때는 또 가독성을 위해 있어줘야 할 필요도 있다.
  • 또 출력에 맨 마지막 공백, 줄바꿈 등등이 있어도 전혀 채점 사이트에서는 문제없다!
  • c++의 경우 endl; 은 쓰지말고 '\n'; 을 사용 적극 권장
  • 배열같이 크기를 지정할 때 100을 지정해야하면 넉넉히 105 로 크기 지정해주기

댓글남기기

참고