알고리즘 코테 준비 자료구조(배열, 리스트, 벡터)

배열

연속적인 메모리 공간에 값이 채워져 있는 자료구조 형태

특징

• 인덱스를 통해 값에 빠르게 접근 할 수 있다
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움 (배열의 마지막 인덱스 부근에서 삽입, 삭제를 하는게 아니라면 값을 이동시키는 과정이 너무 많아지기 때문에 속도가 엄청 느려짐)
• 배열의 크기는 선언시 지정하고 한 번 선언하면 크기를 늘리거나 줄일 수 없음

리스트

값과 포인터(주소)를 묶은 노드라는 것을 포인터로 연결한 자료구조 형태

특징

• 인덱스가 없으므로 해당 값에 접근하려면 Head 포인터부터 순서대로 접근해야 되므로 배열에 비해 접근 속도가 느림
• 데이터 삽입, 삭제 속도가 배열보다 빠름
• 크기를 지정할 필요가 없고 크기가 변하기 쉬운 데이터를 다룰 때 적절
• 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함

벡터

배열과 같은 특징을 가지면서 배열의 단점을 보완한 동적배열의 형태로 업그레이드된 자료구조

특징

• 최초에 지정한 배열크기와 상관없이 데이터 추가시 크기가 자동으로 늘어남 (배열에 들어갈 데이터의 개수가 고정된게 아닌 경우에 동적배열인 벡터를 사용하면 좋음)

벡터 사용방법

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 선언
    vector<int> A;

    // 삽입연산
    A.push_back(29); // 마지막에 데이터 추가     
    A.push_back(6);  // 마지막에 데이터 추가     
    A.insert(A.begin(), 22);    // 맨 앞에 데이터 추가 
    A.insert(A.begin() + 2, 9); // 2번째 인덱스 위치에 데이터 추가

    // 값 변경
    A[2] = 77;

    // 삭제 연산
    A.pop_back(); // 마지막 값 삭제
    A.erase(A.begin() + 2); // index[2] 번째에 해당되는 값 삭제 
    A.clear();    // 모든 값 삭제

    // 정보 가져오기
    A.size();  // 데이터 개수
    // 벡터 내부적으로 배열의 용량(배열에 데이터가 추가됨에 따라서 배열의 크기를 동적으로 늘려주는 표시)을 잡음(데이터의 개수, 크기와는 다름) 
    A.capacity(); 
    A.front(); // 처음 값 
    A.back();  // 마지막 값
    A[3];      // 인덱스 3번째에 해당하는 값 가져오기
    A.begin(); // 첫 번째 데이터 위치
    A.end();   // 마지막 데이터 다음 위치    

    return 0;
}