기초 코드 작성 요령2

claire 2022. 1. 8. 15:40

C언어를 배울 때 두 변수를 swap 하는 함수를 만드는 방법을 배웠을 것이다. 포인터를 통해서 두 변수의 값을 바꾸는 것인데 아래의 코드와 같다.

void swap(int* a,int* b){
     int tmp=*a;
     *a=*b;
     *b=tmp;
}

그런데 C++에서는 해결법이 한 개 더 있는데, 바로 참조자(reference)이다. int 뒤에 &를 붙여 int reference를 만든다. 아래의 코드를 참고해라.

void swap(int& a,int& b){
    int tmp=a;
    a=b;
    b=tmp;
}

위와 같이 a와 b를 참조자로 만들면 함수 내의 코드에서는 그냥 int를 쓰듯이 tmp에 a를 대입하고, a에 b를 대입하지만 위의 과정이 모두 main함수 내의 원본을 바꾸게 된다. 참조자는 C에서의 포인터랑 거의 비슷한 기능을 하지만 포인터에서 null pointer에 값을 넣는다거나 type이 다른걸 마음대로 캐스팅한다거나 하는 문제들을 방지할 수 있다.

STL(Standard Template Library)

STL은 C++에서 제공되는 라이브러리이다. C++ 에는 미리 다양한 알고리즘과 자료구조가 STL에 구현되어 있어 우리는 필요한 자료구조를 직접 구현할 필요가 없이 그냥 STL에서 가져다 쓸 수 있다.

종류도 굉장히 다양한데 각 STL들은 나중에 대응되는 자료구조를 배운 후 소개하고 일단 이번 시간에는 배열과 비슷한 기능을 수행하는 vector STL만 소개하겠다.

원래 C++에서는 배열을 선언할 때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 한다.

하지만 vector는 일종의 가변 배열로 크기를 마음대로 조절할 수 있다. vector는 vector 헤더에 선언되어 있다.

void func1(vector<int> v){
    v[10]=7;
}
int main(void){
    vector<int> v(100);
    func1(v);
    cout<<v[10];
}

위 코드를 보면 100칸짜리가 0으로 초기화된 vector v를 선언하고 func1을 호출한다. func1에서는 v [10]을 7로 바꾼다. 그다음에 v [10]을 출력하는데 과연 값이 0일까 7일까?

답은 0이다. STL도 구조체와 비슷하게 함수 인자로 실어보내면 복사본을 만들어서 보내는 값에 의한 참조이기 때문에 func1 함수에서 바꾼 건 원본에 영향을 주지 않는다. 즉, STL을 쌩으로 함수 인자에 넣으면 복사해서 보낸다는 것을 유의하자.

그렇다면 이 사실을 기억하고 아래의 cmp1 함수를 확인해보자.

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

위의 함수는 두 vector를 인자로 넘겨받아 idx번째 원소의 값을 비교한 결과를 반환하는 함수이다. 두 vector의 크기가 n이라고 할 때 이 함수의 시간 복잡도는?

시간 복잡도는 충격적이게도 O(n)이다. 함수 내에서 연산을 딱 1번만 실행하는데 어째서 O(n)인가. 이는 v1, v2를 인자로 실어서 보낼 때 원본으로부터 복사본을 만드는 비용을 생각하지 못한 것이다.

v1, v2의 크기가 n이니 n개의 원소들을 하나하나 복사하는 과정은 O(n)이 든다. 그래서 위의 함수는 의도치 않게 시간 복잡도가 O(n)이 된다.

단지 idx번째의 원소만 비교하고 싶은데 매번 vector 자체를 복사하는 것은 말도 안 되는 일이다. 이럴 때! 참조자를 이용하면 된다. 아래의 함수를 보자.

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

위의 함수에서는 v1,v2의 타입을 vector의 reference로 만들었다. 그러면 cmp2가 호출될 때 복사본을 따로 만들어내지 않고 참조 대상의 주소 정보만 넘어가기 때문에 시간 복잡도는 의도한 대로 O(1)이 된다.

지금까지의 내용은 함수에서 복사본의 값을 바꿔서 원본은 변함이 없는데 원본이 바뀐다고 생각하는 경우나 복사본을 만드는 시간을 간과하여 시간 복잡도를 착각해버려 분명 답이 이상하지만 원인을 찾지 못하는 경우가 있을 수 있기 때문에 참조자와 함수 인자 부분은 기억을 잘해둬야 한다.

표준 입출력

C에서는 scanf/printf를 C++에서는 cin/cout을 사용한다.

scanf/printf에서는 C++ string을 처리할 수 없다. sacnf와 cin 모두 공백을 포함한 문자열을 입력 받을 때 껄끄럽다. 둘 다 공백 앞까지만 입력을 받기 때문이다. 해결 방법이 3가지 정도 있는데 아래의 코드로 살펴보자.

//1. scanf의 옵션
char a1[10];
scanf("%[^\n]",a1);

//2. gets 함수(보안상의 이유로 C++ 14 이상에서는 제거됨)
char a2[10];
gets(a2);
puts(a2);

//3. getline 함수 (type이 C++ string이어야 한다.)
string s;
getline(cin,s);
cout<<s;

공백이 포함된 문자열을 받을 때 단순히 scanf나 cin을 쓰면 안된다는 것을 꼭 기억하라.

- ios::sync_with_stdio(0), cin.tie(0)

cin/cout을 쓸 때 입출력으로 인한 시간초과를 막기 위해서 ios::sync_with_stdio(0), cin.tie(0) 이라는 두 명령을 실행시켜야 한다. 이걸 안 해두면 입/출력의 양이 많을 때 시간 초과가 날 수 있다. 위의 명령어를 쓰게 되면 무조건 cin/cout만 쓰고 printf/scanf를 쓰면 안 된다는 것도 꼭 기억해라.

이 두 명령이 하는 일을 알아보자.

ios::sync_with_stdio(0)

기본적으로 scannf/printf 등에서 쓰는 C stream과 cin/cout 등에서 쓰는 C++ stream은 분리가 되어있다.

만약 printf와 cout을 번갈아 하며 사용하는 상황을 생각해보면 사용자 입장에서는 C stream과 C++ stream이 분리되어있고 어쩌고 하는 내용이 다 알 바가 아니고 코드의 흐름에 맞는 실제 출력이 나오는 게 정상일 것이다.

이렇게 코드의 흐름과 실제 출력을 동일하게 하기 위해서 기본적으로 프로그램에서는 C++ stream과 C stream을 동기화하고 있다. 그런데 내가 C++ stream만 쓸 거면 굳이 두 stream을 동기화하고 있을 필요가 없다. 쓸데없이 시간만 잡아먹기 때문이다.

그렇기 때문에 C++ stream만 쓸거면 동기화를 끊어버려서 프로그램 수행 시간에서 이득을 챙길 수 있다.

이 동기화를 끊는 명령이 sync_with_stdio(0)이다. 엄밀히 말해 인자가 bool type이라 sync_with_stdio(false)가 더 맞긴 하지만 false보다 0이 더 짧으니 그냥 0으로 하겠다.

대신 동기화를 끊었으면 절대 cout과 printf를 섞어쓰면 안 된다. 섞어 쓰면 출력 순서가 꼬이게 된다.

참고로 Visual Studio 2017/2019에서는 sync_with_stdio를 그냥 무시하고 무조건 동기화를 유지하고 있어서 혹시 실습을 VS 2017/2019에서 진행한다면 출력이 잘 나올 것이다. 하지만 채점 서버는 gcc이기 때문에 분명히 차이가 있다.

cin.tie(0)

우리가 보는 출력은 출력 버퍼라는 곳에 문자가 임시로 저장되었다가 버퍼가 비워지면서 화면에 보인다.

출력에서 버퍼가 있는 것 처럼, 입력에서도 버퍼가 있어서 키보드로 받은 입력을 바로바로 넘겨주지 않고 버퍼에서 어느 정도 모았다가 준다.

입력과 출력이 번갈아나오고 그게 한 화면에서 다 보여질 경우에는 버퍼의 존재로 인해서 순서가 꼬여버릴 수도 있다. 이런 현상을 막으려고 기본적으로는 cin 명령을 수행하기 전에 cout 버퍼를 비워준다.

그런데 온라인 저지 사이트에서는 채점을 할 때 그냥 출력 글자만 확인을 한다. 그렇기 때문에 콘솔 창에서 입력 글자와 출력 글자 사이에 순서가 설령 꼬인다고 해도 채점에 아무런 영향을 주지 않고 두 경우 모두 다 정답 처리가 된다. 그러면 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없다는 걸 알 수 있다. 그래서 cin 명령을 수행하기 전에 cout 버퍼를 비우지 않도록 하는 코드가 cin.tie(nullptr)인 거고, 엄밀히는 type을 지켜서 nullptr로 쓰는 게 좋지만 그냥 타이핑도 아낄 겸 0으로 쓰겠다.

endl은 절대절대절대절대 쓰지 말아라. - endl은 개행문자를 출력하고 출력 버퍼를 비우라는 명령이다. 코테는 프로그램 종료 시 출력이 어떻게 생겼는지를 가지고 채점을 진행하니 중간중간 버퍼를 비우라고 명령을 줄 필요가 전혀 없다. 줄 바꿈이 필요하면 endl 말고 그냥 개행 문자를 출력하면 된다.

코딩 테스트와 개발은 다르다. 코딩 테스트에서는 내가 헷갈리지 않는 범위 안에서 어떻게든 타이핑을 아끼는 것이 최고이다. 어떻게든 제한된 시간 안에 정답을 받아야 하기 때문에 좀 더럽더라도 내가 빠르게 짤 수 있는 방식으로 구현하는 게 중요하다.