ADT
-
Abstract Data Type (추상자료형)
-
특정 데이터들을 저장 및 조작하는 방식에 대한 "명세서"
-
우리는 추상 자료형을 어떻게든 구현하던간에 상관없다!
-
종류 : 배열 ADT, 링크드리스트 ADT, 스택 ADT, 큐 ADT, ....
-
배열 ADT 는 어떻게 구현하던 상관없다. 다만 배열 ADT (= 배열 기능 명세서) 에서 요구하는 기능을 잘 구현하기만 하면 상관없다!
=> ex) vector ADT 에서 요구하는 기능이 push, delete, erase, eraseFront .... 등이 있을때
이 중에서 eraseFront 라는 기능이 인덱스 0에 있는 것을 지우는 기능이라고 해보자.
이 기능을 우리는 1000줄에 걸쳐서 구현하든, 3줄로 구현해내던간에 ADT 에서 정의한대로만 동작하면 상관X
그래서, ADT 를 설명해서 말하고 싶은게 뭐길래?
자료구조 및 알고리즘 구현에 있어서 100줄, 1000줄, ... 이렇게 비효율적인 구현 방법을 찾아내지 말고, 더 효율적인 방법을 생각해보자!
( "클래스"로 구현하는것은 매우 비추천. )1) 구현에 있어 STL 활용에 구현하는것을 매우 지향하자!
2) 만일 STL 사용 금지시, 편법 구현법을 찾아내보자! (클래스로 100줄짜리 만들어 내는것을 다른 방법으로는 10줄로도 줄여낼 수 있다.)
보충설명
- 최악/평균/최선의 경우
배열
배열의 연산
- 임의의 원소를 확인하고 변경, O(1)
- 원소를 끝에 추가, O(1)
- 마지막 원소 제거, O(1)
- 임의의 위치에 원소를 추가, O(n)
- 임의의 위치에 있는 원소를 제거, O(n)
STL vector
-
배열과 매우 유사. <=> 쓰기 편한 배열 버전느낌?
-
Doubling Strategy (더블링 전략) 으로 구현
-
인덱싱(Indexing) 가능 => 배열과 마찬가지로 원소가 메모리에 연속적으로 저장되어 있어서, O(1) 에 인덱스를 가지고 각 원소를 접근 가능
-
수용 공간(capacity)가 꽉차면 이전보다 2배로 크기를 늘리고(2배로 늘린 새로운 공간을 할당), 그곳에 모든 기존의 벡터 요소를 카피
코딩테스트에서 자주 쓰이는 메소드
push_back()
erase()
begin()
rbegin()
end()
rend()
pop_back()
vec1[idx]
front()
back()
size()
예제
vector<int> v1 = {1,2,3,4,5,6};
v1.push_back(7); // 맨뒤에 추가
v1.push_back(8);
for(int i = 0; i < v1.size(); i++) // for문 반복가능. size() 메소드로 반복범위 설정
cout << v1[i] << ' ';
v1.erase(v1.begin() + 2); // 인덱스2 에 있는 원소제거
v1.pop_back() // 맨뒤 원소제거sort()
- 배열 또는 vector 를 오름차순으로 정렬
vector<int> v1 = {1,3,2,4,6,5};
sort(v1.begin(), v1.end()); // 1,2,3,4,5,6
for(int i = 0; i < v1.size(); i++)
cout << v1[i] << ' ';
sort(v1.rbegin(), b1.rend());
for(int i = 0; i < v1.size(); i++) // 6,5,4,3,2,1
cout << v1[i] << ' ';실습문제
BOJ 10808번 알파벳개수
BOJ 2577번 숫자의 개수
