알못에서 잘알까지

   1.  입출력 속도 향상  

#include <iostream>
#include <vector>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    int s, i;
    cin >> s;
    
    vector<int> v(n);
    
    for(i=0; i<n; i++) {
    	cin >> v[n];
    }
    
    for(i=0; i<n; i++) {
    	cout << v[n] << endl;
    }
	return 0;
}

  위 코드에서 7번째 줄에 해당하는 ios_base::sync_with_stdio(false); 를 주목해야 한다. 입력과 출력을 할 때에는 버퍼를 사용하는데 ios_base::sync_with_stdio(false);를 사용하지 않는다면 동기화 되어 있다고 표현을 하는데 이는 C++ 표준 스트림과 C 표준 스트림을 병행해서 쓸 수 있다는 것을 말한다. 이렇게 병행해서 사용하면 속도가 느려지게 된다. 

 따라서, ios_base::sync_with_stdio(false); 이 문장은 동기화를 하지 않겠다고 선언하는 것이며 이는 C++ 표준 스트리만 사용하겠다는 것이 된다. 따라서, 위 문장이 선언된 프로그램은 독립된 버퍼만을 사용하므로 속도적 측면에서 개선될 수 있다.

 속도 비교를 해보면 다음과 같다. 이는 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정한 것이다.

   2. 만능 헤더 파일   

//#include <iostream>
//#include <vector>

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

int main() {

    ios_base::sync_with_stdio(false);
    int s, i;
    cin >> s;
    
    vector<int> v(n);
    
    for(i=0; i<n; i++) {
    	cin >> v[n];
    }
    
    for(i=0; i<n; i++) {
    	cout << v[n] << endl;
    }
	return 0;
}

 매번 프로그래밍을 할 때 필요한 헤더를 선언하는 것은 불편한 일이다. 하지만, 위의 코드 처럼 bits/stdc++.h 헤더를 하나만 선언하고 cin, cout 같은 입출력 객체와 vector 컨테이너를 맘대로 쓸 수있는 방법이 존재했다. 

 bits/stdc++.h 헤더란 표준 라이브러리를 모두 포함하고 있는 헤더이다. 하지만  이 헤더는 GCC 전용 라이브러리이므로 GCC를 지원하는 대회 환경에서 사용해야 한다. 다행히도 대부분의 프로그래밍 환경에서는 이를 지원한다.

 이렇게 편리하데 단점은 없을까? 결론부터 말하자면 단점이 존재한다. 먼저 이 헤더는 위에서 언급한 것처럼 GCC가 아닌 다른 컴파일러로 코드를 컴파일 할 경우에는 실패한다. 또한, 불필요한 헤더를 많이 포함하므로 컴파일 하는데 시간이 길어진다. 마지막으로는 이식성이 떨어진다. 이식성이란 특정 환경에서 동작하는 SW 프로그램이 다른 환경으로 변경해도 동작할 수 있는 성질을 말한다.

 Dev C++에서도 바로 사용할 수는 없고 컴파일러 설정을 해야한다. 맨 위에서 [도구] - [컴파일러 설정]을 누르고 빨간색으로 표시된 부분에 -std=c++11을 추가한다.

[참고]

www.acmicpc.net/blog/view/56

www.acmicpc.net/blog/view/57

   1.  STL(Standard  Template Library)  

  C++ 의 표준 템플릿 라이브러리 (STL) 은 간단하며 효율적인 도구이다.  보통 C++의 STL은 임의 타입의 객체를 보관할 수 있는 컨테이너(Container)와 컨테이너에 보관된 원소에 접근할 수 있는 반복자(Iterator), 그리고 반복자들을 가지고 일련의 작업을 수행하는 알고리즘(algorithm)을 의미한다.

 여기서 컨테이너는 객체가 어떤 타입이든 자유롭게 사용할 수 있다는 것이다. int나 string 같은 일반적인 타입이 아니라 임의로 만든 클래스의 객체들이여도 라이브러리의 기능들을 모두 활용할 수 있다.

   2. 벡터(Vector)   

 그 컨테이너 중에서도 오늘은 벡터(Vector)에 대해서 알아본다. 먼저, 벡터는 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(Sequence Container)의 한 종류이다. 다른 예로는 list, deque가 있다. 

 벡터는 가변길이 배열로 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다.

 사용법은 다음과 같다. 먼저, vector 라이브러리를 include 시켜줘야 한다. 그리고, vector<타입> 변수 명; 과 같이 선언해준다. 임의의 원소에 접근하는 것은 배열처럼 [] 를 사용한다. 또한, 맨 뒤에 원소를 추가하거나 제거하기 위해서는 push_back 과 pop_back 함수를 사용하면 된다. 임의의 위치에 있는 원소에 접근은 O(1) 로 수행하고 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시 O(1) 에 수행한다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> v;
  v.push_back(1);  
  v.push_back(2);  
  v.push_back(3);   

  for(vector<int>::size_type i = 0; i < v.size(); i++) {
    cout << "vector 의 " << i + 1 << " 번째 원소 : " << v[i] << endl;
  }
  
  return 0;
}

 11번째 줄을 보면 size_type의 변수 i가 존재한다. 이는 벡터의 크기를 리턴하는 함수인 size가 리턴하는 값의 타입이 size_type 멤버 타입으로 정의되어있기 때문이다.

   3. 벡터의 특성   

 맨 뒤에 원소를 추가하는 작업(push_back)은 정확히 시간복잡도로 따지면 분할상환의 뜻을 가진 amortized O(1)이라고 한다.  보통 벡터의 경우 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당해 놓고 있기 때문이다. 예를 들어, 위의 예에서 원소의 개수가 3개지만 벡터는 이미 10가 정도 저장할 수 있는 공간을 미리 할당해 놓는 다는 것이다. 따라서, 새로운 원소를 추가해도 그냥 이미 할당된 공간에 그 원소를 쓰기만 하면 된다.

 따라서 대부분의 경우에 원소의 추가, 삭제는 O(1)으로 이루어진다. 하지만,  할당된 공간을 다 채웠을 때는 얘기가 달라진다.  이 때는 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사하는 수 밖에 없다. 

 이 경우 nn 개의 원소를 모두 복사해야 하기 때문에 O(n)의 시간복잡도가 발생한다. 하지만 O(n)으로 수행되는 경우가 매우 적기 때문에, 전체적으로 평균을 내보았을 때 O(1)로 수행이 된다. 그림으로 설명하면 다음과 같다. 

 또한, 맨 뒤에 원소를 추가하거나 제거하는 것(O(1))은 빠르지만, 임의의 위치에 원소를 추가하거나 제거하는 것은 O(N)으로 느리다. 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 줘야하기 때문이다. 따라서 이는 N번의 복사가 필요하다.

 따라서, 어떠한 작업을 하냐에 따라서 속도차가 매우 크기 때문에  C++ 표준 라이브러리를 잘 사용하기 위해서는 내가 이 컨테이너를 어떠한 작업을 위해 사용하는지 정확히 인지해 적절한 컨테이너를 골라야 한다. 

   4. 순회(for)로 원소 접근하기   

 컨테이너를 순회(for)문으로 접근하는 경우가 많은데 이는 포인터와 같은 객체인 반복자(Iterator)를 사용하는 경우도 있고 C++ 11버전 부터는 범위 기반 for문을 제공한다. 순회문에 들어갈 매개변수는 컨테이너의 원소를 받을 변수와 컨테이너를 정의해주면 된다. 이것은 e 변수에 v[i]를 한 것과 같다. 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> v;
  v.push_back(1);  
  v.push_back(2);  
  v.push_back(3);   

  for(int e : v) {
    cout << "원소 : " << e << endl;
  }
  
  return 0;
}

   5. 벡터의 생성자    

#include <iostream>
#include <vector>
using namespace std;

int main() {

   	1. 빈 벡터 생성
 
 	  vector<int> v; 
 
	2. 0으로 초기화 된 10개의 원소를 가지는 벡터 생성
 
 	  vector<int> v(10);
    
 	3. 5로 초기화 된 10개의 원소를 가지는 벡터 생성
 
 	  vector<int> v(10, 5);
    
 	4. v1 벡터를 복사해서 벡터 생성
 
 	  vector<int> v(v1);
}

   6. 벡터의 멤버변수    

#include <iostream>
#include <vector>
using namespace std;

int main() {

	vector<int> v;
   	vector<int> v1;

   	1. v.front(); 		==> 벡터의 첫 번째 원소를 참조한다.
 	
	2. v.end(); 		==> 벡터의 마지막 원소를 참조한다.
    
 	3. v.push_back(2);	==> 벡터의 마지막 원소 뒤에 2를 추가한다.
    
 	4. v.pop_back();	==> 벡터의 마지막 원소를 삭제한다.
 
	5. v.size(); 		==> 벡터의 원소의 개수를 리턴한다.
    
      	6. v.capacity(); 	==> 벡터의 할당된 메모리의 크기를 리턴한다.
    
    	7. v.insert(2, 3);	==> 벡터의 2번째 위치에 3을 삽입하고 삽입한 곳의 iterator를 반환한다.
    
    	8. v.insert(2, 3, 4);	==> 벡터의 2번째 위치에 3개의 4를 삽입하고 삽입한 곳의 iterator를 반환한다.
        
        9. v.swap(v1);		==> v 벡터와 v1 벡터의 요소와 capacity를 모두 바꿔준다.
}

   7. 벡터 여러개 생성하기    

#include <iostream>
#include <vector>
using namespace std;

int main() {

	1. 벡터를 N개 생성
	
    		vector<int> v[3];     // v라는 벡터를 3개 생성
        
    	[비교] 벡터를 하나만 생성
    
    		vector<int> v1(3);     // size가 3인 벡터를 1개 생성
            
            
     	2. 벡터 원소 넣기
        
     		v[0].push_back(1);
            	v[0].push_back(2);
            	v[1].push_back(1);
            	v[2].push_back(1);
            	v[2].push_back(2);
                v[2].push_back(3);
                
	3. 원소 접근
        
       		cout << v[0][2] << endl;
          	cout << v[1][1] << endl;

   8. 벡터 Pair   

#include <iostream>
#include <vector>
using namespace std;

int main() {

	1. 동시에 Int 값을 넣을 수 있는 Pair 벡터 선언
	
    		vector<pair<int, int> > v[3];     // [주의] <pair<int, int> > 이 부분에서 끝에 띄어써야 함

            
     	2. 벡터 원소 넣기
        
     		v[0].push_back({3, 5});
            	v[0].push_back({2, 7});
            	v[1].push_back({1, 3});
            	v[1].push_back({5, 6});
            	v[2].push_back({2, 7});
                
	3. 원소 접근
        
          	cout << v[1][1].first << " " << v[1][1].second << endl;
            	cout << v[0][0].first << " " << v[0][0].second << endl;

   1.  C    

 프로그래밍을 하다보면 동적으로 메모리를 할당해 배열을 생성해야하는 경우가 발생한다. C에서는 그 역할을 malloc 함수가 한다. 이 함수는 memory allocation 의 약자이며 <stdlib.h> 라이브러리에 정의되어 있기 때문에 먼저, 선언하는 작업이 필요하다.  

또한, 이 함수는 인자로 전달된 크기의 바이트 수 만큼 메모리 공간을 할당한다. 입력한 n개인 int 형 배열을 만들기 위해서는 int 의 크기 * n이 된다. 이 때, int 타입의 크기를 정확하게 알기 위해서 sizeof 키워드를 사용한다.

 주의할 점이 있는데 이 함수는 자신이 할당한 메모리의 시작 주소를 리턴한다. 이 때, 리턴형이 (void *) 형이므로 (int *) 형으로 형변환 하는 작업을 해야한다.  

 그리고 초기화 하는 방법으로 순회(for)를 돌아 값을 넣어주거나 <string.h> 라이브러리의 memset 함수를 사용한다. 이 함수는 어떤 메모리의 시작점부터 연속된 범위를 특정 값으로 지정하고 싶을 때 사용하는 함수이다. 첫 번째 인자로는 메모리의 시작점, 두 번째 인자로는 채우고자 하는 특정 값, 세 번째로는 채우고자 하는 메모리의 크기(바이트 수)가 들어간다. 

1. C에서의 동적배열

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n;
scanf("%d", &n);
int *arr = (int *)malloc(sizeof(int) * n);
memset(arr, 0, n * sizeof(int));

free(arr);

동적인 배열을 다 사용하면 메모리를 다시 돌려주어야 하는데 이것은 free 함수가 한다. 이 함수는 메모리 누수를 방지하는 역할을 한다.   

   2. C++   

C에서는 malloc과  free 함수를 통해서 메모리를 할당하고 해제하였는데 C++에서는 new와 delete라는 연산자를 활용하여 메모리를 관리한다. new는 malloc() 함수와 달리 메모리 크기를 정하지 않고 동적으로 할당한다.

2. C++에서의 동적배열

#include <iostream>

int n;
cin >> n;
int *arr = new int[n];

delete[] arr;

   1. char  to int   

 첫 번째 방법은 아스키 코드를 이용하는 방법이다. char 변수는 1 byte 정수이다. 하지만, char 자료형이 정수일지라도 아스키 코드로 해석된다. 아스키는 American Standard Code for Information Interchange의 약자로 영어 문자 또는 특수문자를 0에서 127 사이의 숫자(아스키 코드)로 나타낸다. 예를 들어 숫자 0은 코드 48이고 9는 57이다. 그리고 'a' 문자는 코드 97이다. 'b'는 98이다. 

 이러한 아스키 코드를 이용하여 char형 데이터를 int 형으로 바꾸는 방법은 48을 빼주는 방법과 '0'을 빼주는 방법이 있는데 예제는 다음과 같다. 

// 1. 48을 빼주는 방법

char one = "1";
int num = one - 48;

scanf("%d", num + 3); 		// 4


// 2. '0'을 빼주는 방법

char one = "1";
int num = one = '0';

scanf("%d", num + 4); 		// 5

   2. char 배열 길이만큼 순회(for)문 돌기   

char 배열의 길이만큼 순회(for)문을 도는 방법은 많은데 그 중 두 가지를 소개한다. 첫 번째 방법은 cstring 라이브러리의 함수 strlen()를 쓰는 방법이다. 마지막으로는 데이터가 없는 인덱스의 값이 '\0'임을 이용하는 방법이다. 두 번째 방법은 아래 그림을 참조하면 된다. 

 두 가지 예제는 다음과 같다.

// 1. cstring 라이브러리 strlen() 함수 이용하기

#include <cstring>

char array[51];
scanf("%s", &array);			// g0en2Ts8eSoft 입력

int len = strlen(array);        	// 13

for(int i=0; i<len; i++) {
	// 작업
}


// 2. 값이 없는 index의 값이 '\0'임을 이용하기

char array[51];
int res = 0;
scanf("%s", &array);			// g0en2Ts8eSoft 입력

for(int i=0; array[i] != '\0'; i++) {
	if(a[i]>=48 && a[i]<=57){
		res = res * 10 + (a[i] - 48);
	}
}