2. 배열과 리스트, 벡터, 구간 합

※ Do it! 알고리즘 코딩테스트 c++편 교재와 강의로 공부한 내용을 정리했습니다.

---

1-1. 배열

---

배열은 메모리의 연속 공간에 값이 채워져있는 형태의 자료구조이다.

인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.

 

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근할 수  있다.

2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하려면 주변에 있는 값을 이동시켜야한다.

3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.

4. 구조가 간단하므로 코딩 테스트에서 많이 사용한다.

 

1-2. 리스트

---

 

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.

 

 

리스트의 특징

1. 인덱스가 없으므로 값에 접근하려면 Head포인터부터 순서대로 접근해야 한다.(배열보다 값에 접근하는 속도가 느리다.)

2. 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.

3. 크기가 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.

4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

 

1-3. 벡터

---

배열과 같은 특징을 가지면서 배열의 단점을 보완한 동적 배열의 형태이다.

 

 

벡터의 특징

1. 동적으로 원소를 추가할 수 있다. 즉, 크기가 자동으로 늘어난다.

2. 맨 마지막 위치에 데이터를 삽입하거나 삭제할 때는 문제가 없지만 중간 데이터의 삽입과 삭제는 배열과 같다.

3. 인덱스를 이용하여 각 데이터에 직접 접근할 수 있다.

 

벡터는 사용하기 편리하고 쉬우므로 코딩 테스트에서 많이 사용한다. 

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

int main(){
	vector<int> A;//벡터의 선언
    
    A.push_back(10); //마지막에 1 추가
    A.push_back(30);
    A.push_back(5);
    A.push_back(8);
    A.push_back(6);
    
    A.push_back(1);
    A.insert(A.begin(),7); //맨 앞에 7 삽입
    A.insert(A.begin() + 2,10);//index 2의 위치에 10 삽입
    
    A[4] = -5; //값 변경
    
    A.pop_back();//마지막 값 삭제
    A.erase(A.begin() + 3);//index3에 해당하는 값 삭제
    
    cout<< A.size() <<endl;
    cout<< A.front() <<endl;
    cout<< A.back() <<endl;
    cout << A[3] << endl;
    cout << A.at(5) <<< endl;
    
    A.clear();//모든 값 삭제

 

 

2-1. 구간 합

---

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

 

합 배열 S의 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] //A[0] 부터 A[i]까지의 합

 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

 

구간 합을 구하는 공식

S[j] - S[i-1] //i에서 j까지의 구간 합

 

A[2]부터 A[5]까지의 구간 합을 합 배열로 구하는 과정

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]