[C++] ICPC 25W 3회차 - 정렬, 수학

제곱시간 미만 정렬

합병정렬(merge sort)

 

void merge(vector<int>&arr, int start, int mid, int end){
	int leftIdx=start;
    int rightIdx=mid+1;
    vector<int> sorted;
    while (leftIdx <= mid && rightIdx <= end){
		if(arr[leftIdx] <= arr [rightIdx]){
        	sorted.push_back(arr[leftIdx]);
            leftIdx++;
        }else{
        	sorted.push_back(arr[rightIdx]);
            rightIdx++;
        }
   }
   while (leftIdx <= mid){
		sorted.push_back(arr[leftIdx]);
        leftIdx++;
   }
   while (rightIdx <= end){
		sorted.push_back(arr[rightIdx]);
        rightIdx++;
   }
for(int i=start; i<=end; i++){	
	arr[i]=sorted[i-start];
 }
}

void mergeSort(vector<int>& arr, int start, int end){
	if (start >= end) return;
    int mid = (start + end) /2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1, end0;
    merge(arr, start, mid, end);
 }
 
 void solve(){
 	vector<int> arr={2, -33, 24, 4, 54, 1, 2453, -3455, 342445};
    mergeSort([&]arr, start:0, end:(int)arr.size()-1);
    for(int i:arr) cout<<i<<" ";
 }

 

counting sort

값의 개수를 세서 정렬

void countingSort(vector<int>&arr){
	int maxVal=0;
    for(int i: arr)maxVal = max(a:maxVal, b:i);
    vector<int> count(n:maxVal+1);
    for(int i:arr)count[i]++;
    int idx=0;
    for(int i=0; i<=maxVal; i++){
		while(count[i] >0){
			count[i]--;
            arr[idx]=i;
            idx++;
       }
  }
  
  void countingSort(vector<int>& arr){
	int maxVal=0;
    for(int i:arr)maxVal=max(a:maxVal,b:i);
    vector<int>count(n:maxVal+1);
    for(int i:arr) count[i]++;
    int idx=0;
    for(int i=0; i<=maxVal; i++){
		while(count[i].0){
			count[i]--;
            arr[idx]=i;
            idx++;
       }    
   }
   
  vector<int> arr={2,0,24,4,54,1,2453,3455,13,24};
  countingSort9[7]arr);
  for(int i:arr) cout << 1 << " ";

 

cpp 기본정렬

sort(시작위치, 종료위치, cmp)

void solve(){
	vector<int> arr={2,0,24,4,54,1,2453,3455,13,24};
    sort(first:arr.begin(), last:arr.end());
    for(int i:arr) cout << i << " ";
    cout << endl;
    
    arr={2,0,24,4,54,1,2453,3455,13,24};
    sort(first:arr.begin()+3, last:arr.end());
    for(int i:arr) cout << i << " ";
    cout << endl;
    
    arr={2,0,24,4,54,1,2453,3455,13,24};
    sort(first: arr.begin(), last: arr.end()-3);
    for (int i : arr) cout << i << " ";
    cout << endl;
    
    int arr2[]={2,0,24,4,54,1,2453,3455,13,24};
    sort(first: arr2, last: arr2+10);
    for(int i: arr2) cout << i << " ";
    cout << endl;
   }

 

cmp 함수

• 정렬의 기준을 알려주는 함수
• a와 b를 비교할 때, 해당 함수가 true라면 a가 b보다 앞에 있어야 한다 라는 뜻.
• false라면? 
  • a가 b보다 뒤에 있어야 한다 : x
  • a가 b의 앞에 있지 않아도 된다.
• 유의할 점: 절대 등호 넣지 말기

bool cmp(int a, int b){
	return a<=b;
}

• 해당함수가 true이면 a는 반드시 b 앞에 와야 함. 그러나 a와 b가 같다면? 그와 같은 c가 있다면?
  • 굳이 앞에 올 필요가 없는데 서로가 서로의 앞에 서려는 꼬리잡기가 펼쳐짐 --> 맞왜틀, 런타임에러 발생가능

 

수학

올림, 내림

• 내림: A/B 
• 올림: A/B에다가 A%B가 0이 아니면 1 더해주기

int a=17, b=5;
int ans=a/b;
if (a%b != 0) ans += 1;

//아니면 

int a=17, b=5;
int ans=(a+b-1)/b;

 

음수 나눗셈

• 몫 나눗셈: 절댓값 계산 이후 부호를 붙여줌
• 나머지 연산: 자기 맘대로. 
  • 뺄셈이 일어날 경우 나머지가 음수로 나올 가능성이 있음
    • 연산의 결과값이 음수라면 나눠준 수를 더해줘야 함
      • ex. 17%5와 -17%5는 실제로 다른 값

 

소수

• 1과 자기 자신만을 약수로 가지는 자연수
• 어떤 수 N이 소수임을 보이려면?
  • N을 2부터 N-1까지로 나눠보며 나누어 떨어지는지 보면 됨.

int n=100003;
int flag =1;
for(int i=2; i<n; i++){
	if(n%1==0){
    	flag=0;
        break;
     }
 }
 if (flag ==1)cout << "prime" << endl;
 else cout << "not prime" << endl;

• 시간복잡도: 2부터 N-1까지니까 O(N)

O(sqrt(N))으로 판정하는 법

• 기본 아이디어: N이 합성수라면 N=p*q로 나타내어지는 p와 q가 있다. 에서 출발
  • p<=q라 생각하기. 만약 p가 sqrt(N)보다 크다면 q도 sqrt(N)보다 당연히 큼 >> p*q가 N이 될 수 X
  • N을 2부터 sqrt(N)까지 나눠보며 나누어 떨어지는지 확인하면 됨

int n=100007;
int flag =1;
for(int i=2; i*i<=n; i++){
	if(n%1==0){
    	flag=0;
        break;
     }
 }
 if (flag ==1)cout << "prime" << endl;
 else cout << "not prime" << endl;

 

• 판정할 수 있는 소수범위가 제곱으로 증가
• 유의할 점: n이 int 범위를 벗어나는 경우, 반복문에서 사용되는 변수 i도 long long으로 선언해야 함
  • 그렇지 않을 경우 i*i<=n계산 조건절에서 i가 int라 오버플로우가 나서 맞왜틀 할 수 있음

 

소인수분해

• 합성수를 소인수들의 곱으로 나타내는 것 
• 소인수분해를 하기 위해 소수 판정을 할 필요는 x
  • 2부터 차례대로 해당 수를 나눠준다고 생각: ex) 42는 2로 나눠져서 21이 되고, 21인 상태에서 3으로 나눠져 7이 됨. 6에 도달했을 때는 이미 2와 3으로 나눠진 상태.

long long n=400028;
vector<int> p;
for(int i=2; i<=n; i++){
	while (n%i==0){
    p.push_back(i);
    n /= i;
   }
  }
  for(int i:p) cout << i << " ";

• 시간복잡도 : O(N)
• 소인수분해도 이전과 같은 아이디어로 O(sqrt(N))으로 최적화 가능
• N=p*q*...*s로 이루어진 합성수일 때 sqrt(N)보다 큰 소인수는 최대 1개. 에서 출발
  • 2개 이상이라면 소인수끼리 곱했을 때 N을 넘어버림
  • sqrt(N)까지만 보고, 만약 소인수분해가 끝났는데 N이 1이 아니라면 그때의 N이 가장 큰 소인수가 됨

int n=400028;
vector<int> p;
for(int i=2; i*i<=n; i++){
	while (n%i==0){
    p.push_back(i);
    n /= i;
   }
  }
  if(n!=1) p.push_back(n);
  for(int i:p) cout << i << " ";

 

에라토스테네스의 체

 

• 소수가 아니다? 패스  ,  소수다? 본인의 배수를 모두 소수가 아니라 판정

int n=100;
vector<int> p(n+1, value:1);
vector<int> prime;
p[1]=0;
for(int i=2; i<=n; i++){
	if(p[i]==0) continue;
    prime.push_back(i);
    for(int j=i+i; j<=n; j+=i){
    	p[j]=0;
    }
 }
 cout << prime.size() <<endl;
 for (int i: prime)cout<< i<< " ";

• 에라토스테네스 체의 시간복잡도: O(nlogn)