본문 바로가기

Programming/C++ STL

 (7)
[C++ STL] list(연결리스트) 연결리스트(list) 연결리스트는 배열의 각 요소가 값만 갖고있는 것이 아니라 다음 요소를 가리키는 포인터를 함께 가지고 있다. 이는 배열에서 중간에 추가 혹은 삭제할 때 뒤의 원소를 쭉 밀거나 뒤의 원소를 쭉 당겨와야하는 단점을 보완한 것이다. 배열의 요소들을 직접 미는 것이 아닌 포인터값만 변경해주는 것으로 임의의 위치에 추가/삭제 연산을 할 수 있다. C++에서는 list라는 자료형으로 연결리스트가 구현되어 있다. 리스트 각 요소는 포인터로 연결되어있기 때문에 메모리 상에 연속적으로 존재하지 않아도 된다. 그래서 각 요소에 접근할 때도 포인터를 이용해서 순서대로 접근해야한다. 이를 아래의 예제를 통해 소개한다. 리스트 선언 양 끝의 요소 삭제(삽입) 임의의 위치에 새로운 요소 추가(삭제) 리스트의 ..
[C++ STL] queue(큐) 큐(queue) 큐 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있는 선입선출(FIFO, First In First Out)의 속성을 지닌다. (동적배열(vector)의 경우 맨 끝에서 자료를 넣는 것이 유사하지만 맨 앞에서 자료를 꺼내진 않음) 이는 일상생활과 아주 밀접한 자료구조이다. 예를들면 놀이공원이나 음식점에서 선 줄이나 할 일의 목록을 큐를 이용해 표현할 수 있다. 간단한 예제를 통해 기본적인 큐의 연산을 살펴보자. 큐 선언 요소 삽입/삭제 큐에서 꺼낸(삭제한) 요소 저장 큐의 각 요소 출력 #include #include using namespace std; int main() { //큐 선언 queue que; //큐에 요소 추가하기 for (int i = 0; i < 5; i..
[C++ STL] stack(스택) 스택(stack) 스택은 한쪽 끝에서만 자료를 넣고 빼는 후입선출(LIFO, Last In Last Out)의 속성을 지닌다. 이런 속성으로 스택은 전산학에서 많이 쓰인다. 함수의 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야 한다. 이때 컴퓨터 내부적으로 스택을 이용해 함수들의 문맥을 관리한다. 스택 선언 요소 삽입/삭제 스택에서 꺼낸(삭제한) 요소 저장 스택의 각 요소 출력 #include #include using namespace std; int main() { //스택선언 stack stk; //스택에 요소 삽입 for (int i = 0; i < 5; i++) { stk.push(i); } //스택에서 요소 제거 int out = stk.top(); stk.pop..
[C++ STL] vector(동적배열) 동적배열(vector) 동적배열은 배열의 크기를 미리 정하지 않고 자료의 개수가 변함에 따라 배열의 크기가 변경되는 배열이다. 이는 C++에서 배열(정적배열)을 선언 시 배열의 크기를 정해야하는 단점을 보완한 것이다. C++의 STL에서는 vector라는 자료형으로 동적배열이 구현되어 있다. vector가 동적으로 배열을 할당하는 과정을 이해해보자. vector는 맨 뒤쪽에서 삽입과 삭제가 이루어진다. 이렇게 들어간 요소들이 배열의 크기인 vec.size()를 형성한다. 또한 vector자료형은 배열 요소들의 갯수가 증가함에 따라 공간을 점점 늘려가며 할당하므로 배열의 크기보다 더 큰 여유공간을 할당해둔다. 이를 vec.capacity()라고 한다. 벡터가 너무 커져 연속된 메모리를 할당할 수 없을 경우..
[C++ STL] unique함수와 erase함수를 통한 문자열 중복제거 중복문자를 제거하기 위해 unique와 erase 함수를 사용할 수 있다. 1. 필요한 라이브러리 #include #include #include #include 2. vector input받기 int N; cin >> N; for (int i = 0; i > tmp; v.push_back(tmp); } 3. sort하기 (sort를 꼭 해줘야함) sort(v.begin(), v.end(), comp_length); 4. erase하기 unique의 return값은 유일한 원소들이 끝나고 첫번째 쓰레기 원소가 나오는 곳의 위치이다. 예를 들면, 112335가 존재할 때 unique를 통해서 123513이 나오는데. 이때 빨간표시한 자리를 나타낸다. 그래..
[C++ STL] C++ 입출력 속도 향상 입출력 sync 끊기 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); endl 대신 \n 사용하기 cout
[C++ STL] algorithm헤더의 유용한 함수들(정렬, 최댓값, 최솟값) 코딩테스트 준비하면서 쓰고있는 함수들을 정리하려고 한다. 굳이 직접 짜서 쓰지 말고 STL을 잘 활용하는게 더 빠르고 편리하다. 배열과 벡터에 모두 적용하는 방법을 소개한다. (또 새로운 함수를 사용하면 추가로 작성할 예정이다.) 정렬하기: sort함수 그냥 사용하면 오름차순으로 정렬한다. (작은 것 -> 큰 것) #include using namespace std; int main() { int a[10] = { 9,3,5,4,1,10,8,6,7,2 }; sort(a, a + 10); for (int i = 0; i < 10; i++) { cout

티스토리툴바