[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II

1.  STL과 함수 인자

 

함수 인자

 

위의 세 코드는 원본의 값을 바꾸는지 복사본의 값을 바꾸는지에 대해 묻는 것으로 출력 결과는 다음과 같다. 

1. 0

함수 인자로 그냥 int 만 전달하게 되면 함수에서 아무리 값을 바꿔도 원본에 영향을 주지 않는다.

 

2. 10

함수 인자로 배열을 넘겨주게 되면 인자로 배열의 주소가 전달되기 때문에 함수에서 바꾼 것에 따라 원본 값에도 영향이 있다.

 

3. 0

구조체도 함수 인자로 전달하게 될 때, int 와 같이 값만 복사되는 것이기 때문에 원본에 영향을 주지 않는다.

 

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

위 코드는 원본에 영향을 주지 않아 원하는대로 동작하지 않는 swap 코드이다.

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

위 코드는 포인터를 보내서 원본의 값을 변경하는 제대로 동작하는 swap 코드이다.

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

위 코드는 참조자(reference)를 이용한 코드이다. 참조자로 전달하게 되면 주소값을 전달하기 때문에 함수 내에서 포인터 없이 그냥 사용해도 원본의 값이 변경된다.

---

STL(Standard Template Library)

vector

- 가변배열로 크기를 마음대로 조절 가능하다.

- vector 헤더에 선언되어 있다.

- 인덱스를 통해 접근가능하다.

- 함수 인자로 보낼 때 구조체와 같이 복사본을 전달하여 원본에 영향을 주지 않는다.

 

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

위 코드의 시간복잡도는 O(N)이다. 함수 안에서 연산은 1번일지 몰라도 v1, v2를 인자로 실어서 보낼 때 원본으로부터 복사본을 만드는 시간을 고려해줘야 한다. v1, v2 의 크기가 N이므로 N개의 원소들을 복사하면 O(N)의 시간이 들게 된다.

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

값만 비교할 때마다 매번 vector를 복사하는 건 시간적인 측면에서 비효율적이다. 이럴 때 참조자를 사용하면 시간복잡도를 줄일 수 있다.

참조 대상의 주소만 넘어가서 위의 코드의 시간복잡도는 O(1)이 된다.

 

---

2. 표준 입출력

C - scanf/printf

C++ - cin/cout

 

scanf/printf 에서는 C++ string을 처리할 수 없는데 char* 보다는 C++ string이 훨씬 사용하게 편하다. scanf/printf를 쓰면서 C++ string을 쓰고자 한다면 char*로 입력 받고 string으로 형 변환을 한 뒤에 작업을 하고 c_str() 메소드로 출력하면 된다.

 

scanf나 cin 모두 공백 앞까지만 입력을 받기 때문에 공백을 포함한 문자열을 입력받기 힘들다. 이때 쓸 수 있는 방법은 3가지가 있다.

공백을 포함한 문자열을 입력받는 방법.

1. scanf에서 '\n'이 나오기 전까지 입력받는걸 명시한다.

char a1[10];
scanf("%[^\n]", a1);

2. gets 함수를 사용한다.

char a1[10];
gets(a2);
puts(a2);

C++14 이상에서는 보안상의 이유로 제거되었다.

 

3. getline을 이용한다.

string s;
getline(cin, s);
cout << s;

타입이 C++ string 이어야 한다.

 

 

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

cin/cout 은 scanf/printf와 다르게 시간초과가 날 수 있기 때문에 위의 명령어를 실행시켜야 한다.

위 명령어가 어떤 의미인지 정리해보자.

 

기본적으로 scanf/printf 등에서 쓰는 C stream 과 cin/cout 등에서 쓰는 C++ stream 은 분리가 되어 있다. printf와 cout을 번갈아 사용하는 상황에서 일반적으로 사용자는 차례대로 출력이 나오길 바란다. 이렇게 코드의 흐름과 실제 출력을 동일하게 만들기 위해서 프로그램에서는 기본적으로 C++ stream과 C stream을 동기화하고 있다. 그런데 어차피 C++ stream만 쓸 것이라면 두 stream을 동기화 할 이유가 없다. 시간만 오래 잡아 먹기 때문이다.

 

C++ stream만 쓸 때, 동기화를 끊어서 프로그램 수행 시간에서 이득을 챙길 수 있게 되고, 이 동기화를 끊는 명령이 바로 sync_with_stdio(false)이다. bool type이지만 코드를 더 간단히 쓰려면 false 대신 0을 넣어도 괜찮다.

 

동기화를 끊고 난 뒤에는 cout과 printf를 섞어서 쓰면 안 되는데 출력 결과의 순서가 꼬이기 때문이다.

 

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

 

cin.tie(0)을 이해하기 위해서는 버퍼를 알아야 한다. 화면에 출력을 할 때 문자가 바로 화면에 보이는 게 아니라 출력 버퍼라는 곳에 문자가 임시로 저장되었다가 버퍼가 비워지면서 화면에 보이게 된다. 출력에서 버퍼가 있듯, 입력에서도 버퍼가 있다. 

 

입력과 출력이 번갈아 나오고 한 화면에서 보여질 경우 버퍼의 존재로 인해 순서가 꼬일 수도 있다. 이런 일을 막기 위해 기본적으로 cin 명령을 수행하기 전에 cout 버퍼를 비워준다. 그런데 온라인 저지 사이트에서는 채점 시 그냥 출력 글자만 확인하기 때문에 입력 글자와 출력 글자의 순서가 꼬인다고 하더라도 채점에 아무런 영향을 주지 않는다.

 

따라서 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없으며 이렇게 만드는 코드가 바로 cin.tie(nullptr)이다. nullptr 타입이지만 0으로 써도 무방하다.

 

따라서 코딩테스트를 준비할 때는 위의 두 명령어를 꼭 넣어주자!

 

endl

개행문자('\n')를 출력하고 출력 버퍼를 비우라는 명령인데 어차피 위에서 봤듯이 출력 버퍼를 비울 필요가 없기 때문에 그냥 개행문자를 출력하자. 

 

---

3. 코드 작성 팁

1. 코딩테스트와 개발은 다르다.

BOJ 10871번: X보다 작은 수

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, X, tmp;
    int A[10000] = {
        0,
    };

    cin >> N >> X;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        A[i] = tmp;
    }
    for (int i = 0; i < N; i++)
    {
        if (A[i] < X)
        {
            cout << A[i] << " ";
        }
    }

    return 0;
}

 

2. 출력 맨 마지막 공백 혹은 줄바꿈이 추가로 있어도 상관 없다.

3. 디버거는 굳이 사용하지 않아도 된다.

 

---

참고자료

[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II

[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II