20220621 TIL

[C++ STL] vector와 List의 차이점

알고리즘 스터디하다가 두 컨테이너의 메서드간 연산 속도 차이가 발생하는 걸 알게되어서 찾아봄

Vector

• (물리적으로) 연속적인 메모리

• 미리 공간을 할당해놓음

• 각 요소는 해당 타입만큼의 공간을 요구함

• 요소를 추가/제거할 때마다 전체 메모리를 다시 할당해야할 수도 있음

  • 제일 끝에 요소를 추가/제거하는데에는 상수시간소요
  • 이 외에는 O(n)

• 해당 요소에 임의로 접근이 가능

• 벡터에 요소를 추가/제거하면 반복자(iterator)가 무효화됨

• 개별 원소 접근 가능

• 마지막에 요소를 추가/제거하면 빠름

• 랜덤하게 원소 순회 가능

• 인덱싱 비용이 작음

Vector의 장점

• 개별 원소 접근 가능
• 마지막에 요소를 추가/제거하면 빠름
• 랜덤하게 원소 순회 가능
• 인덱싱 비용이 작음

Vector의 단점

• 처음 및 중간에 요소를 삽입/삭제하는 비용이 큼
• 동적이라 확장/축소가 용이하나, 비용이 큼

List

• 비연속적인 메모리 (논리적으로 연속적임)
• 미리 공간을 할당해놓지 않음
  • 메모리 오버헤드는 상수 < meaning?
• double linked list로 구현되어있음
  • 이전과 이후를 가리키는 포인터가 필요하므로, 각 요소의 해당 타입의 크기 이외에도 두 포인터를 위한 추가 공간이 필요
  • 요소 추가/제거할때마다 전체 메모리를 다시 할당해야할 필요 X
  • 요소에 랜덤하게 접근이 불가능 > 인덱싱 비용이 비쌈
• 리스트에서 요소를 추가/제거해도 반복자는 유효함

List의 장점

• 어느 위치에서든 삽입/삭제 비용이 작음
• 원소들의 컨테이너 이동이 빠름

List의 단점

• 원소의 특정 인덱스로 직접 접근이 불가능
  • 접근하려면 처음이나 끝에서 선형탐색해야함
• 컨테이너 순회가 forward/reverse 만 가능해서 느림
• 이전/이후 포인터가 추가적으로 필요하므로, 메모리 오버헤드가 발생

[바킹독의 실전 알고리즘]

OT : 코딩 테스트에 대해서

• 주어진 Test Case만 확인하지 말고, 직접 다양한 Test Case를 생각해서 확인해야함
• 코딩 테스트를 잘하려면 강의들어서 자료구조, 알고리즘, 테크닉 등의 배경 지식을 쌓고, 다양한 문제를 직접 풀어보면서 문제 해결 능력을 기르고, 내가 짠 코드와 다른 사람들의 코드를 비교해보면서 좋은 점을 흡수해서 구현력을 키워야함
• VLA(Variable Length Array) : 변수로 배열의 크기를 선언 하는 것
  • gcc 컴파일러는 가능한데, msvc 컴파일러는 안됨
• #include <bits/stdc++.h> : 자주 쓰는 헤더들을 모두 포함 시키고 있는 헤더

기초 코드 작성 요령

• 시간/공간 복잡도
  • 주어진 문제를 보고 풀이를 떠올린 후 무턱대고 바로 짜지 말고, 내 알고리즘의 시간복잡도와 문제 입력 범위를 확인하고, 주어진 시간 내에 답을 낼 수 있는 알고리즘인지 확인할 것
  • 코딩테스트에서는 공간 복잡도 크게 신경 안써도 ㄱㅊ (512MB == 1.2억개의 int)
• 자료형
  • 기억해야할 실수 자료형의 성질 !
    • 실수의 연산/저장 과정에서 반드시 오차가 발생할 수 밖에 없음
      ex : 0.1 + 0.1 + 0.1 != 0.3
    • WHY? 유효숫자가 들어가는 fraction field가 유한하기 때문에, (2진수기준) 무한 소수를 저장하려면 잘라야 해서 오차가 발생함
      float : 상대 오차가 $10^{-6}$ 까지 안전
      double : 상대 오차가 $10^{-15}$ 까지 안전
      --> 참 값이 1일 때 $1$-$10^{-15}$ ~$1$+$10^{-15}$이 보장된다든 것
      double 타입이 저장할 수 있는 유효숫자가 더 많기 때문에 되도록 double 쓰셈 !
• STL과 함수 인자
  • STL 컨테이너는 기본 배열과 달리 그냥 함수 인자로 넘기면 "복사"되어 넘어간다는 점을 주의 !
  • Example

    bool cmp1(vector<int> v1, vector<int> v2, int i) {
        return v1[i] > v2[i];
    }
    bool cmp2(vector<int> &v1, vector<int> &v2, int i) {
       return v1[i] > v2[i];
    }

  • cmp1은 복사 시간이때문에 O(N)이 걸리고, cmp2는 O(1)
• 표준 입출력
  • 공백이 포함된 문자열을 입력 받을 때 > getline 사용
  • cin/cout 사용할 때

    ios::sync_with_stdio(false); // 1
    cout.tie(nullptr);			// 2
    cin.tie(nullptr);			// 3

    1) scanf/printf 에서 쓰는 C stream과 cin/cout에서 쓴 C++ stream은 분리되어있음. 그래서 기본적으로 두 stream을 동기화 시켜줘야 함께써도 ㄱㅊ은데, 코테 때는 굳이..? 해당 동기화에 시간을 쓸 필요가 없기 때문에 동기화를 해제시켜주는 명령어
    2,3) 입출력은 기본적으로 버퍼에 어느정도 모았다가 보내줌. 때문에 순서가 꼬이지 않게 기본적으로 cin 수행전, cout 버퍼를 비워주는 작업이 있다. 그런데 코딩테스트 채점 시스템은 "출력"만 확인하기 때문에, 콘솔창에서 입출력 순서가 꼬여도 채점에 영향 X.
  • endl : 개행문자를 출력하고 출력 버퍼를 비우라는 뜻 > 사용하지 마셈
• 코드 작성 팁 : 코딩 테스트와 개발은 다르다 !
  • 코딩테스틑 제한시간 내에 빠르게 푸는 것이 중요하니, 이쁘게 짜는 것보단 빠르게 푸는 것에 집중할 것

배열 : 메모리상에 원소를 연속적으로 배치한 구조

• 배열의 성질
  • O(1)에 임의의 원소 확인 가능
  • 추가적으로 소모되는 메모리의 양(=overhead) 거의 없음
  • cache hit rate가 높음
  • 메모리 내 연속된 구간을 잡아야해서 할당에 제약이 있을 수 있음
• Vector
  • push_back(),pop_back() : O(1)
  • push_front(), pop_front() : O(n)
  • =을 사용하면 Deep Copy
  • 기본적으로 size() 메서드는 unsigned int 를 반환
    • range-based loop로 순회를 추천 !

[백준 알고리즘] LCS 알고리즘

Longest Common Substring

if (i==0 || j==0)
    LCS[i][j] = 0;
else if (A[i] == B[j])
   LCS[i][j] = LCS[i-1][j-1] + 1;
else
   LCS[i][j] = 0

• 메모이 제이션을 이용한 풀이
• 공통 문자열은 연속되어야하기 때문에 가능한 알고리즘

Longest Common Subsequence

if (i==0 || j==0)
    LCS[i][j] = 0;
else if (A[i] == B[j])
   LCS[i][j] = LCS[i-1][j-1] + 1;
else
   LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

• 부분 수열은 연속된 값이 아닐 수 있음
  • 현재 이전의 최대 공통 부분 수열은 유지
  • 현재 이전의 과정이 바로 제일 마지막 줄 !

---

Reference

https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl
https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://www.acmicpc.net/problem/9251