[코테 합격자 되기] 04/05장 반드시 알아야 할 C++ 문법

# 데이터 타입 크기

아래의 표를 살펴보면,

운영체제에 따라 데이터 타입 크기가 달라지는 것은 long과 pointer이다

 

# 동적 배열

동적 배열은 정적 배열과 달리 런타임 중에

배열의 개수를 설정할 수 있다

또한, 동적 배열은 힙에 할당이 되기에 new로 생성하고

반드시 delete를 해줘야 한다

int size;
cin >> size;
int* dynamicAttary = new int[size];

...

delete[] dynamicArray;// 반드시 delete

 

# 배열의 성능

맨 뒤 삽입은 O(1)

맨 앞 삽입은 O(N)

 

# 문자열의 메서드

- 초기화

- replace (문자열 대체)

- + operator (문자열 추가)

- substr (부분 문자열 추출)

- find (문자열 검색)

- length (문자열의 길이)

 

특히, find의 경우는

찾으면 찾은 문자열이 몇번 인덱스에 시작하는지를 반환하고

못 찾으면 string::npos를 반환한다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/reference/string.cpp

 

# 코테에 꼭 필요한 STL

- STL 정의

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

코테에서는 컨테이너와 알고리즘을 중점적으로 공부해야 한다

 

- STL의 3종류

 

- 반복자

반복자를 통해 모든 알고리즘과 컨테이너를 동일한 방법으로 순회할 수 있다

코테에서는 순방향/역방향 반복자를 알아둬야 한다

순방향 반복자는 begin(), end()

역방향 반복자는 rbegin(), rend() 이다

여기서 end()와 rend()는 유효하지 않은 영역이다

vector, list는 서로 다른 컨테이너지만 반복자를 통해 동일하게 접근한다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/iterator.cpp

 

- 컨테이너

STL에서 제공하는 데이터를 저장하고 관리하는 저장소이다

각 컨테이너의 시간복잡도와 특징을 잘 알아두어야 한다

 

1) vector

동적배열이기에 capacity와 size를 자동으로 증가시킨다

임의접근이 가능하고 O(1)으로 효율적이다

맨 뒤에 원소 삽입은 O(1)으로 효율적이다

맨 앞이나 중간에 원소 삽입은 O(N)으로 비효율적이다

탐색은

인덱스 접근으로 탐색은 O(1),

순차탐색(find)은 O(N),

정렬을 하고 이진탐색(binary_search)은 O(logN)이 걸린다

순차탐색의 find를 사용하는 경우에 원하는 값을 못 찾으면, end()를 반환한다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/vector.cpp

 

2) set

중복 X

삽입, 삭제와 동시에 정렬한다 (AVL로 동작)

삽입/삭제/탐색이 모두 O(log N)이다

만약, 중복이 필요하면 multiset을 사용하면 되는데 코테에서는 거의 사용되지 않는다

 

추가적으로, set과 map은 삽입/삭제 시 자동정렬이 되기에 정렬이 필요 없는 경우에는 비효율적이다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/set.cpp

 

3) map

set과 모든 것이 동일하지만, key value 쌍으로 key를 통해 접근하는 것이 핵심이다

key 중복 X (만약, 중복된 key 삽입을 하면 value가 덮어쓰기 된다)

삽입, 삭제와 동시에 key를 정렬한다 (AVL로 동작)

find 연산자와 유사한 [] 연산자는 사용하지 않는 것이 좋다

[] 연산자의 경우에는

존재하지 않는 key를 []를 통해 찾는다면,

해당 키와 기본값을 설정해서 새로 만들어버리기 때문이다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/map.cpp

 

4) unordered_map

중복 X (만약, 중복된 key 삽입을 하면 value가 덮어쓰기 된다)

정렬 X (HASH로 동작)

삽입/삭제/탐색 평균적으로 O(1)이고, 최악의 경우는 O(N)이다

 

추가적으로, 해시 함수에 따라 원소 순서가 결정된다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/unordered_map.cpp

 

5) unordered_set

중복 X 

정렬 X (HASH로 동작)

삽입/삭제/탐색 평균적으로 O(1)이고, 최악의 경우는 O(N)이다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/unordered_set.cpp

 

6) stack

중복 O

LIFO

탐색 X, 임의접근 X

삽입/삭제 O(1)

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/stack.cpp

 

7) queue

중복 O

FIFO

탐색 X, 임의접근 X

삽입/삭제 O(1)

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/queue.cpp

 

- 알고리즘

1) count

해당 값의 개수를 반환하는 함수이다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/count.cpp

 

2) sort

정렬을 해주는 함수이다

정렬 기준을 전달하지 않으면, 오름차순으로 동작한다

bool 타입을 반환하는 정렬함수를 직접 설정하면 사용자 정의로 동작한다

또한, 사용자 정의형 (ex. 구조체, 클래스)은 반드시 정렬함수를 인자로 작성해야 한다

사용자 정의 bool 타입이 false를 반환할 때 스왑이된다

시간복잡도는 O(NlogN)으로

분할하는 단계에서 O(logN)
한 번씩 모든 원소들을 비교하며 병합 및 정렬하는 단계에서 O(N)가 소요된다

 

그리고

sort 정렬의 범위는 ≤ < 이기 때문에

반드시 주의해야 한다

 

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/sort.cpp

 

3) unique

인접한(연속적인) 중복요소를 하나만 남기고 뒤로 재배치하는 함수이다

ex. 1 2 2 3 3 3 4 -> 1 2 3 4 2 3 3

중복되어 재배치된 부분의 시작지점을 반환한다

인접한 것만 체크하기에 모든 원소에 적용하려면, 미리 정렬해놓아야 한다

삭제는 해주지 않는다. 삭제를 원한다면, erase를 통해 삭제를 해야 한다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/unique.cpp

 

4) binary_search

반드시 정렬을 해줘야 정상적으로 사용 가능하다

찾는 값의 유무에 따라서 true/false 반환한다

이진 탐색이기에 O(logN)의 시간복잡도가 걸린다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/binary_search.cpp

 

 

5) max_element, min_element

범위 내에서 가장 큰/작은 원소의 위치를 반환한다

선형 탐색으로 O(N)의 시간복잡도가 걸린다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/max_element.cpp

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/min_element.cpp

 

6) next_permutation

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

아래의 주의사항을 지킨 실제코드(ex. 순열을 출력하는 방법)를 함께 이해하는 것이 중요하다

시간 복잡도는 O(N * N!)이다

 

주의점 1)

다음 순열 생성해 주기에 현재 상태는 생략해 버린다

그래서 아래의 실제 코드를 보면,

정렬을 하고 do while을 통해 첫 번째 순열은 일단 출력하는 모습을 알 수 있다

 

주의점 2)

반드시 정렬을 먼저 해줘야 정상 작동한다

 

예시 코드:

#include <iostream>
#include <vector>
#include <algorithm> // for std::next_permutation and std::sort
using namespace std;

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};

    // 반드시 정렬!!!!!!!!!!!!!!!!!!!!!!!!!
    sort(v.begin(), v.end());

    vector<int> v_sorted = v;
    print_permutations(v_sorted);

    return 0;
}

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/next_permutation.cpp