- STL vector 와 유사한 점은 많지만 정확히 일치는 x
vector
-
배열의 확장된 개념 (배열보다 편한 기능들을 제공)
-
배열을 활용해서 구현하는 것이 가장 적합 (링크드 리스트로도 구현은 가능)
-
벡터와 배열의 관계 : 배열 + 여러 함수 = 클래스화 ⇒ 벡터
- 공통점 : index를 통해 데이터에 접근 가능
- 차이점 : insert 함수에서 full 일때, 벡터는 더 큰 배열을 할당받아 크기를 키울 수 있음
-
주소가 아닌 index로 배열의 element를 access 한다.
-
탐색, 삽입, 삭제 모두 index 로 한다.
-
incorrect index 호출시 exception 발생 (ex) 인덱스 -3 의 element 조회)
메인 기능
at(integer i) : 인덱스 i에 있는 element 를 리턴 => return V[i]
set(integer i, object o) : 인덱스 i의 element를 새로운 값 o로 대체
- update 연산. 탐색,삽입,삭제 다음으로 자주쓰이는 연산
insert(integer i, object o) : 인덱스 i에 o를 삽입
- 삽입시 element 들이 한칸씩 뒤로 밀려서 인덱스가 하나씩 증가함
erase(integer i) : 인덱스 i에 있는 element 제거.
- 삭제시 (i+1) 부터 있는 element들을 한칸씩 이동해야함.
부가 기능
- size()
- empty()
벡터의 활용범위
- 배열 대신 사용=> 특히 배열의 사이즈를 유연하게 사용하고 싶을때
- 그래프 이론에서 "인접 리스트"의 구현을 벡터를 이용해서 편하게 구현 가능
성능 분석 - 시간 복잡도
( 크기가 N인 배열 A을 사용하는 것을 가정. N과 n은 다르다. n은 배열안에 담겨있는 현재 element의 개수, N은 배열의 크기 )
-
사용 공간 : O(N)
- 배열 A의 사이즈만큼 공간필요
-
size, empty, at, set : O(1)
-
insert, erase : O(n) (최악의 경우)
-
환형배열로 구현한다면, insert(0, x)와 erase(0) 처럼 0번 인덱스에 대한 삽입, 삭제만 필요한 경우 O(1) 에 수행가능
- 선형 배열의 경우 insert하면 한칸씩 뒤로 밀지만, 환형 배열이면 그냥 맨 앞 원소가 있는 인덱스(front)의 바로 앞 칸(front-1)에다 원소를 할당하는 것이다.
- 이때 우리가 생각하는 인덱스와 배열의 실제 인덱스가 달라질 수 있다는 점 주의!
=> 맨 앞에 insert 하는경우 front 인덱스가 0이 아닐 수 있다. front가 1일 수도 있고, 5일수도 있고 하는 것이다. - cf. 임의의 인덱스에 대해선 환형배열에서도 여전히 O(n) 걸림
상세 설명
- at(i) : O(1)
- return A[i]
- set(i,o) : O(1)
- A[i] = o
- insert(i, o) : O(n)
- 인덱스 i에 삽입시 A[i] ~ A[n-1] element들이 모두 뒤로 한칸씩 이동
(n-i개의 element가 이동) - 최악의 경우(i=0) : O(n)
- 인덱스 i에 삽입시 A[i] ~ A[n-1] element들이 모두 뒤로 한칸씩 이동
- erase(i) : O(n)
- 인덱스 i의 element 삭제시 A[i+1] ~ A[n-1] element 들이 모두 앞으로 한칸씩 이동 (n-i-1 개의 element가 이동)
- 최악의 경우 (i=0) : O(n)
Growable Array-based Vector
배열이 가득찼을 때 insert 하는 경우 : O(1) - 더블링으로 구현시에만
그냥 평소에 insert 하는 경우 : O(n)
- 배열 자체의 고정된 크기는 변할 수 없다.
따라서 더 큰 배열을 새롭게 할당받아 저장소로 사용한다
⇒ insert 연산 수행시 마지막 원소의 인덱스가
"벡터에 내부적으로 사용하고 있던 배열의 크기 -1" 보다 크다면, 즉 insert 하려는데 배열이 꽉차있으면 배열을 새로 할당하게 된다.
cf. 당연하게도 새로 할당받았으므로 할당받은 배열의 주소는 기존 배열 주소와 다름!
-
Growable Array-based Vector 에서 아래와 같은 insert 연산은
배열이 꽉 찼을시에 insert시 O(n), 아직 꽉 안찼을 때 insert시엔 O(1) 이 걸린다. ( 꽉 찼을때는 배열을 카피 해야하므로 O(n) ). 그러나 더블링 strategy 로 구현하면 배열이 꽉찼을때 insert연산 O(1)이 걸리게 된다. -
아래 수도코드는 배열의 맨 끝에다 삽입하는 insert 함수임을 가정한다.
// 배열 끝에다 삽입
// 기존 배열 S를 새로운 배열 A에 할당
// S:배열이름, A:새로 할당한 배열, S.length : 배열 원소의 개수(배열의 크기가 아니다!) <->(S.size: 배열의 크기)
// t : 배열의 마지막 인덱스 번호, N : 배열의
Algorithm insert(o) // insert(N,o) 구현할 수도 있지만, 배열 끝에다 삽입한다는 것을 알고 있으므로, 또 인덱스 N에다 삽입하는 것인지 모를수도 있으므로 insert(o) 로 구현함
if t = S.length - 1 then // full (배열이 꽉찬 경우). => 여담이지만, n = S.size() 으로 해도될듯?
A <- new array of // 새로운 배열 A 생성
size <- ... // 사이즈는 구현하기 나름임. 당연한거지만 기존 배열 사이즈인 n보다는 커야할 것임 (* 구현 방법은 Incremental / Doubling 구현법 2가지이다 )
for i <- 0 to n-1 do // 최악의 경우 => 이 for문 때문에 insert 연산이 O(n) 이 걸린다. (즉, 기존 배열을 카피해야 해서 O(n) 이 걸림)
A[i] <- S[i] // 새로운 배열 A에 기존 배열 S의 값들을 할당
S <- A // 기존 S의 주소값을 A의 주소값으로 바꿔버리면, A가 새로운 S가 된다.
// 아래 2문장은 다음 2문장으로 구현해도됨. S[n] <- 0 n <- n + 1
n <- n + 1
S[n-1] = o새로운 배열 크기 할당 받는법
- Incremental strategy : 상수 c만큼 사이즈를 늘리는 방법
- ex) 사이즈 : 10 -> 20 -> 30 -> 40 -> ..
- Doubling strategy : 사이즈를 2배 늘리는 방법
- ex) 사이즈 : 10 -> 20 -> 40 -> 80 -> ...
- Incremental strategy vs Doubling strategy
Incremental strategy : O(n)의 수행시간이 걸림
Doubling strategy : Amortized 분석 결과 O(1)의 수행시간이 걸림
=> 더블링 방법이 더 효율적이다. ( STL vector 가 사용하는 방법 )
상식적으로 생각하면 입력크기가 많아질수록 더블링을 할 필요가 점점 없어지므로
안정적으로 작동이 가능해서, 더블링이 잘 안일어난다는 것!
→ 지금 우리 레벨로 이해할 수 없으므로 그냥 그렇구나 생각하기 ^^
- 더블링의 장단점
- 장점 : 배열 카피를 할일이 줄어든다.
- 다넘 : 공간낭비 될수도 있음
erase 하는 경우 벡터의 사이즈 조절
- 사이즈가 1/4 만큼 줄어들면 사이즈를 줄임
ex) 사이즈가 40인 꽉찬 배열에 insert하면 80이 된다.
여기서 erase를 한다고 바로 사이즈가 40으로 돌아오지 않는다.
사이즈 값인 80의 1/4 인 20이 되면 그때 사이즈를 절반인 40으로 줄인다.
정리
-
공간: O(N)
- N: 벡터의 내부안에 들어있는 배열의 크기
-
insert
- 배열: O(n)
- 환형배열 : O(n) / O(1) (=>맨앞에 insert하는 경우)
- Growable-Array : O(1) (=> 아직 다 안찼을때) / O(n) (=> 꽉찼을떄의 insert. incremental strategy로 구현한 경우),
O(1) (=> 꽉찼을때의 insert. Doubling strategy로 구현한경우 )
-
erase
- 배열 : O(n)
- 환형배열 : O(n) / O(1) (=> 맨앞의 원소 erase)
-
at
- 배열 : O(1)
- 환형배열 : O(1)
-
set
- 배열: O(1)
- 환형배열: O(1)
-
empty
- 배열: O(1)
- 환형배열: O(1)
-
size
- 배열: O(1)
- 환형배열: O(1)
