자료구조 정리 C++

내장된 라이브러리가 존재

  선형 자료 구조

    # 정적 배열 (array)

      - 인덱스를 통해 자료에 접근

    

    # 동적 배열 (std::vector)

      - 정적 배열과 같으나, 배열의 크기를 런타임에 바꿀 수 있다.

      정렬 - algorithm 내의 sort, partial_sort, stable_sort 를 사용 => 정렬을 하기위해 비교 함수를 명시해야 한다. => 비교 함수 사용법 알아둘 필요가 있다.

      검색 - 정렬후 이진탐색 (lower_bound, upper_bound, binary_search)

    # 연결 리스트 (std::list)

      - 임의의 위치에 새로운 문자를 삽입 할 때 효율적 (그 외에는 배열을 사용하도록 하자)

    # 스택 (std::stack)

      - 후입선출 (LIFO)

      - push, pop

    # 큐 (std::queue)

      - BFS(너비 우산 팀섹)와 같은 알고리즘에 사용된다.

      - 선입선출 (FIFO)

    # 데크 (std::deque)

      - 배열과 큐와 비슷하지만 앞과 뒤에서 빠르게 삽입 삭제가 가능하다.

  비선형 자료 구조

    # 균형 잡힌 이진 검색 트리 (std::map, std::set)

      - AVL 트리, 레드-블랙 트리로 균형 잡힌 이진 트리를 구현해 놓은 라이브러리 (보통 레드-블랙 트리로 구현)

      - 삽입, 검색, 삭제 작업이 O(logN)

      - map 은 키->데이터 페어를, set 은 키만을 저장한다

    

    # 힙 (std::priority_queue : 최대힙 기본)

      - 완전 이진 트리 (x를 루트로 하는 서브트리의 각각은 x보다 작아야 한다 : 우선순위 큐)

      - 최대 값 추출, 새로운 원소 추가를 O(logN) 에 할 수 있고, 최대 값을 알아내는 것은 O(1) 시간에 할 수 있다.

    # 해시 테이블 (std::unordered_map)

      - 대회에선 map을 사용해도 충분하다!

자체적인 라이브러리가 필요한 자료 구조

  # 그래프

    - 정점의 집합과 간선의 집합으로 구성된다.

      A) 인접 행렬 (2차원 배열 형태 / int adjMat[V][V])

        - 정점의 개수 V에 대해 O(V^2)의 공간 복잡도를 가진다.

        - 작은 크기의 밀집 그래프(dense graph)에 속한 두 정점 사이의 연결 관계 확인 (O(1))에 확인가능) 시 유리

        - 큰 크기의 희소 그래프(sparse graph)는 비효율적

        - V가 1000보다 크면 보통 사용하기 힘들다.

        - 정점 v와 연결된 이웃을 나열할 때 O(V)만큼의 시간이 든다(실제로 이웃이 몇 안되도 무조건 최악의 알고리즘이 된다).

      

      B) 인접 리스트 (vector<vii> adjList / using ii = pair<int,int>; using vii = vector<ii>)

        - 각 정점 u의 이웃 목록 + 간선 정보(주로 가중치) 를 저장

        - 공간 복잡도는 O(V+E) 이고, 보통 E는 O(V^2) 수보다 훨씬 작다.

        - 정점 v의 이웃 수가 k 일대, 이웃 나열 작업 시간 복잡도는 O(k)가 된다.

      C) 간선 리스트 (vector<pair<int, ii> > edgeList)

        - 간선만큼 저장하기 때문에 공간 복잡도는 O(E) 이다.

        - 간선의 가중치 목록을 정렬할때 괜찮게 사용 (크루스칼 알고리즘)

    - 묵시적 그래프

  # 유니온-파인드 상호 배타적 집합 (Union-Find Disjoint Set, UFDS)

    - 상호 배타적인 집합들의 모임

        - 어떤 원소가 어느 집합에 속해 있는지 판별 (거의 O(1))

        - 두 집합을 더 큰 하나의 집합으로 합치는 작업 (거의 O(1)))

       

        - 각 원소마다 부모 원소의 번호 / 각 트리의 높이를 저장 (vi p, vi rank)

          1. 모든 rank 를 0으로 / 모든 p 를 자기 자신으로 초기화 한다.

          2. union(i,j) 작업은 i와 j가 동일한 대표 원소를 갖도록 만든다. (랭크가 더 높은 집합의 대표 원소를 -> 랭크가 더 낮은 집합의 새 부모로 삼으면 "랭크 최소화" 가능)

          3. 경로 압축을 통해 모든 원소가 "부모 노드로 루트를 직접 가리키도록" 만든다. (find(i) 는 단순히 p[i]를 참조하는 것과 비슷하므로 매우 빠를것!)

    C++ 구현 코드

    (

      #include <vector>

      #include <set>

      #include <algorithm>

      using vi = std::vector<int>;

      using si = std::set<int>;

      class UnionFind {

          private: vi p, rank, size;

          public: 

                UnionFind(int N) { 

                    rank.assign(N,0); p.assign(N,0); for (int i=0;i<N;i++) p[i] = i; size.assign(N,1);

                }

                int findSet(int i) {

                    return (p[i] == i) ? i : (p[i] = findSet(p[i]));

                }

                bool isSameSet(int i, int j) {

                    return findSet(i) == findSet(j);

                }

                void unionSet(int i, int j) {

                    if (!isSameSet(i, j)) { // 다른 집합일때만

                        int x = findSet(i), y = findSet(j);

                        if (rank[x] > rank[y]) swap(x,y); // 랭크가 더 높은 집합의 대표 원소를 랭크가 더 낮은 집합의 새 부모로 결정한다.

                        if (rank[x] == rank[y]) rank[y]++; // 랭크가 같으면 랭크를 하나 증가시킨다.

                        p[x] = y; size[y] = size[x] + size[y];

                    }

                }

                // 여기부터는 내가 직접 만들어보는 유용한 함수들

                int numDisjointSets() { // 현재 구조에 존재하는 상호 배타적 집합의 개수를 반환 O(NlogN)

                    si s(p.begin(), p.end()); return s.size();

                }

                int sizeOfSet(int i) { // 현재 원소 i가 속해 있는 집합의 크기를 반환 O(1)

                    return size[findSet(i)];

                }

      };

    )

  # 구간 트리

   - 동적인 구간 질의에 효율적으로 답하기 위한 자료 구조 (배열 [0..n] 중에 [i..j] 중에 가장 ~한 것은?)

   - 구간 트리를 만드는데 O(n)

   - 구간 트리를 만들면 구간 질의엔 O(nlogn)

   @ 구간이 정적이라면 O(1)에 해결하는 DP 풀이가 있다.

   - 원소 갱신에 O(logn) -> 이것 때문에 동적인 구간 질의에서 사용!

    부분합 구간 트리 구현해본거

      class ST {

        private:

          vi A;

          vll st;

          int n;

          int left(int p) { return p << 1; }

          int right(int p) { return (p << 1) + 1; }

          void build(int p, int L, int R) { // O(n)

            if (L == R)

              st[p] = A[L];

            else {

              build(left(p), L, (L + R) / 2);

              build(right(p), (L + R) / 2 + 1, R);

              st[p] = st[left(p)] + st[right(p)];

            }

          }

          long long rsq(int p, int L, int R, int i, int j) { // O(logn)

            if (i > R || j < L) return 0; // 질의 구간의 바깥 쪽

            if (L >= i && R <= j) return st[p]; // 질의 구간의 안쪽

            long long s1 = rsq(left(p), L, (L + R) / 2, i, j);

            long long s2 = rsq(right(p), (L + R) / 2 + 1, R, i, j);

            return s1 + s2;

          }

          void update(int p, int L, int R, int i, long long diff) {

            if (i < L || i > R) return;

            st[p] += diff;

            if (L != R) {

              update(left(p), L, (L + R) / 2, i, diff);

              update(right(p), (L + R) / 2 + 1,R, i, diff);

            }

          }

        public:

          ST(const vi &_A) {

            A = _A; n = (int)A.size();

            st.assign(4 * n, 0);

            build(1, 0, n - 1);

          }

          long long rsq(int i, int j) { return rsq(1, 0, n - 1, i, j); }

          void update(int i, long long diff) {

            update(1, 0, n - 1, i, diff);

          }

        };

  # 펜윅 트리 (이진 인덱스 트리)

    - [1..n] 범위의 정수 키 m 개가 주어졌을 때

    - 질의 및 갱신 O(n) 공간 & O(nlogn) 시간에 처리

    @ 정적인 구간에선 O(n)의 사전작업 후 O(1)에 질의 가능

    using vi = std::vector<int>;

    class FenwickTree {

      private: vi ft;

      public: FenwickTree(int n) { ft.assign(n+1, 0); } // [1..n] 범위를 사용하고 0은 무시

        int rsq(int b) {

          int sum = 0; for (; b; b -= LSOne(b)) sum += ft[b]; // LSOne 은 제일 오른쪽 켜진 비트를 반환한다. (ex 110 (6) 은 010 (2) 를 반환)

          return sum;

        }

        int rsq(int a, int b) {

          return rsq(b) - (a == 1 ? 0 : rsq(a-1));

        }

        void adjust(int k, int v) { // k번째 원소의 값을 v만큼 조정한다 (v가 양수이면 증가, v가 음수이면 감소)

          for(; k < (int)ft.size(); k += LSOne(k)) ft[k] += v;

        }

    };