[C++] Day 5 - 자료 구조(1) - 배열과 벡터, 튜플

배열

배열은 파이썬과 다르게 선언한 자료형의 값만 저장할 수 있다.

인덱스를 통해 값에 바로 접근할 수 있고,

새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.

배열의 크기는 처음에 생성할 때 지정할 수 있고 이후 못 바꾼다.

 

구조가 간단하고 빨라서 PS에서 가장 많이 이용된다. 선언하려면 이렇게 하면 된다.

int arr[1001];

 

아래는 C++17에서는 지원하지 않는 문법인데, 백준 환경이 GCC 어쩌구여서 가능한 간단한 배열 초기화 방법이다.(위처럼 그냥 선언만 해주면 배열 안에 뭐가 들어있을지 모른다)

int arr[1001] = {0};

 

이렇게 아예 처음부터 초기값을 정할 수도 있다.

int arr[3] = {3, 4, 5};

 

아래는 내가 파이썬을 쓰면서 유일하게 C++이 부러웠던 점이다. 바로 swap() 함수이다.

이렇게 바로 그냥 두 원소의 위치를 바꿀 수 있다.

swap(arr[i], arr[j]);

 

다음은 배열의 원소를 거꾸로 뒤집는 방법이다.

int arr[5] = {1, 2, 3, 4, 5};
reverse(arr, arr+5); //reverse(begin(arr), end(arr)); 이렇게 해도 됨

 

다음은 배열의 원소를 특정 값으로 채우는 방법이다.

bool prime[10001];
fill(prime, prime+10001, true);

 

벡터

얘는 배열과는 다르게, 파이썬에서의 리스트와 가장 비슷하다.

동적으로 원소를 추가할 수 있으며(크기가 자동으로 늘어난다),

벡터 중간중간에 원소를 삭제하거나 삽입할 수 있으며,

배열과 마찬가지로 인덱스 접근이 가능하다.

 

사용법은 아래와 같다.

 

// 선언
vector<int> A; 
vector<long long> B(N, 0); // 길이 N짜리인 벡터를 0으로 초기화

// 삽입
A.push_back(1); // 맨 뒤에 1 추가
A.insert(A.begin(), 7); // 맨 앞에 7 추가, O(N)
A.insert(A.begin() + 2, 19); // 인덱스 2 위치에 19 추가, O(N)

// 값 변경
A[4] = -5;

// 삭제
A.pop_back(); // 맨 뒤에 값 pop
A.erase(A.begin() + 3); // 인덱스 3 삭제, O(N)
A.clear(); // 모든 값 삭제, O(N)

// 정보 접근
A.size(); // 데이터 개수
A.front(); // 맨 앞 원소
A.back(); // 맨 뒤 원소
A[3];
A.at(5); // 인덱스 5
A.begin(); // 메모리상 초기 위치
A.end(); // 메모리상 마지막 위치

 

아쉽게도 파이썬처럼 바로 리스트의 합을 구하는 sum 이런 건 없는 것 같다.

 

 

튜플

파이썬에서는 큐 등에 자료를 저장할 때 튜플로 여러가지 값을 한 번에 저장하곤 했다. 하지만 역시나 C++에서는 튜플이라는 자료형을 따로 선언해줘야한다.

 

두 개의 원소를 하나로 묶을 때는 pair라는 자료구로를 지원해준다. 그러나 약간 길어서, 코드 초반에 typedef를 이용해서 Node와 같이 줄여준다.

그리고, 각각의 원소에 접근할 때는 .first, .second를 쓴다.

// 백준 11003번 풀이 예제

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Node;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, L; cin >> N >> L;
    deque<Node> Q;

    for (int i = 0; i < N; i++) {
        int now; cin >> now;
        while (Q.size() && Q.back().first > now) {
            Q.pop_back();
        }
        Q.push_back(Node(now, i));
        if (Q.front().second <= i - L) {
            Q.pop_front();
        }
        cout << Q.front().first << ' ';
    }

}

 

그런데 만약 3개 이상의 원소를 하나로 묶고 싶다면 어떻게 하는가?
tuple이라는 자료구조를 이용해서 Node를 새로 만들어주자.

얘는 접근할때는 이렇게 구조적 바인딩을 이용할 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> Node;

int main() {
    deque<Node> dq;
    
    int val = 7, idx = 3, extra = 42;
    dq.push_back(Node(val, idx, extra));

    auto [v, i, ex] = dq.front();  // 구조적 바인딩
    cout << v << ' ' << i << ' ' << ex << '\n';
}

 

참고로 맨 위에 typedef 문은 아래처럼 쓸 수도 있다.

using Node = tuple<int,int,int>;

 

 

struct문을 이용해서 직접 자료구조를 정의하는 방법도 있다.

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

struct Node {
    int val;    // 구간 최소값
    int idx;    // 배열 인덱스
    int extra;  // 예: 원본 값의 우선순위 등
}; // 그렇다. struct 문 뒤에는 세미콜론이 붙는다?!?

int main() {
    deque<Node> dq;

    dq.push_back({7, 3, 42});       // 중괄호 초기화
    dq.emplace_back(5, 4, 99);      // 더 빠른 in-place 생성

    cout << dq.front().val  << ' '
         << dq.front().idx  << ' '
         << dq.front().extra << '\n';
}

---

[참고] Do it! 알고리즘 코딩 테스트 C++ (김종관)