위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.
알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.
강의링크
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