[C++] 기초부터 공부하기(1. 기초 & 입출력)!

백준을 100문제 넘게 풀고 골드 문제로 가면서부터 C언어로 PS를 하는데에 한계를 느끼기 시작했다..

그래서!!! C언어와 매우 유사한 C++을 공부하기로 마음을 먹었다! 이젠 C++을 이용해 알고리즘을 풀거다!

 

1) C++ 기초

이에 앞서 C와는 다른 C++의 차이점 몇가지를 짚고 넘어가려고 한다.

1-1. std

 -cout,cin,endl를 포함하여 자주 사용되는 함수들이 정의되어 있는 곳으로 표준라이브러리에 있는 변수 또는 함수들이 std 네임스페이스에 포함되어 있다. 따라서 표준 라이브러리를 사용하기 위해서는 std::를 앞에 붙어야지만 사용할 수 있지만 using namespace std를 이용하면 생략해서 사용이 가능하다.

 

1-2. 입출력 (cin,cout) 및 \n과의 차이점

 입력과 출력을 각각 scanf와 prinf를 이용하는 C와는 달리 C++에서는 cin과 cout를 사용한다. 또한 괄호를 이용하여 표현하는 것이 아니라 << 혹은 >>을 이용하여 좀 더 직관적으로 입출력을 표현 가능하다.

 

 예를 들어 cin같은 경우에는 cin>>arr[i]라고 한다면 arr[i]에 입력을 받는 다는 뜻이고 cout 같은 경우에 cout<<arr[i]라고 한다면 arr[i]를 출력한다는 뜻이다. 이때 cout << 1 << 2 << 3 << 4  << 5 이런 식으로 된다면 왼쪽부터 1 2 3 4 5로 출력이 된다. 

 

 또한 endl도 std에 정의되어 있는 함수인데 얘의 역할은 출력 버퍼를 비우는 역할을 한다. 버퍼란 임시 메모리 공간으로 이 임시 메모리 공간에 저장했다가 버퍼가 가득차거나 개행 문자가 나타나면 버퍼의 내용을 한번에 전송하는 것을 뜻한다. 따라서 매번 endl을 사용한다면 버퍼를 매번 비우고 다시 버퍼를 채우기 때문에 시스템콜을 많이 호출하고 이에 따라 속도가 느리다. 반면에 \n을 사용하면 얘는 버퍼를 매번 비우지 않기 때문에 속도가 endl보다 빠르게 된다. 이와 관련한 시간 차이는 밑에 '수 정렬하기 2' 문제에서 더욱 욱 나타난다.

 

 endl과 \n 차이점에 대한 궁금증은 밑에 블로그 글이 많은 도움이 됐다!

https://yechoi.tistory.com/48

[C++] std::endl이 \n과 다른 점 - 출력버퍼 이해하기

 

1-3. 입출력(cin,cout) 속도

 

 cin,cout는 위에 언급했다 싶이 scanf와 pritnf를 대체하여 자료형에 상관없이 >> <<만을 이용하여 표현할 수 있다는 점에서 편리하게 사용이 가능하다. 하지만 알고보니 cin은 scanf에 비해 수행시간이 느리다는 것이다(10^7개의 숫자를 입력받을 때 std::cin은 2.051초이고, scanf는 수행시간이 0.798초이다.)

 

  iostream은 'input out stream'의 줄임말인데 이때 stream은 프로그램과 입출력하는 단말기(키보드) 사이에 연결된 입출력 통로를 말한다고 한다. 이때 C++의 stream은 C의 stream과 동기화 되어 있어 C++코드와 C 코드가 같은 stream buffer에 쌓이게 된고 이는 곧 딜레이가 발생한다는 것이다! 그 결과 C와 C++의 입출력을 혼용할 수 있지만 프로그램의 속도는 scanf와 printf보다는 느리게 된다는 것이다. 그리고 이는 알고리즘 문제를 풀 때 유의미한 시간속도 차이를 보인다. (밑에 있는 1920번: 수 찾기가 그 예!)

 

 

 

 그렇다면 cin과 cout를 사용하면서 속도를 높일 수 있는 방법은 없을까? 

 

   ios_base::sync_with_stdio(false);    

 

를 이용하면 C와 C++ 사이의 버퍼 동기화를 끊어 cin과 cout가 독립적인 버퍼를 갖게하는 방식으로 해결가능하다. 위에서 언급했다싶이 C와 C++이 같은 buffer를 사용해 문제가 생겼기 때문에 이를 사용하면 사용하는 버퍼 수를 줄여 입출력 속도를 크게 향상 시킬 수 있다.

 

 다만 주의 해야할 점은 동기화를 끊었기 때문에 scanf, printf,getchar과 같은 C의 입출력 함수와 섞어 쓰게 된다면 buffer을 같이 사용하고 있는 것이 아니기 때문에 입출력의 순서가 올바르지 않을 수 있다. 또 멀티 쓰레트 환경에서 예상하지 못한 결과가 도출될 수도 있어 현업에서는 주의가 필요하다. 

 

    cin.tie(NULL);
    cout.tie(NULL);

 

를 이용하여 속도를 더 줄일 수 있다. cin과 cout가 묶여있는 tie에서는 입력스트림(cin)에서 입력 작업을 하려면 미리 출력 스트림(cout)에 있는 것을 비워야하는 동작을 한다. 즉, 버퍼를 여러번 출력하고 새로 받는 과정에서 시스템콜의 횟수가 늘어나게 된다. 이 상태가 디폴트 상태이다.

 

 하지만 cin과 cout가 untie 되어 있는 상태에서는 위에 언급한 과정들을 신경쓰지 않고 단지 버퍼가 가득 차거나 수동적으로 flush(콘솔에 표시되는 상태)를 시켜주기 전까지는 출력이 되지 않는 상태를 만들어준다. 그 결과 시스템콜의 횟수가 줄어 속도가 향상된다.  이 두 과정을 통해 속도를 향상 시킬 수 있다.

 

 

 

 

2) 정렬하기

C언어로 풀었을 때 자꾸 시간초과가 나서 풀지 못했던 백준 2751: 수 정렬하기 2를 먼저 풀었다.

 

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 C++에는 sort 알고리즘이 있는데 평균 시간복잡도가 n log n 인 매우 효율적인 알고리즘이다!! (C로 평균 시간복잡도가 n log n인 알고리즘을 구현하는 것이 쉽지 않다-quicksort,mergesort 모두 구현하더라도 시간초과가 발생했다)

 sort 함수 원형은 void sort(T start, T end)이며 3번째 인자를 넣지 않으면 default로 오름차순 정렬이 되고 인자를 넣으면 정의한 기준에 따라 정렬이 가능하다.

• sort(arr, arr+n);
• sort(v.begin(), v.end());
• sort(v.begin(), v.end(), compare);                //사용자 정의 함수 사용
• sort(v.begin(), v.end(), greater<자료형>());    //내림차순 (Descending order)
• sort(v.begin(), v.end(), less<자료형>());        //오름차순 (default = Ascending order)

 이 문제를 풀 때 한가지 조심해야할 점은 출력할 때 \n이 아닌 endl를 사용할 경우 최대 1000000번 버퍼를 호출하고 내보내기 때문에 시간이 오래걸려 시간초과가 발생하게 된다. 따라서

 

 cout<<arr[i]<<endl; 이 아닌  cout<<arr[i]<<"\n";

 

와 같이 써야한다!

아래는 전체 소스코드이다!!

 

#include <iostream>
#include <algorithm>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000000];

int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    {
      cin>>arr[i];
    }
  sort(arr+1,arr+n+1);
  for(int i=1;i<=n;i++)
    {
      cout<<arr[i]<<"\n"; 
    }
}

 

 

3) 탐색하기 

  백준 1920: 수 찾기 이 문제도 정렬을 제대로 시키지 못해 C로 풀었을 때 시간초과가 나왔던 문제이다. 

 위에서 풀었던 것과 비슷하게 입력받은 배열을 sort 함수를 이용해 정렬시킨 뒤 C++의 STL을 이용하여 Binary Search로 문제를 풀었다.

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 STL에 있는 bool binary_search(arr.begin,arr.end,k) (k는 찾고자 하는 수)을 이용하면 O(log n)으로 찾았다면 1을 못찾았다면 0을 반환할 수 있다. Binary Search를 직접 구현하는건 작년에 알고리즘  수업을 하면서 주구장창해서 그냥 기존에 있는 함수를 이용하였다. 이를 이용해 문제를 풀면 되는 간단한 문제이다!

 

 근데 어라라? 시간초과가 나와서 뻥졌다. 찾아보니까 위에 1-3) 입출력 속도에 썼다 싶이 C와 C++ buffer의 동기화를 끊는 코드를 이용하여 고쳤더니 문제가 해결이 되었다. 아래는 전체 소스코드다!

 

#include <iostream>
#include <algorithm>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[100002];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n,k,tmp;
  cin>>n;
  for(int i=1;i<=n;i++)
    {
      cin>>arr[i];
    }
  sort(arr+1,arr+n+1);
  
  cin>>k;  
  for(int i=1;i<=k;i++)
    {
      cin>>tmp;
      bool isFound=binary_search(arr+1,arr+n+1,tmp);
      cout<<isFound<<"\n";
    }  
}