[C++/STL] 알고리즘을 위한 팁(21.02.16 수정)

 

 

어느 자료구조를 사용해야 하는가?

 

 - 배열(Array) : 데이터에 빠른 접근과 수정, 삭제가 필요할 때. 크기가 제한되기 때문에 크기를 고려해야 한다.

 

 - 벡터(Vector) : 동적 배열, 배열과 같이 빠른 접근과 수정, 삭제가 필요할 때 사용하지만 크기가 제한되지 않았다.

[C++/STL] 벡터(Vector)

---

 - 스택(Stack) : 데이터를 넣은 역순으로 사용해야 하는 경우(가장 최근에 넣은 데이터 사용) 

[C++/STL] 스택(Stack)

---

 - 큐(Queue) : 데이터를 넣은 순으로 사용해야 하는 경우(제일 처음에 넣은 데이터 사용) 

[C++/STL] 큐(Queue), 우선순위 큐(Priority Queue)

---

 - 덱(Deque) : 맨 처음에 넣은 데이터 & 맨 뒤에 넣은 데이터를 사용해야 하는 경우

[C++/STL] 덱(Deque)

---

 - 셋(Set) : 데이터 수가 많고, 삽입 시 정렬이 필요한 경우나 빠른 데이터를 찾아야 하는 경우 

 

 - 맵(Map) : 셋의 특성과 함께 키에 대응되는 값이 필요한 경우 

[C++/STL] 셋(Set), 맵(Map)

---

 - 우선순위 큐(Priority_queue, Heap) :  삽입 시 정렬이 필요하고 최대, 최소만 필요한 경우 

[C++/STL] 큐(Queue), 우선순위 큐(Priority Queue)

---

 - 해쉬(unodered_map, Hash) : 정렬이 필요하지 않고, 빠른 삽입, 삭제가 필요한 경우

[C++/STL] 셋(Set), 맵(Map)

 - multiset 보다는 priority_queue가 더 빠르다. 그러므로 priority_queue를 이용하자.

 

---

 

 

- 변수를 선언할 때 메모리를 얼마나 사용할 지 생각해서 선택해야 한다.

---

시간 복잡도

 

 - 대략 1초에 1억번 연산이 가능하다고 생각하면 된다..

 

 - N=100,000,000 : O(N), O(logN)

 

 - N=1,000,000 : O(NlogN)

 

 - N=10,000 : O($N^2$)

 

 - N=20 : O($2^N$)

 

---

 

입출력

 

 - cin, cout보다 printf, scanf가 더 빠르다.

 

 - 별도의 설정을 해주면 cin, cout도 빠르게 사용할 수 있다.

int main(void) 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cout << "입출력 테스트" << endl;
	return 0;
}

 

 - endl 보다 \n이 더 빠르다.

 

 - 데이터 입력 시 scanf는 공백으로 구분하지만, cin은 자동으로 구분한다.

 

---

 

문자열

 

 - String에서 Size는 O(1) 이고, Strlen은 O(n)이다. 그래서 Size를 사용해야 한다.

 

 

---

 

함수 선언

 

 - 함수에 배열이나 벡터등을 전달하는 경우 주소만 전달해라.

int solution(int number, vector<int> &v)
{

	// 함수 내용...
	// 벡터등은 & 키워드를 이용하여 주소만 전달하여 사용하는것이 효율적이다.
    
}

 

---

 

수 관련

 

 - 절대 값 선언 방법(C++ STL의 cmath에 선언되어 있는 abs를 이용한다.)

#include <cmath>

int solution(int num1,int num2)
{
	return abs(num1-num2);
}

 

 - INT 최대 값(2147483647) // 무한대라는 값을 표현하기 위해 주로 사용된다.

int maxInt = INT_MAX; //INT_MAX는 미리 정의되어 있다.

INT_MAX는 미리 정의되어 있다.

 

---

 

간편 사용

 

 - typedef

typedef pair<int,int> pii;

vector<pii> piiVector;
piiVector.push(make_pair(3,4));

 

 - #define

#define MAX_BLOCK_NUM 1000

int maxNum=MAX_BLOCK_NUM;

 

---

 

 

형변환

 

 - int <-> string 형변환

#include<string>

// int to string
int iNum=30;
string iToS = to_string(iNum);

// string to int
string sNum="300";
int sToI= stoi(sNum);

 

---

 

구조체

 

 - 구조체를 이용하면 좀 더 편리하게 코드를 작성할 수 있다.

struct path {
	int x;
	int y;
	bool isSave;
	int value;
};


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<path> vp;

	vp.push_back({ 0, 0, false, 3 });
	vp.push_back({ 1, 1, true, 4 });
	vp.push_back({0, 3, true, 10});


	return 0;
}

 

---

 

초기화

 

 - C++ 에서는 전역 변수로 선언 시 별도의 초기화를 하지 않아도 기본값으로 초기화 된다.

 - 지역변수는 별도의 초기화가 필요하다.

// 모두 0으로 자동 초기화
int bags[1000];  

int main(void)
{
	// 별도의 초기화 필요
    // 모두 0으로 초기화
	int bagsLocal[10]={0,}; 
    
    return 0;
}

 

 - 지역 변수 배열 초기화 //  fill_n(초기화 하려는 원소의 시작 주소, 원소 개수, 값);

int main(void)
{
	// 별도의 초기화 필요
    // 모두 0으로 초기화
	int bagsLocal[10];
    
    // fill_n(초기화 하려는 원소의 시작 주소, 원소 개수, 값);
    fill_n(bagsLocal,10,-1);
    
    for(int i=0;i<10;i++)
    	cout<<bagsLocal[i]<<endl;
    
    return 0;
}

 

 - 2차원 배열 초기화

int main(void)
{
	// 별도의 초기화 필요
    // 모두 0으로 초기화
	int bagsLocal[10][11];
    
    // fill(초기화 하려는 원소의 시작 주소, 마지막 주소, 값);
    fill(&bagsLocal[0][0],&bagsLocal[0][0] + (10*11),-1);
    
    return 0;
}

---

 

좌표 사용

 

 - 2차원 배열을 이용하여 좌표값 설정

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

for(int i=0; i<4; i++)
{
    //x, y는 기준 좌표
    int nx = x + dx[i];
    int ny = y + dy[i];
    
    // N은 좌표의 최대 값
    // 배열의 범위에서 벗어나지 않았는지 등을 체크한다.
    if(nx >= 0 && ny >= 0 && nx < N && ny < N)
    {
    	// 해당 좌표에서 실행할 내용
    	...
    }
}

 

 

---

 

순열, 조합

 

 - #include<algorith> 

 

 

순열

 

 - 순열의 값 : nPr = n! / (n-r)!

 

 - next_permutation을 이용하여 순열을 구할 수 있다.

 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vector<int> v{ 3,45,12,6 };
    
	// 오름차순 순열 구하기
	// 오름차순 정렬 반드시 필요
	sort(v.begin(), v.end());

	do {
		for (auto n : v) {
			cout << n << " ";
		}
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));



	return 0;
}

 - prev_permutation을 이용하면 next_permutation 순열을 역으로 출력할 수 있다.

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vector<int> v{ 3,45,12,6 };

	// 내림차순 순열 구하기
	// 내림차순 정렬 반드시 필요
	sort(v.begin(), v.end(),greater<>());

	do {
		for (auto n : v) {
			cout << n << " ";
		}
		cout << endl;
	} while (prev_permutation(v.begin(), v.end()));



	return 0;
}

 

 

조합

 

 - 조합의 값 : nCr = n! / ((n-r)! x r!)

 

 - next_permutation을 응용하여 조합을 구할 수 있다.

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vector<int> v{ 3,45,12,6 };
    
    // 4C2구하기. nCr인 경우 n개의 원소 중 1을 뒤에서 r개 선언하면 된다.
	vector<bool> comb{ 0,0,1,1 };

	do {
		for (int i = 0; i < comb.size(); i++) {
			if (comb[i]) {
				cout << v[i] << " ";
			}
		}
		cout << endl;
	} while (next_permutation(comb.begin(), comb.end()));



	return 0;
}

 

 

 

 

---

 

bits/stdc++.h 헤더 파일

 

 - C++을 이용하여 알고리즘 문제를 풀기 위한 표준 라이브러리 헤더파일 모음

 

 - 비표준 헤더파일이기 떄문에 컴파일러마다 사용이 불가능할 수 있다.