오늘의 공부

erase와 remove의 차이

erase, remove

한줄로 간단하게 말하자면 erase는 멤버함수이고 remove는 알고리즘이다.

◎ erase

컨테이너의 erase는 실제 객체를 제거한다.

하나를 지울 수 있는데 STL의 데이터 공간까지 다 지우는 것이다.

즉, iterator에 해당하는 하나의 요소만을 삭제하며 capacity가 감소한다.

	vector<int> v;
	v.resize(10, 0);

	for (int i = 0; i < v.size(); ++i)
	{
		v[i] = i + 1;
	}

다음과 같이 1부터 10까지의 벡터가 있다고 가정한다. 

	auto iter = v.begin();
	v.erase(iter + 1); // index 1번값 = 2

	printVector(v);

iterator가 begin값에서 +1, 즉 2를 가리키고 있는 상태에서 erase시키면 다음과 같은 결과가 나온다. 

◎ remove

Algorithm의 remove는 그 요소를 덮어씌움으로써 지워진 것처럼 보이게 된다.

정확하게 말하면 지워야 할 원소를 뒤의 원소들을 하나씩 앞으로 당겨서 덮어 씌우는 것이다. 

erase는 capacity까지 감소되었지만 remove는 조건을 함께 넘기면 조건과 일치하는 원소들은 다 지워지는데 공간은 그대로 남아있고 데이터만 삭제 된다.

즉, 해당 조건에서 일치하는 모든 요소는 삭제하지만 capacity는 그대로이다. 

◎ erase + remove?

특정 조건에 해당하는 원소를 아예 지우려면 erase와 remove를 함께 사용하면 좋다.

remove는 제거되지 않은 마지막 원소를 가리키는 itertor를 리턴하기 때문에 

erase( remove(시작, 끝, value), 컨테이너의 end 반복자); 

의 형태로 사용해준다. 

Permutation

순열

◎ 수학에서 순열 구하기

n개에서 r개를 택하는 순열이란 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것이다. 

여기서 중요한 것은 '순서 있게'다. 왜냐하면 개념이 헷갈리는 조합은 '순서'가 없이 나열하는 것이기 때문에 구분을 잘 해야 한다. 

표현은 주로 nPr로 한다. (n개에서 r개를 택하는 Permutation)

이 순열을 구하는 방법은 간단하다. 바로 팩토리얼을 이용하면 된다.

식을 간단하게 표현하면 위와 같다. 

◎ Permutation 사용

순열을 구하기 위해서는 재귀를 통해서 직접 구현할 수도 있다. 하지만 stl에 있는 기능을 가져다가 사용하면 빠르고 간단하게 순열을 만들 수 있다.

std::prev_permutation과 std::next_permutation은 현재 범위가 현재보다 더 작은 순열(이전 순열) 또는 더 큰 순열(다음순열)이 되도록 요소들을 정리한다. 이전 순열이나 다음 순열이 있으면 true, 없으면 false를 리턴한다. 

이때 순열이 끝나 false를 리턴하는 경우는 완전히 역순이 되는 경우다. 이 때 다시 원래 순서대로 바꾼뒤에 false를 리턴하는 것이다. 

ex) 1234의 경우 return 하기 직전 4321였다가 false를 리턴할때 다시 1234로 만들어준다. 

단 permutation은 중복이 있는 경우에는 중복을 제외하고 순열을 만들어준다. 

permutation 기능의 원리는 다음과 같다.

1. 우선 뒤에서부터 탐색을 시작한다. 오름차순의 형태를 띄는 구간이 나올 때까지 진행하며 작은 쪽은 i, 큰 쪽은 ii라고 가정한다. 

2. 그 다음에는 뒤에서부터 i보다 큰 j를 찾아 i와 j를 바꿔준다.

3. 그 후 ii를 포함해 뒷부분을 모두 reverse한다. 

범위를 이전 순열로 만드는 것

범위를 다음 순열로 만드는 것

위의 인자에 정렬 기준을 명시적으로 사용할 수 있다. 기본적으로는 std::less가 사용된다.

두 알고리즘 중 어떤 것을 사용하든, 주어진 범위의 모든 순열을 손쉽게 생성할 수 있다. 

ex ) permutation을 사용한 예시 

#include <algorithm>

std::vector<int> Init{1,2,3};
do{
	for(auto i:Init) std::cout << i;
	std::Cout << " ";
} while(std::next_permutation(Init.begin(), Init.end())); 

// 출력 예시 123 132 213 231 312 321 

std::reverse(Init.begin(), Init.end());
do{
	for(auto i:Init) std::cout << i;
    std::cout << " ";
 } while(std::prev_permutation(Init.begin(), Init.end()));
 
 // 출력 예시 321 312 231 213 132 123

permutation말고 직접 순열 구하기? 

참고 자료;

namu.wiki/w/%EC%88%9C%EC%97%B4

핵심 C++ 표준 라이브러리 (라이너 그림 지음; 류광 옮김. 인사이트) 

jeonggyun.tistory.com/110