알고리즘 자주 사용 함수(C++)(알고리즘)(fill, memset, memcpy,sort, unique, stable_sort)

위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.

알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.

강의링크

fill()과 memset()

fill()과 memset()은 배열을 초기화 할 때 쓰입니다

fill()

fill()은 O(n)의 시간복잡도를 가지며 fill(시작값, 끝값, 초기화하는값)로 값을 초기화합니다. 모든 값을 기반으로 초기화가 가능합니다.

void fill (ForwardIterator first, ForwardIterator last, const T& val);

fill()로 배열의 값을 초기화한다고 했을 때 배열의 모든 값이 아닌 일부값을 초기화하는 경우도 있지만 보통은 전체를 초기화 합니다.

#include <bits/stdc++.h> 
using namespace std;  
vector<int> v[10];  // 초기값이 0인 vector 1개를 생성 
vector<int> v2(10, 0);  // 크기 10 * 10, 초기값은 0 2차원 vector 생성 
vector <vector<int> > v3(10, vector<int>(10, 0));  // 크기가 정해지지 않은 2차원 vector 생성 
vector<vector<int> > v4;  // 1차원 배열을 만들어서 0으로 초기화하는 방법입니다. // 그러나 일부 컴파일러에서 통하지 않을 수도 있으니 쓰지 않는 것이 좋습니다. 
int dp[10] = {0,};  // 1차원 배열 a, 2차원 배열 a2 
int a[1000]; 
int a2[1000][1000];  
int main() 
{ 		
    // 이터레이터 기반으로 초기화 		
    fill(v2.begin(), v2.end(), INF); 		
    // 10으로 초기화, 1004까지 전체적으로 초기화 합니다. 		
    fill(a, a + max_n, 10); 		// fill을 이용한 2차원 배열 초기화 방법 1 		
    for(int i = 0; i < max_n; i++) fill(a2[i], a2[i] + max_n, INF); 		// fill을 이용한 2차원 배열 초기화 방법 2 [이걸 추천합니다.] 		
    fill(&a2[0][0], &a2[0][0] + max_n * max_n, INF); 		
    return 0; 
}

memset()

memset()은 바이트단위로 초기화를 하며 0, -1, char형의 하나의 문자(a, b, c, 등..)으로 초기화를 할 때만 사용합니다.

void * memset ( void * ptr, int value, size_t num );

memset(배열의 이름, k, 배열의 크기) 이렇게 사용합니다.

#include <bits/stdc++.h> 
using namespace std; 
const int max_n = 1004; 
int a[max_n]; 
int a2[max_n][max_n]; 
int main() 
{ 	
    memset(a, -1, sizeof(a)); 	
    memset(a2, 0, sizeof(a2)); 	
    for(int i = 0; i < 10; i++) cout << a[i] << " "; 	
    return 0; 
} 
//-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 %

앞의 코드를 보듯이 fill 보다는 간편하게 초기화하는 것을 볼 수 있습니다. 0 또는 -1이란 값으로 초기화할 때는 memset을 쓰는 것이 좋습니다. 그러나. 1 또는 10 이런 숫자는 절대 이 memset()으로 초기화 못하니 주의해주세요!

memcpy()

어떤 변수의 메모리에 있는 값들을 다른 변수의 “특정 메모리값”으로 복사할 때 사용합니다. 주로 배열을 깊은 복사할 때 사용합니다.

void * memcpy ( void * destination, const void * source, size_t num );

#include <bits/stdc++.h> 
using namespace std; 
int a[5], temp[5]; 
int main()
{ 	
    for(int i = 0; i < 5; i++)a[i] = i; 	
    memcpy(temp, a, sizeof(a)); 	
    for(int i : temp) cout << i << ' '; 	
    cout << '\n'; 	// 원본 배열 a를 수정하여 출력하는 로직 	
    // a를 수정해서 ~~를 더하는 로직이 될 수 있겠죠? 	
    a[4] = 1000; 	for(int i : a) cout << i << ' '; 	
    cout << '\n'; 	// 그 다음 다시 temp를 기반으로 원본배열을 담아 둠. 	
    memcpy(a, temp, sizeof(temp)); 
    for(int i : a) cout << i << ' '; 
    cout << '\n'; 	return 0; 
} 

/* 
0
1
2 
3 
4 
0
1 
2 
3
1000
0
1 
2 
3 
4 
*/

sort()

sort()는 배열 등 컨테이너들의 요소를 정렬하는 함수입니다. 보통 array나 vector를 정렬할 때 쓰이며 O(nlogn)의 시간복잡도를 가지는 함수입니다. sort()에 들어가는 매개변수로는 3가지가 있으며 2개는 반드시 넣어야 하며 한개는 선택입니다. (넣어도 되고 안 넣어도 됩니다. 커스텀하게 정렬하고 싶을 때 넣습니다.)

sort(first, last, *커스텀비교함수)

이렇게 들어갑니다. first는 정렬하고 싶은 배열의 첫번째 이터레이터, last는 정렬하고 싶은 배열의 마지막 이터레이터를 넣으면 됩니다. 또한 [first,last) 라는 범위를 갖습니다.

즉, first는 포함하고 last는 포함하지 않는다는 의미입니다. 그렇기 때문에 예를 들어 크기가 5인 a라는 배열 전체를 sort한다고 하면 sort(a[0],a[0] + 5)라고 해야 합니다. 즉, last에 배열의 마지막요소가 아닌 그 “다음”의 위치를 넣어주어야 합니다.

다시 말하자면 a[0] + 5는 배열의 마지막원소가 아닙니다. 마지막원소는 a[0] + 4이겠죠? 하지만 sort()의 특성상 last)로 last는 포함하지 않기 때문에 마지막 원소 그 다음의 위치를 가리켜야 하는 것이죠.

3번째 인자로는 커스텀비교함수(선택)이 있습니다. sort에 커스텀비교함수를 넣지 않으면 기본적으로 오름차순이며 이를 3번째 인자에 greater<int>()를 넣어 내림차순등으로 변경할 수 있습니다. 참고로 less<int>()을 통해 오름차순으로 정렬할 수 도 있습니다

#include <bits/stdc++.h> 
using namespace std; 
vector<int> a; int b[5]; 
int main()
{ 	
    for(int i = 5; i >= 1; i--) b[i - 1] = i;  	
    for(int i = 5; i >= 1; i--) a.push_back(i);  	
    // 오름차순 
    sort(b, b + 5); 	
    sort(a.begin(),a.end());  
    for(int i : b) cout << i  << ' '; 
    cout << '\n'; 
    for(int i : a) cout << i  << ' '; 
    cout << '\n';  	
    sort(b, b + 5, less<int>());  
    sort(a.begin(),a.end(), less<int>());  
    for(int i : b) cout << i << ' ';  	cout << '\n'; 
    for(int i : a) cout << i << ' ';  	cout << '\n'; 	 
    //내림차순 	
    sort(b, b + 5, greater<int>());  
    sort(a.begin(),a.end(), greater<int>());  
    for(int i : b) cout << i << ' '; cout << '\n'; 	
    for(int i : a) cout << i << ' '; 	cout << '\n'; 	
    return 0; 
} 	

/* 	
12345  		
12345  		
12345  		
12345  	
54321  	
54321  
*/

pair를 기반으로 한 vector 정렬

pair를 기반으로 만들어진 vector의 경우 따로 설정하지 않으면 first, second, third 순으로 차례차례 오름차순 정렬됩니다.

#include<bits/stdc++.h> 
using namespace std;  
vector<pair<int, int>> v; 
int main()
    { 	
    for(int i = 10; i >= 1; i--)
    { 
    	v.push_back({i, 10 - i}); 
    } 
    sort(v.begin(), v.end()); 	
    for(auto it : v) cout << it.first << " : " << it.second << "\n"; 
    return 0;
}

/*  
1:9  
2:8
3:7  
4:6 
5:5 
6:4 
7:3 
8:2  
9:1  
10:0  
*/

 

unique()

unique는 범위안의 있는 요소 중 중복되는 요소를 제거하고 중복되지 않은 요소들로 앞에서부터 정렬되어 채웁니다. 그리고 나서 나머지 요소들은 삭제하지 않고 그대로 두는 함수입니다. O(n)의 시간복잡도를 가집니다.

#include <bits/stdc++.h> 
using namespace std;  
vector<int> v; 
int main () 
{ 	
    for(int i = 1; i <= 5; i++)
    {  		
        v.push_back(i); 	
        v.push_back(i);  
    } 
    for(int i : v) cout << i << " "; 	cout << '\n';
    // 중복되지 않은 요소로 채운 후, 그 다음 이터레이터를 반환한다. 
    auto it = unique(v.begin(), v.end()); 	
    cout << it - v.begin() << '\n'; 
    //앞에서 부터 중복되지 않게 채운 후 나머지 요소들은 그대로 둔다.  	
    for(int i : v) cout << i << " "; 	cout << '\n'; 	
	return 0; 
} 
/* 
1 1 2 2 3 3 4 4 5 5  
5 
1 2 3 4 5 3 4 4 5 5 */

따라서 unique()를 통해 중복되지 않은 요소들의 집합을 만들고 싶다면 다음 코드처럼 구축 하면 됩니다. sort(), erase(), unique() 순입니다.

#include <bits/stdc++.h> 

using namespace std;  
vector<int> v; 
int main () 
{ 	
for(int i = 1; i <= 5; i++)
{ 	
    v.push_back(i);  	
    v.push_back(i); 	
} 
for(int i = 5; i >=1; i--)
{ 		
    v.push_back(i); 	
    v.push_back(i);  
} 
    sort(v.begin(), v.end()); 
    for(int i : v) cout << i << " "; cout << '\n';
    v.erase(unique(v.begin(), v.end()), v.end()); 
    for(int i : v) cout << i << " ";
    return 0; 
} 

// 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 
// 1 2 3 4 5

stable_sort()

stable_sort 함수는 여러 값들이 묶여 있을 때 하나의 요소로 정렬 할 때 다른 요소들의 정렬 순서도 정렬 전과 같이 유지 될 수 있도록 하는 정렬입니다.

#include <algorithm>
bool my_sort(pair<int,int> a,pair<int,int> b)
{
	return (a.second > b.second);
}

stable_sort(arr.begin(),arr.end(),my_sort);

사용은 sort와 비슷하게 사용이 됩니다.

또 stable_sort가 sort보다 빠르며, 유용하게 쓰일 때가 있다.

인자로 비교하는 함수에 레퍼런스 타입을 넣어주게 되면 컴파일 에러가 난다.

bool my_sort(pair<int,int> &a,pair<int,int> &b)

비교 함수를 이렇게 만들었었는데 자꾸 에러가 나서 레퍼런스를 지웠더니 컴파일이 됐다.

이렇게 const를 붙혀도 된다.

bool my_sort(const pair<int,int> &a,const pair<int,int> &b)
{
	return (a.second > b.second);
}

이게 되는 이유는 함수의 전달인자가 반드시

bool cmp(const Type1 &a, const Type2 &b);

이렇게 생겨야 하기 때문이다.