[Step 1.5] 코딩 테스트에서 꼭 알아야 할 C++ 문법

빌트인 데이터 타입(배열)

int main()
{
	int a[5];
	a[3]=2;
	cout<<a[3]<<endl;
	
	return 0;
}

==> 임의 위치에 원소 삽입할 경우 O(N), 맨 뒤에 원소 삽입 할 경우 O(1)

동적 배열

int* dynamicArr=new int[10];//동적 배열 메모리 선언

delete[] dynamicArr;// 동적배열 메모리 해제


int size;
cout<<"배열 크기는?";
cin<<size;
int* arrSize=new int[size];
delete[] arrSize;

문자열

C와 다른점 =⇒ 문자의 연속으로 구성되며 \0 문자로 종료되지 않는다.

문자열 관련 함수
string str1="Hello, World!"
cout<<str1.substr(7,5); ==> 출력: World //7번째 문자인 W부터 자신을 포함한 5개 출력

c++ 에서 string::npos 는 size_t 로 정의된 특수값이다. find함수 수행시 찾는 문자열이 없을때 npos를 반환한다.

size_t pos = str.find(toFind);
if (pos != std::string::npos) {
    std::cout << "'" << toFind << "' found at position " << pos << std::endl;
} else {
    std::cout << "'" << toFind << "' not found" << std::endl;
}

STL

==>C++에서 제공하는 템플릿 기반의 표준 라이브러리

1. 반복자

//벡터
vector<int> vec={1,2,3,4,5};

//it의 타입은 vector<int> ::iterator
//==> 순방향 반복자를 사용해 벡터의 요소를 순회하고 출력
cout << "Vector elements: ";
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " "; // 반복자가 가리키는 요소를 출력
}
cout << endl; 

//==> 역방향으로 출력할때는 rend(), rbegin()을 사용
 cout << "Vector elements in reverse: ";
for (vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
  cout << *rit << " "; // 역방향 반복자가 가리키는 요소를 출력
}
    cout << endl; // 출력: Vector elements in reverse: 5 4 3 2 1

 

//리스트
list<int> lst={1,2,3,4,5}
//it의 타입은 list<int> ::iterator
//==> 순방향 반복자를 사용해 리스트 요소를 순회하고 출력
for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
    cout << *it << " "; // 반복자가 가리키는 요소를 출력
}
cout << endl;


//==> 역방향으로 출력할때는 rend(), rbegin()을 사용
cout << "List elements in reverse: ";
  for (list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) {
    cout << *rit << " "; // 역방향 반복자가 가리키는 요소를 출력
 }
cout << endl;

==> 둘 다 타입은 다르나 접근하는 문법은 동일하다.

컨테이너 : vector, list, map등

반복자는 컨테이너의 요소를 순회하는데 사용한다.

반복자를 사용하면 컨테이너 내부 구현에 독립적으로 요소를 처리 가능하다. ==> 동일한 문법으로 원소 처리 및 접근 가능.

2. 컨테이너

==> 데이터를 저장하고 관리하는 저장소

- vector(거의 배열처럼 사용한다.)

=> 원소의 수에 따라 내부 배열 크기가 자동으로 증가!

=> but 맨 앞 혹은 중간에 원소를 삽입 하는 경우 비효율적 O(N)

=> 맨뒤에 원소를 삽입하는 경우는 효율적 O(1)

//초기화 방법
vector<int> vec1;// => 공간을 지정 안해줬기 때문에 vec1[2]=0 ; 이런식으로 접근 x

vector<int> vec2(5);// 크기 지정, 모든 원소를 0으로 초기화 함.

vector<int> vec3={1,2,3,4,5}; //벡터 초기화.

벡터를 사용해야 하는 경우

1. 동적 배열이 필요한 경우.
2. 임의 접근이 필요한 경우
3. 데이터의 크기가 자주 바뀌는 경우

벡터가 비효율적인 경우

1. 값을 자주 찾아야 할 때 =⇒ set 이나 unorderd_set을 사용
2. 맨 앞에 원소를 추가해야 할 때 =⇒ deque나 list를 사용

- set

=>중복을 허용하지 않는 순서가 있는 집합

⇒균형 이진트리(레드 블랙 트리)로 동작함. 원소가 자동으로 정렬이 된다.

//set
//초기화
std::set<int> s;
auto it=s.find(10);
if(it!=s.end()) //=> 만일 set에 찾으려는 값이 없으면 end()를 반환
{
	std::cout << "Found: " << *it << std::endl;
}
else
{
	...
}

set을 사용해야하는 경우

1. 중복을 허용하지 않는 경우
2. 정렬된 순서가 필요한 경우
3. 탐색,삽입,삭제의 성능이 중요한 경우

set을 사용하지 말아야 하는 경우

1. 중복된 원소를 허용해야 하는 경우
2. 정렬이 필요 없는 경우=⇒ SET사용하면 오히려 성능이 떨어짐 왜냐하면 정렬을 할 때 시간 복잡도가 발생하기 때문이다.

ex) 이중 for문을 돌린다 생각해보자

       set을 쓰면 N^2logN이 걸리지만

       vector을 사용하면 그저 N^2밖에 안걸림

  3. O(1) 시간 복잡도가 필요한 경우 : 빈번한 삽입과 삭제가 필요한 경우

std::unordered_set<int> unorderedSet;
unorderedSet.insert(5);
unorderedSet.insert(10);
unorderedSet.erase(5);
if(unorderedSet.find(10)!=unorderedSet.end())
{
	....
}

 

- map

=> key-value로 이루어져 있음.

=> 중복허용 X, 원소가 자동으로 정렬(레드 블랙 트리 사용)

=>키를 기준으로 정렬

 

map 사용해야 하는 경우

1. 키와 값의 쌍을 효율적으로 저장할 때
2. 키를 기준으로 정렬된 순서로 데이터 저장 할 때
3. 삽입,삭제,탐색 연산의 시간복잡도가 O(logN)이면 충분히 빠른경우

map을 사용하지 말아야하는 경우

1. 키의 중복으로 허용해야 할 때
2. 키의 순서가 중요하지 않은 경우 => unorderd_map이 더 효율적
3. 데이터의 크기가 매우 크고, 삽입 및 탐색 연산이 더 빠른 시간복잡도를 요구하는 경우

//map 선언
map<int,string> map1;
//요소 삽입
map1.insert({1,"abc"});
// 맵의 모든 요소 출력
cout << "Initial map content:\n";
for (const auto& pair : studentMap) {
    cout << "ID: " << pair.first/*키*/ << ", Name: " << pair.second/*값*/ << endl;
}
//맵의 요소 탐색
//없으면 end()반환.
 auto it = map1.find(102);
  if (it != map1.end()) {
     cout << "\nStudent with ID 102 found: " << it->second/*값 출력.*/ << endl;
 } else {
     cout << "\nStudent with ID 102 not found.\n";
 }
//맵의 요소 업데이트
map1.insert({1,"dd"});// 존재하면 업뎃, 존재하지 않으면 삽입
//맵의 요소 삭제
map1.erase(1);

//[] 연산자와 find의 차이
map1[1] ==> 존재 하는 키
map2[2] ==> 존재 하지 않는키이다.
==>[]연산자를 사용하면 접근하는 것 만으로도 기본값이 설정되어 []연산자 보다는 find를 사용.

 

- unordered_map

=> key-value로 이루어진 순서 없는 집합.

=>중복 허용 X, 해시 테이블로 관리되므로 자동정렬 X

=>삽입 시 같은 키가 있으면 삽입이 아니라 업데이트를 함.

=> 정렬이 없기 때문에 시간복잡도는 평균 O(1)

=> 사용법은 map이랑 같음. 정렬이 안되어 있는 것이 차이.

unordered_map<int,string> map1;
...이하 기존 map이랑 사용법 동일

- unordered_set

=> 중복 허용 x, 순서 x

=> 원소가 해시 테이블로 관리되어 자동정렬이 안됨.

unordered_set을 사용해야 하는 경우

1. 중복되지 않는 값의 집합을 효율적으로 저장, 관리 해야 할 때
2. 원소의 순서가 중요 하지 않을 때.
3. 평균 O(1)의 시간복잡도를 갖는 빠른 삽입, 삭제, 탐색이 필요할 때

unordered_set을 사용하지 말아야 하는 경우

1. 원소의 순서가 중요할 때 ⇒set사용
2. 해시 함수가 비효율적으로 동작하여 충돌이 많이 발생할 경우
3. 데이터의 크기가 매우 크고, 메모리 사용이 중요한 경우 =⇒ 해시 테이블은 메모리 사용량이 많을 수 있음

unordered_set<int> set1;
... 이하 기존 set과 동일

set과 map을 구분 할 때 =⇒ 값만 필요한가? 키와 값이 둘다 필요한가? 에 따라 구분된다.

- stack => LIFO(Last In First Out)

=> 탐색 및 임의 접근 불가

 

- queue => FIFO(First In First Out)

=> 탐색 및 임의 접근 불가

 

3. 알고리즘

- count

=>데이터를 세는 함수, 특정 값의 출현 횟수를 반환

 

- sort

=>데이터 정렬.

=> default : 오름차순으로 정렬

=> 사용자 정의형 일때는 무조건 정렬 기준전달(ex : struct같은 구조체 정렬 할 때는 정렬 기준을 전달해 줘야함)

//사용자 정의 비교함
bool compare(int a, int b)
{
//sort함수에서 비교시 이 함수가 true를 반환하면 a가b보다 앞에 있어야 한다고 판단해 
//a와 b의 위치를 교환 하지 않음 따라서 내림차 순으로 정렬이 됨.
	return a>b;
}
int main()
{
	vector<int> arr={5,2,3,4,6,7};
	
	sort(arr.begin(),arr.end(),compare);
	for(int n : arr)
	{
		cout<<n<<' ';
	}
	//==>6,5,4,3,2 출력. 만일 sort안에 compare이 없으면 오름차순 정렬 2 3 4 5 6
	/*
		struct Axis
		{ int x; int y;} ==> 구조체를 정렬 할 때 정렬 함수를 정의해서 정렬하자
	*/
	
	
arr={5,2,3,4,7,6}
sort(arr.begin(),arr.begin()+3)//제일 앞에서 3개까지만(맨마지막은 포함 x) 정렬하자.	
//출력 =>2 3 5 4 7 6

//역방향 정렬 벡터 
sort(arr.rbegin(),arr.rend());//==>내림차순 정렬

}

 

- unique

=> 인접한 중복 요소를 뒤로 재배치 하는 함수

=> 함수 사용 후 중복 요소를 뒤로 재배치 하는 것이지 제거된 것이 아니므로 erase함수를 추가로 사용 해야 함

주의 할 점

1. 정렬 된 상태에서 사용 : unique함수는 인접한 중복 요소만 재배치 한다. 따라서 정렬을 해준 상태에서 사용.따라서 1 2 2 2 3으로 정렬을 해주고 unique를 사용해야 인접한 요소를 뒤로 재배치 할 수 있다.
2. ex) 1 2 2 3 2 =⇒ 여기서 마지막 2는 인접하지 않았으므로 중복된 요소가 아니라고 판단함
3. return 값 : 새로운 끝 부분을 반환.
4. 백터 크기 조정 : 중복 요소를 재배치 한 후 erase를 통해 삭제 해야 함

vector<int> arr={3,1,2,3,2,4,1,5,3};
//==>만일 이 상태에서 unique를 사용하면 요소중 인접한 요소들은 중복 되지 않는다 
//판단해 그대로 나옴 
//출력 : 3 1 2 3 2 4 1 5 3

sort(arr.begin(),arr.end());// 따라서 이와 같이 정렬을 해 주고
auto arrSort=unique(arr.begin(),arr.end()); //중복요소를 재 배치 해주고
//출력: 1 2 3 4 5 x x x x x는 쓰레기값. 따라서 삭제 해줘야함.
arr.erase(arrSort,arr.end())// arrSort는 중복요소를 재배치 후 끝 부분을 반환 하므로
//그 위에 중복 요소는 erase를 이용해 삭제 해줌.
//출력: 1 2 3 4 5 가 나옴

 

- binary_serach (이진 탐색)

=> 정렬된 범위에서 특정 값을 찾는 함수 —> 반드시 정렬 된 상태여야 함

=> 값이 존재 하면 true 없으면 false반환

 

- max_element / min_element => 최대 / 최소 값

=> 선형탐색 사용. 따라서 O(N)

 

- next_permutation

=> 주어진 범위의 요소들에 대해 다음 순열을 생성

=> 정렬이 되어 있어야 함

=> return 값: 다음 순열이 존재 하면 true , 없으면 false

void print_permutations(vector<int> v) {
    do {
        // 현재 순열 출력
        for (int num : v) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(v.begin(), v.end())); => 다음 순열이 있을때 까지 계속 출력
}
int main()
{
	vector<int> v = {3, 2, 1};
	//=> 만일 정렬을 안하고 next_permutation을 하면 1 2 3의 끝 순열은
	// 3 2 1이므로 만일 위에 함수를 실행하면 그냥 3 2 1만 출력되고 끝 
	//따라서 3 2 1을 정렬하여 1 2 3을 만들고 그 이후에 순열을 출력해주면 된다
	sort(v.begin(), v.end());// 정렬 후
	vector<int> v_sorted = v;
  	print_permutations(v_sorted);
//출력
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
	
}

 

출처 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런