벡터 Vectors

[Vector] vs [List] vs [Sequence]

• Vector (또는 Array List로 불림)
  • 정수 인덱스 [0, n-1]를 사용해 요소에 접근합니다.
  • 요소 e의 인덱스: e 앞에 있는 요소의 수입니다.
• List
  • 인덱스 대신 노드를 사용하여 접근하고 업데이트합니다.
  • 구체적인 연결 리스트 데이터 구조를 추상화합니다.
• Sequence
  • 벡터와 리스트 ADT를 일반화합니다.
  • 요소에 접근할 때 인덱스(indices)와 위치(positions)를 모두 사용합니다.

Vector

ADT

Vector ADT (Array List ADT)는 객체의 연속적인 시퀀스를 저장하는 확장된 배열 개념입니다.

요소에는 해당 요소의 인덱스(그 요소 앞에 있는 요소의 수)를 지정하여 접근, 삽입 또는 제거할 수 있습니다.

잘못된 인덱스(예: 음수 인덱스)가 주어지면 예외가 발생합니다.

주요 메소드:

• at(integer i): 인덱스 i에 있는 요소를 반환하되, 제거하지 않습니다.
• set(integer i, object o): 인덱스 i에 있는 요소를 새 객체 o로 대체합니다.
• insert(integer i, object o): 새 요소 o를 인덱스 i에 삽입합니다.
• erase(integer i): 인덱스 i에 있는 요소를 제거합니다.

추가 메소드:

• size(): 벡터에 저장된 요소의 수를 반환합니다.
• empty(): 벡터가 비어 있는지 여부를 반환합니다.

Applications of Vector

직접적인 응용

• 정렬된 객체 모음 (기초 데이터베이스): 벡터는 데이터를 순서대로 저장할 수 있으므로, 정렬된 데이터의 컬렉션을 관리하기 위한 기초적인 데이터베이스로 사용될 수 있습니다.

간접적인 응용

• 알고리즘의 보조 데이터 구조: 벡터는 다양한 알고리즘에서 중요한 보조 데이터 구조로 활용됩니다. 예를 들어, 동적 프로그래밍, 정렬, 검색 알고리즘 등에서 중간 결과를 저장하는 데 사용될 수 있습니다.
• 다른 데이터 구조의 구성 요소: 벡터는 다른 복잡한 데이터 구조의 일부로 통합되어 사용될 수 있습니다. 예를 들어, 해시 테이블의 버킷 배열이나 그래프의 인접 리스트 등이 이에 해당합니다.

Array-based Implementation

• 크기가 N인 배열 A를 사용합니다.
• 변수 n은 배열 리스트의 크기(저장된 요소의 수)를 추적합니다.
• at(i) 연산은 O(1) 시간 내에 A[i]를 반환하여 구현됩니다.
• set(i, o) 연산은 O(1) 시간 내에 A[i] = o를 수행하여 구현됩니다.

삽입 Insertion

• insert(i, o) 연산에서 새 요소를 추가하기 위해, 기존의 요소들을 뒤로 이동시켜야 합니다.
• 즉, 새 요소를 삽입할 위치 i부터 배열 끝까지의 요소들인 A[i]부터 A[n−1]까지를 한 칸씩 뒤로 이동시켜야 합니다.
• 최악의 경우 (i = 0일 때), 즉 새 요소를 배열의 맨 앞에 삽입할 때는 모든 요소를 한 칸씩 이동시켜야 하므로, 이 작업은 O(n) 시간이 소요됩니다.

요소 삭제 Element Removal

• erase(i) 연산에서는 특정 인덱스 i에서 요소를 제거하고, 제거된 요소가 남긴 빈 자리를 메우기 위해 그 뒤의 요소들을 앞으로 이동시켜야 합니다.
• 이는 A[i+1]부터 A[n−1]까지의 요소들을 한 칸씩 앞으로 이동시키는 것을 의미합니다.
• 최악의 경우 (i = 0일 때), 즉 배열의 맨 앞 요소를 제거할 때는 모든 요소를 한 칸씩 앞으로 이동시켜야 하므로, 이 작업은 O(n) 시간이 소요됩니다.

Performance

■ 공간 사용

• 데이터 구조가 사용하는 공간은 O(n)입니다. 여기서 𝑛n은 배열에 저장된 요소의 수입니다.

■ 연산 성능

• size, empty, at 및 set 연산은 O(1) 시간에 실행됩니다. 이는 이들 연산이 배열의 인덱스 접근을 바로 수행하기 때문입니다.
• insert 및 erase 연산은 최악의 경우 O(n) 시간이 소요됩니다. 이는 요소를 삽입하거나 제거할 때 배열의 요소들을 이동해야 하기 때문입니다.

■ 원형 배열 사용 시의 성능 향상

• 배열을 원형 방식으로 사용하면, insert(0, x) 및 erase(0, x) 연산이 O(1) 시간에 실행될 수 있습니다.
• 이는 원형 배열에서는 배열의 끝과 시작이 연결되어 있어 특정 위치(예를 들어, 시작 또는 끝)에 대한 요소의 추가 및 제거가 인덱스 조정만으로 가능하기 때문입니다.

■ 배열이 가득 찬 경우의 처리

• 삽입 연산 중 배열이 가득 찼을 때, 예외를 던지는 대신, 더 큰 새 배열로 교체할 수 있습니다.
• 이 과정에서 기존 배열의 모든 요소를 새 배열로 복사하고, 새로운 요소를 추가합니다.
• 이 방법은 동적 배열 구현(예: C++의 std::vector)에서 자주 사용되며, 일반적으로 배열 크기를 두 배로 확장하는 것이 일반적입니다.

Growable Array-based Array List

• insert(o) 연산에서 (인덱스 없이) 항상 배열의 끝에 요소를 삽입합니다.
• 배열이 가득 찼을 때, 더 큰 새 배열로 교체합니다.
• 새 배열은 얼마나 커야 할까요?
  • 증분 전략 (Incremental strategy): 크기를 상수 c만큼 증가시킵니다.
  • 배가 전략 (Doubling strategy): 크기를 두 배로 늘립니다.

Comparison of the Strategies

분할 상환 분석을 사용하여 증분 전략과 배가 전략을 비교해 보겠습니다.

이 분석은 n개의 insert(o) 연산을 수행하는 데 필요한 총 시간 T(n)을 분석하여 이루어집니다.

초기 상태

• 배열의 초기 크기는 1이고, 배열은 비어 있습니다.

분할 상환 시간 amortized time

• 분할 상환 시간은 연산 시리즈에 걸친 insert 연산의 평균 시간, 즉 T(n)/n을 의미합니다.

Incremental Strategy Analysis

배열을 k=n/c 번 교체합니다.

n개의 insert 연산 시리즈에 대한 총 시간 T(n)은 다음과 같이 비례합니다:

여기서 c는 상수이므로, T(n)은 O(n+k2), 즉 O(n2)입니다.

insert 연산의 분할 상환 시간은 O(n)입니다.

Doubling Strategy Analysis

배열을 𝑘=log⁡2𝑛k=log2​n 번 교체합니다.

n개의 insert 연산 시리즈에 대한 총 시간 T(n)은 다음과 같이 비례합니다:

따라서 T(n)은 O(n)입니다.

insert 연산의 분할 상환 시간은 O(1)입니다.

Vectors in C++ STL