백투더코딩

알고리즘 스터디에서 발표를 맡은 문제 중 다른 코드를 참고해 좀 특이한 방식으로 sort 함수 비교 부분을 커스터마이징한 코드가 있었다. 필자도 이번에 처음 본 작성 방식이라 정리해두면 좋을 것 같아 포스팅을 하게됐다.

기본 세팅

#include <algorithm>

위 헤더파일을 include해야 sort 함수를 사용할 수 있다.

compare 커스터마이징 사용안할 시 sort 함수 

vector <int> v(6,6);
sort(v.begin(),v.end());

첫  번째 인자로 정렬을 시작할 부분의 iterator 혹은 포인터를 넣어주고

두 번째 인자로 정렬의 끝인 부분의 iterator 혹은 포인터를 넣어주면 된다.

참고로, 알고리즘 헤더파일을 삽입해 사용하는 sort 함수는 quick sort와 insertion sort를 섞은 intro sort를 사용한다.

해당 함수의 시간 복잡도는 평균 nlogn, 최악일 경우 n^2이다.

compare 커스터마이징 사용할 시 sort 함수 type 1

vector <int> v(6,6);
 
bool compare(int i, int j) { return i > j; }
 
sort(v.begin(),v.end(),compare);

첫 번째 인자와 두 번째 인자는 동일하며 세 번째 인자로 커스터마이징한 compare 함수를 넣어준다.

함수명이 compare일 필요는 없다. 

예시로 적은 위 코드는 내림차순으로 정렬되는 코드이다.

compare 커스터마이징 사용할 시 sort 함수 type 2

이 포스팅을 하게 된 계기는 아래 코드인데 배열 하나에서의 값들만 비교해서 정렬을 해주는 것이 아니라

다른 배열의 값을 기준으로 정렬을 할 수도 있다.

또한, 함수를 따로 분리하여 작성하지 않아도 sort 함수 내에서 아래와 같이 작성가능하다.

이때 주의해야되는 점이 c++14 이상 버전에서만 문제 없이 빌드된다.

vector<int> a[10000000];
vector<int> order(n);

for (int i=0; i<n; i++) {
        sort(a[i].begin(), a[i].end(), [&](const int &k, const int &l) {
            return order[k] < order[l];
        });
   }

참고 사이트 

https://yeondube.tistory.com/entry/sort-%ED%95%A8%EC%88%98-%EC%BB%A4%EC%8A%A4%ED%84%B0%EB%A7%88%EC%9D%B4%EC%A7%95

https://charles098.tistory.com/130

https://seongjuk.tistory.com/entry/c-sort-%ED%95%A8%EC%88%98-%EC%BB%A4%EC%8A%A4%ED%85%80-%ED%8A%B9%EC%A0%95-%EC%A1%B0%EA%B1%B4-%EC%A0%95%EB%A0%AC-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-%EC%A0%95%EB%A0%AC

https://leeeegun.tistory.com/5

사용 준비

헤더파일 추가

#include <algorithm>

사용

함수에 배열의 주소 또는 벡터의 iterator를 넣어주면 다음 순열과 이전 순열을 구할 수 있다. 

next_permutation 함수 

현재 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구해주는 함수

다음 순열이 존재해 구할 수 있다면 true 반환 다음 순열이 없다면 false 반환

// 첫번째 인자:순열의 시작, 두번째 인자:순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

예시 코드

vector <int> min(k);
do{
      for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}

		cout << '\n'; 
}while(next_permutation(min.begin(),min.end()));

prev_permutation 함수

현재 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구해주는 함수

이전 순열이 존재해 구할 수 있다면 true 반환 이전 순열이 없다면 false 반환

//직접 비교함수를 넣어주는 경우
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

예시 코드

vector <int> min(k);
do{
      for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}

		cout << '\n'; 
}while(prev_permutation(min.begin(),min.end()));

참고 사이트

https://twpower.github.io/82-next_permutation-and-prev_permutation

덱(Deque)이란?

벡터의 단점을 보완하기 위해 만들어진 컨테이너

새로운 원소가 삽입될 때마다 메모리 재할당 후 이전의 값들을 복사하는 벡터와 달리

덱은 미리 일정한 크기의 메모리 블록을 할당해 둔 후 값을 저장함.

데이터의 삽입과 삭제의 위치가 정해진 큐와 달리 덱은 앞 뒤로 다 데이터를 삽입/삭제 할 수 있음

헤더파일 삽입

#include <deque>

using namespace std;

데이터 생성

deque <type> dq;

deque dq;

deque dq(10);

0으로 초기화된 10개 원소 가진 덱 생성

deque<int> dq = { 1, 2, 3 };

deque dq2(dq1);

dq1의 내용을 복사한 덱 dq2 생성

데이터 삽입/삭제

dq.push_front(3);

첫 번째 원소 앞에 5 삽입

dq.push_back(4);

마지막 원소 뒤에 4 추가

dq.insert(2, 5);

2번째 위치에 5 추가

dq.insert(2, 5, 4);

2번째 위치에 5개의 데이터 값 4 추가

dq.pop_front();

첫 원소 삭제

dq.pop_back();

마지막 원소 삭제

dq.clear();

데이터 다 삭제

iterator

dq.begin()

첫 번째 원소 iterator

dq.end()

마지막 원소의 다음! iterator

데이터 조회

dq.at(idx);

idx번째 데이터 참조

dq[idx];

덱 사이즈

dq.size();

데이터 개수 리턴

dq.resize(10);

덱의 크기를 10으로 변경크기가 더 증가했다면 0으로 채움

dq.resize(10,2);

덱의 크기를 10으로 변경

크기가 더 증가했다면 2로 채움

참고사이트

https://blockdmask.tistory.com/73

https://velog.io/@choiiis/C-STL-deque%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC

큐에 대한 자료구조 설명

https://cofls6581.tistory.com/118

헤더파일 삽입

#include <queue>

데이터 선언

queue<int> q;

데이터 추가/삭제

q.push(2);

q.pop(); front 데이터를 삭제

데이터 조회

q.front(); 최상위 데이터 반환

q.back(); 제일 마지막 데이터 반환

데이터 크기

q.size();

q.empty(); 비어있으면 true 아니면 false

데이터 swap

swap(queue1 , queue2); 두 큐의 내용 swap

참고사이트

https://life-with-coding.tistory.com/408

vector 컨테이너

-가변 길이 배열을 구현한 제네릭 클래스

-스스로 내부 크기를 조정하므로 개발자가 크기에 대해 고민한 필요가 없는 장점

-배열의 원소를 저장, 삭제, 검색하는 멤버 함수들을 제공

-인덱스 0부터 시작

vector 사용

#include<vector>

using namespace std;

vector 멤버 함수

▶vector 객체 생성

vector<int> v;

비어있는 벡터 v 생성

vector<int> v(3);

0으로 초기화된 3개 원소 벡터 v 생성

vector<int> v(3,2);

2로 초기화된 3개 원소 벡터 v 생성

vector<int> v2(v1);

v1 벡터 복사해서 v2벡터 생성

▶vector 원소 삽입

v.push_back(2);

벡터 v에 2 삽입

v.insert(3,2);

벡터 v의 위치 3에 2 삽입

v.insert(3,5,3);

3의 위치에 5개의 3 삽입

그다음 값들이 뒤로 밀림

▶vector 원소 삭제

v.clear();

모든 원소 제거, 메모리는 남아있음

v.pop_back();

벡터 v의 마지막 원소 삭제

v.erase(iter);

반복자 iter가 가리키는 원소에 접근해서 벡터 v의 원소 삭제

사이즈는 줄어들고 메모리는 남아있음

▶vector 원소 접근

v[idx];

idx번째 원소 접근

v.at(idx);

idx번째 원소 접근

v.front();

첫 번째 원소 접근

v.back();

마지막 원소 접근

v.begin();

반복자로 접근 시 제일 처음 데이터의 위치 가리킴

v.end();

반복자로 접근 시 제일 마지막 데이터의 위치 가리킴

▶vector 사이즈

v.size();

원소 갯수 리턴

v.capacity();

할당된 공간의 크기 리턴

v.empty();

비어있으면 true 리턴 아니면 false 리턴

비어있다의 기준은 사이즈 O 용량 X

v.resize(5);

벡터 v의 크기를 5로 변경

v.resize(5,10);

벡터 v의 크기를 5로 변경한 후 값 10으로 초기화

참고

서적: 명품 C++ 프로그래밍

사이트: https://blockdmask.tistory.com/70

https://life-with-coding.tistory.com/411

STL(Standard Template Library)

템플릿으로 작성된 제네릭 클래스들과 함수들 라이브러리

->보다 쉽게 프로그래밍을 할 수 있음

STL의 3가지 종류

1. 컨테이너(클래스)

자료 구조 구현 클래스

2. 반복자(컨테이너 원소 포인터)

반복자=iterator

컨테이너의 원소들에 접근하기 위한 원소에 대한 포인터

ex) iterator(다음 원소 전진), reverse_iterator(지난 원소 후진)

3. 알고리즘(함수)

템플릿 함수

컨테이너의 원소들에 대한 기능을 구현

ex) 복사, 검색, 삭제 등

보통 이 세 가지를 아우러서 함께 사용함

STL은 std 이름 공간에 저장돼있기 때문에 using namespace std; 코드가 필요하다.

참고

서적: 명품 C++ 프로그래밍