반응형
1. 입출력 시간 단축
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);- C++ 표준 스트림과 C 표준 스트림의 동기화를 끈다
- endl 대신 "\n"을 사용하기
2. 순열 (next_permutation)
- 서로 다른 n개의 원소에서 r개를 뽑는다
- 순서가 다르면 다른 경우로 판단
- algorithm 헤더의 next_permutation 함수를 사용
- 오름차순으로 정렬된 값을 가진 컨테이너에만 사용 가능
- 오름차순으로 순열 생성
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> v{ 1, 2, 3 };
sort(v.begin(), v.end());
do {
for (auto i = v.begin(); i != v.end(); i++)
{
cout << *i << " ";
}
cout << "\n";
} while (next_permutation(v.begin(), v.end()));
return 0;
}
3. 순열을 이용한 조합 구하기
배열 arr에서 n개의 원소 중 r개의 원소를 택하는 방법은 아래와 같다.
- r개의 원소는 1, (n-r)개의 원소는 0인 배열 temp를 만든다.
- temp의 모든 순열을 구한다
- temp의 순열에서 원소가 1인 인덱스만 arr에서 가져온다.
next_permutation이 오름차순으로 정렬되기 때문에 조합은 내림차순으로 정렬된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> v { 1, 2, 3, 4, 5 };
vector<int> temp{ 0, 0, 0, 1, 1 };
sort(v.begin(), v.end());
do {
for (int i = 0; i < v.size(); i++)
{
if (temp[i] == 1) cout << v[i] << " ";
}
cout << "\n";
} while (next_permutation(temp.begin(), temp.end()));
return 0;
}
4. 2차원 배열의 나선형 알고리즘
- 홀수 길이의 2차원 배열의 중심에서 시작하여 방향을 바꾸며 이동
- 방향을 2번 바꿀 때마다 이동 거리가 1씩 증가한다
5. 배열 회전
- 배열 전체를 90도 회전
- 시계 방향: board[c][n-1-r] = board[r][c]
- 반시계 방향: board[n-1-c][r] = board[r][c]
반응형
