C++에서 헤더 파일에 있는 sort와 stable_sort를 통해서 정렬하는 방법을 알아보자.


환경 및 선수조건


sort() 사용하기

  • 배열의 경우
#include <iostream>
#include <algorithm>

using namespace std;

int main (){

    int a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    sort(a, a+100);
}
  • 벡터의 경우
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main (){

    vector<int> a(100);

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = iterator의 begin()
    // 두번째 인자는 끝나는지점 + 1 = iterator의 end()
    sort(a.begin(), a.end());    
}


sort() 사용하기(비교함수 이용하기)

  • 때로는 직접 비교함수를 추가해줘야하는 경우가 있다 사용법은 위와 동입하며 함수만 3번째 인자로 추가해주면 된다.
  • Point라는 구조체를 정렬한다고 가정해보자.
#include <iostream>
#include <algorithm>

using namespace std;

struct Point{
    int x;
    int y;
};

// const와  &를 통해서 레퍼런스로 받아오는걸 잊지말자!
// x순으로 정렬하고 x값이 같으면 y순으로 각각 오른차순으로 정렬
bool cmp(const Point &p1, const Point &p2){
    if(p1.x < p2.x){
        return true;
    }
    else if(p1.x == p2.x){
        return p1.y < p2.y;
    }
    else{
        return false;
    }
}

int main (){

    Point a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    sort(a, a+100, cmp);
}


stable_sort() 사용하기

  • stable_sort()는 구조체처럼 여러 값들이 묶여 있을 때 하나의 요소로 정렬을 했을 때 다른 요소들의 정렬 순서도 정렬 전과 같이 그대로 유지 될 수 있도록 하는 정렬이다.
#include <iostream>
#include <algorithm>

using namespace std;

struct Point{
    int x;
    int y;
};

// const와  &를 통해서 주소값을 받아오는걸 잊지말자!
// x순으로 정렬하고 x값이 같으면 y순으로 각각 오른차순으로 정렬
bool cmp(const Point &p1, const Point &p2){
    if(p1.x < p2.x){
        return true;
    }
    else if(p1.x == p2.x){
        return p1.y < p2.y;
    }
    else{
        return false;
    }
}

int main (){

    Point a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    stable_sort(a, a+100, cmp);
}


참고자료

  • 코드플러스 알고리즘 기초 강의

소수를 구할 때 가장 빠른 시간에 구할 수 있는 에라토스테네스의 체의 방법을 알아보자


환경 및 선수조건

  • C++


에라토스테네스의 체

2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.

  1. 2부터 시작해서 n까지 진행한다.
  2. 가장 작은 수를 선택한다.
  3. 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.


  • 시간복잡도 : O(n*log(log(n)))


코드

  • count : 저장된 소수의 개수
  • c[n+1] : 2 ~ n까지 수에서 제거된 숫자를 체크하는 배열, true(제거됨), false(제거되지않음)
  • p[n] : 소수를 저장하는 배열

example.cpp

bool c[1000001]= {false,};
int p[1000000];
int count = 0;

//0~1000000까지 소수 구하기
for(int i=2; i<=1000000; i++){
	if(c[i] == false){
		// 추가
		p[count++] = i;
		// i의 배수 지우기
		for(int j=i+i; j<=1000000; j+=i){
			c[j]=true;
		}
	}
}


참고자료

  • 코드플러스 알고리즘 기초 강의

업데이트(2018.04.29) : a mod b 부분 추가

유클리드 호제법을 통해서 최대공약수를 공하고 최대공약수를 통해서 최소공배수를 구해보자


환경 및 선수조건

  • C++


최대공약수 공식(유클리드 호제법)

  • a,b : 최대공약수를 구하고자 하는 두 수
  • r : a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
  • 식 : gcd(a,b) = gcd(b,r)


코드(최대공약수)

example.cpp

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}


최소공배수 공식(최대공약수를 이용)

  • a,b : 최소공배수를 구하고자 하는 두 수
  • gcd(a,b) : a와b의 최대공약수
  • (최소공배수 * 최대공약수 = a * b)를 이용
  • 식 : a * b / gcd(a,b)


코드(최소공배수)

example.cpp

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

int lcm(int a, int b){
    return a * b / gcd(a,b);
}


참고자료

  • 코드플러스 알고리즘 기초 강의

알고리즘 문제를 풀 때 연산의 결과가 너무 커서 어떠한 수로 나눈 나머지를 통해 해를 답을 구하는 경우가 있는데 이 때 어떻게 이용할 수 있는지 보자


환경 및 선수조건

  • C++


공식

  • 합: (A + B) % M = ((A % M) + (B % M)) % M
  • 곱: (A X B) % M = ((A % M) X (B % M)) % M
  • 차: (A - B) % M = ((A % M) - (B % M) + M) % M
  • 뺄셈의 경우에는 % 결과가 음수로 나올 수 있기 떄문에 M을 더해준다


유도(덧셈만)

다음 아래 사진처럼 식 유도가 가능합니다 Equation


참고자료

  • 코드플러스 알고리즘 기초 강의

for문 조건문으로 strlen으로 조건을 주었을 때 발생하는 문제에 대해 생각해보자.


환경 및 선수조건

  • C++


비교

  • strlen을 for문에 사용하였을 경우
  • 시간 복잡도 : O(n^2)
...
for(int i=0; i<strlen(s); i++){
    // Do Something
}
...


  • strlen를 for문 밖에 사용하였을 경우
  • 시간 복잡도 : O(n)
...
int len = strlen(s)
for(int i=0; i<len; i++){
    // Do Something
}
...


참고자료

  • 코드플러스 알고리즘 기초 강의