알고리즘 기초수학에 대해 알아봅시다!
집합
Set을 사용한 집합
- Set은 중복을 제거하고 저장한다.
교집합을 구할 때는? Set의 a.retainAll(b)
합집합을 구할 때는? a.addAll(b)
차집합을 구할 때는? a.remove(b);
여집합도 전체 여집합 Set에서 Set A를 remove해주면 된다!
그럼 Set을 언제 활용하면 좋을까?
- 중복제거가 필요할 때
경우의 수
중요한 부분? 은 약수, 최소공배수 ,최대공약수 부분이다.
사실 합의 법칙, 곱의 법칙은 따로 공부하고 있지 않아도 어렸을 때 수학공부했던 기억덕분에 로직이 생각나는 반면 약수, 최소 공배수, 최대공약수는 살짝 고민을 해봐야한다. 물론 구현하는데에 어려움은 없지만 자주 연습해서 익혀두는 것이 좋다!
참고로 최대공약수는 MOD(나누기연산)을 사용해서 재귀를 이용해 약수를 구하지 않고도 간단하게 구할 수 있다.
최소 공배수 = A * B / A와B의 최대공약수
최대 공약수 = A, B약수들 중에서 일치하는 값 중 제일 큰거, MOD연산과 재귀함수를 통해 구할 수도 있다.
약수 구하기= i=1 부터 n/2까지 연산을 통해서 n/2로직에 끝낼 수 있다. 마지막에 자기자신을 추가하는 것을 잊지말자
순열과 조합
위의 것들보다 훨씬 많이나오는 유형
언제나 내가 잘 못하는 유형이기도 하다 ㅋ 막상 기초문제를 풀면 잘 푸는데 응용은 아직 어려워 하는 느낌이 많이 든다.
순열과 조합의 간단한 원리를 적어보았다. 사실 이걸 굳이 다 알아야 하나 싶은데 개인적으로 내가 훨씬 쉽게 푸는 방법이 있다.
백준의 N과 M시리즈이다. 이거 1,2,3,4번까지 주구장창하면 백트래킹 조합이 그리 어렵지는 않게 된다. ~~~근데 응용문제에서 맨날 틀린다.
개인적으로 내가 생각하는 백트래킹의 사용 방법이다.
자기 자신을 중복해서 사용하느냐 - > isused사용
순열의 중복을 허용하느냐 - > st를 이용해 시작점 조절
이 두가지 항목을 기억하고 로직에 적용하는 편이다. 예시로
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
int n,m;
int arr[10];
bool isused[10];
void func(int k) {
if(k==m) {
for(int i=0; i<m; i++)cout << arr[i]<< " ";
cout << "\n";
return;
}
int st=1;
if(k !=0) st = arr[k-1];
for(int i=st; i<=n; i++) { //시작점을 조절해 순열의 중복 제거
if(!isused[i]) {
arr[k] = i;//index이자 숫자의 순서
isused[i] =1; // isused를 이용해 본인 사용 제거 1 2 3 (가능) 1 1 1(불가능)
func(k+1);
isused[i] =0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n>>m;
func(0);
}
1 2
1 3
1 4
2 3
2 4
3 4
위 문제에서 n =4 m=2(m은 depth를 의미) 인경우 해답은 이렇다.
시작점을 컨트롤 하지 않았을 경우의 답
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int n,m;
bool isused[10];
int arr[10]; //정답의 인덱스가 들어갈 배열
void func(int k) {
if(k==m) {
for(int i=0; i<m; i++)cout << arr[i] << " ";
cout << "\n";
return;
}
//st를 이용해서 시작점 조절한 부분을 없앰
for(int i=1; i<=n; i++) {
if(!isused[i]) {
arr[k] = i;
isused[i]=1;
func(k+1);
isused[i]=0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >>n >>m;
func(0);
}
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
같은 정보를 넣었을 때 (n=4, m=2)위와 같은 결과가 나오게 된다. 즉 본인만 제외하고 모든 조합이 나타나게 된다. 이 조합에는 중복된 조합도 섞여있다. (1,4 쌍과 4,1쌍은 중복된 값이다.)
순열과 조합문제는 N과 M 1,2,3,4번만 풀어봐도 대충 답이나온다.
전역변수 지정한 arr[]에서는 값의 인덱스가 들어간다는 것을 명심하자. 만약 값이 1,2,3,4같은게 아니라 배열로 주어진다면 value[arr[i]]를 통해 뽑아내면 된다.
REVIEW:
순열과 조합
순열과 조합은 수학적으로 생각하지 않았던 부분인데 새로 알게되어서 흥미로웠다!
풀어나가는 방식은 내가 생각하는 방식으로 하되 알게된 개념을 적용하는 방향으로 하는 것이 좋을 것 같다!
