[바킹독 알고리즘]0x02강 - 기초 코드 작성 요령 II

0x00 STL과 함수 인자

참조자(Reference)

[중간]c에서의 포인터    [오른쪽]c++에서의 참조자    를이용해 원본을 바꾸고 있다.

 

 

swap1 함수는 제대로 동작하지 않는걸 알 수 있다. 원본 2개를 바꾸고 싶은데 복사된 2개를 바꾼다한들 의미가 없는것.

 

그래서 swap2 함수처럼 포인터를 보내서 두 변수의 값을 바꿀 수가 있다. 그런데 C++에서는 해결법이 한 개 더 있는데, 바로 참조자(reference)이다. swap3 함수를 보면 함수 인자인 a와 b의 type이 int가 아니고, int 뒤에 &가 붙어있는 것을 볼 수 있다. 그러니까 a와 b는 int reference인 것이다.

저렇게 a와 b를 참조자로 만들면 함수 내의 코드에서는 그냥 int를 쓰듯이 tmp에 a를 대입하고, a에 b를 대입하고 하는데 저게 다 원본을 바꾸는 것이다.

 

참조자는 C에서의 포인터랑 거의 비슷한 기능을 하지만 포인터에서 Null pointer에 값을 넣는다거나 type이 다른걸 마음대로 캐스팅한다거나 하는 문제들을 덜 할 수 있게 하는 패러다임인것.

 

 

 

 

STL(Standard Template Library) - vector

STL은 C++에서 제공되는 라이브러리로, C++에는 미리 다양한 알고리즘과 자료구조가 STL에 구현되어 있어서 우리는 필요한 자료구조를 직접 구현할 필요 없이 여기서 가져다 쓸 수 있다. 종류도 굉장히 다양하다.

 

vector STL

다양한 STL 중 배열과 비슷한 기능을 수행하는 vector STL을 소개하겠다.

원래 C++에서는 배열을 선언할때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 한다. 그런데 vector는 일종의 가변배열로 크기를 마음대로 조절할 수 있다. vector는 vector 헤더에 선언되어있다.

 

 

 

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

 

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

 

 

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

 

첫 번째 코드는 v1, v2를 인자로 실어서 보낼 때 원본으로부터 복사본을 만드는 비용이든다. 따라서 v1, v2의 크기가 N이니깐 N개의 원소들을 하나하나 복사하는 과정을 거치므로 O(N)이 든다.

우리가 원하는 것은 idx번째 원소의 값만 비교하고 싶은것,, 하지만 매번 vector를 복사하는건 너무 비효율적이다.

 

두 번째 코드는 v1, v2의 type을 vector의 reference로 만들었따. 그래서 cmp2가 호출될 때 복사본을 따로 만들어내지 않고 참조 대상의 주소 정보만 넘어가기 때문에 시간복잡도는 의도한대로 O(1)이 된다.

 

 

 

 

 

 

0x01 표준 입출력

코딩테스트에서 입력과 출력은 표준 입출력을 사용한다. C에서는 scanf/printf로 입력과 출력을 처리, C++에서는 cin/cout을 사용한다.(후자를 권장)       scanf/printf에서는 C++ string을 처리할 수 없다.

 

scanf와 cin 주의점

scanf와 cin 모두 공백을 포함한 문자열을 입력받을 때 둘 다 공백 앞까지만 입력을 받기 때문에 껄끄럽다.

 

해결책으로는 3가지 방법이 있는데, 첫 번째는 scanf에서 줄바꿈(\n)이 나오기 전 까지 입력을 받는다는걸 명시하는 방식이다. 그런데 비효율적...

 

두 번째는 gets 함수를 사용하는건데, 문제는 저 함수가 보안상의 이유로 C++14 이상에서는 제거되었다. 그래서 이것도 별로.. 

 

세 번째는 getline을 이용하는건데 이게 제일 깔끔하다. 대신 이건 type이 C++ string이어야 한다.

 

두 번째는 환경에 따라 사용하지 못할 수도 있으니 아예 제껴두고, 선택지가 첫 번째나 세 번째인데 역시 getline이 더 좋아보인다.

 

아무튼 공백이 포함된 문자열을 받아야 할 때 단순히 scanf나 cin을 쓰면 안된다!

 

 

cin/cout 주의점

cin/cout에서는 입출력시 시간제한이 있다. 따라서 입/출력의 양이 많을 때 시간초과가 날 수 있다. 이를 방지하기 위해 ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 한다. 

 

기본적으로 scanf/printf 등에서 쓰는 C stream과 cin/cout 등에서 쓰는 C++ stream은 분리가 되어있다.  코드의 흐름과 실제 출력이 동일하기 위해서 기본적으로 프로그램에서는 C++ stream과 C stream을 동기화하고 있다. 그런데 내가 C++ stream만 쓸거면 굳이 두 stream을 동기화하고 있을 필요가 없게 된다. 불필요한 시간만 생겨서 프로그램 수행 시간이 늘어남.

 

그래서 동기화를 끊는 명령인 sync_with_stdio(0) 을 사용. 대신 동기화를 끊었으면 절대 cout과 printf를 섞어쓰면 된다. 섞어쓰면 출력 순서가 꼬이게 된다. 

 

 

 

버퍼(buffer)

 

두 번째 명령인 cin.tie(0)을 이해하려면 버퍼라는 개념을 이해해야 한다. 우리가 화면에 아무 글자나 출력을 하는걸 생각해보면, 저희는 별 생각 없이 cout으로 출력을 찍지만 사실은 한 글자 한 글자가 바로 화면에 보이는게 아니다.

 

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

 

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

 

 

 

 

cin.tie(0)

그런데 입력과 출력이 번갈아나오고 그게 한 화면에서 다 보여질 경우에는 버퍼의 존재로 인해서 순서가 꼬여버릴 수도 있다.

위 코드를 보면 3번에 걸쳐 두 수를 입력받고 합을 출력하는데 우리는 당연히 순서에 맞게 콘솔에 나타나기를 원한다. 그런데 예를 들어 6번 줄에서 "118\n"이란 출력을 하라고 했을 때, 바로 출력이 되지 않고 버퍼에 들어있다가 "2 5"를 입력한 후에야 출력이 되면 순서가 꼬일 것이다.

 

이런 현상을 막으려고 기본적으로는 cin 명령을 수행하기 전에 cout 버퍼를 비워준다. 버퍼를 비우면 자연스럽게 "2 5" 입력이 들어오기 전에 118이 출력될거고 또 "94 542" 입력이 들어오기 전에 7이 출력되어서 순서가 꼬이지 않게 된다. 

 

 

그런데 온라인 저지 사이트에서는 채점을 할 때 그냥 출력 글자만 확인을 한다. 그렇기 때문에 콘솔 창에서 입력 글자와 출력 글자 사이에 순서가 설령 꼬인다고 해도 채점에 아무런 영향을 주지 않고 두 경우 모두 다 정답 처리가 된다.

 

그러면 굳이 cin 명령을 수행하기 전에 cout 버퍼를 비울 필요가 없기 때문에 cin 명령을 수행하기 전에 cout 버퍼를 비우지 않도록 하는 코드 cin.tie(nullptr) 혹은 cin.tie(0)를 사용한다.

 

 

결론

• cin/cout을 쓸 땐 반드시 sync_with_stdio(0) 와 cin.tie(0) 넣어줘야함
• sync_with_stdio를 쓴 이후로는 무조건 cin/cout만 쓰고 printf/scanf를 쓰면 안된다
• endl은 절대로 사용 X
  • endl은 개행문자("\n")를 출력하고 출력 버퍼를 비워라는 명령임. 채점시 중간 중간 버퍼를 비우라고 명령을 줄 필요가 전혀 없다. 줄바꿈이 필요하면 endl 말고 그냥 개행문자를 출력

 

 

 

 

 

0x02 코드 작성 팁

1.코딩테스트와 개발은 다르다. 클린코드로 짤 필요가 없다.

결과값만 같다면 모두 합격,, 코딩테스트에서는 좀 더럽더라도 내가 빠르게 짤 수 있는 방식이 더 중요하다

 

 

 

[BOJ 10871번:X보다 작은 수]                                  나의 답안

#include <iostream>
using namespace std;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x, a[10002];
    cin >> n >> x;
    for(int i =0; i<n; i++) cin >> a[i];
    for(int i =0; i<n; i++)
        if(a[i] < x) cout << a[i] << ' '; 
}

 

 

 

 

 

2.출력 맨 마지막 공백 or 줄바꿈이 추가로 있어도 괜찮다.

3 뒤에 공백이 있어도 정답처리된다

 

 

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

 

구현을 끝냈는데 예제에 대해 답이 올바르게 나오지 않을 때 코드의 어디가 잘못됐는지 알고 싶어서 디버거를 이용하는 경우가 간혹 있다. 그럴 때 디버거를 켜면 뭔가 꼬이고 늪에 빠져드는 것과 같은 느낌을 받을 때가 있어서 차라리 중간 변수를 보고 싶으면 cout이나 printf로 출력을 찍어서 확인하고 디버거는 굳이 사용을 안하는 것을 권장한다.