TWpower Reading time ~1 minute

업데이트(2020.05.26): 배열의 크기를 변수로 받아서 동적으로 그래프를 생성하는 예시 추가

업데이트(2019.03.02): 그래프(방향, 무방향) 이미지 추가

C++에서 그래프를 구현하는 방법을 알아보자.


환경 및 선수조건

  • C++
  • 그래프의 기본 개념(정점, 간선 등등)


그래프의 구현

  • 행렬을 이용한 구현
  • List를 이용한 구현(vector를 Linked List처럼 사용)


행렬

개념

  • 행렬: 정점
  • 행렬값: 가중치 값(연결만 되었으면 1)
  • 행과열은 정점을 나타내고 [i][j]값은 정점 i로부터 j가 연결되어있으면 1 아니면 0으로 표시
  • 가중치가 있다면 [i][j]에 가중치를 저장


방향 그래프

  • 방향 그래프 예시


무방향 그래프

  • 무방향 그래프 예시
  • 무방향 그래프는 행렬이 대칭임을 알 수 있습니다.


코드

#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m; // 정점과 간선의 개수를 입력받음

    int graph[n+1][n+1];

    // Visual Studio의 경우
    /* 변수를 통해서 배열을 동적으로 생성할 때
    int ** graph = new int * [n];
    for (int i = 0; i <= n; ++i)
        graph[i] = new int[m];
    */

    // 정적으로 선언했기 때문에 값들을 전부 -1로 초기화
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            graph[i][j] = -1;
        }
    }

    for(int i=0; i<m; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u][v] = graph[v][u] = 1;
        // 단방향의 경우 graph[u][v] = 1;
        // 가중치가 있는 경우 단방향의 경우 graph[u][v] = 가중치값;
    }
}


리스트(vector를 Linked List처럼 사용)

개념

  • vector: 정점
  • vector의 요소: 연결된 정점
  • 정점의 수만큼 리스트를 생성하고 해당 정점 리스트에다가 연결된 정점들을 추가


방향 그래프

  • 방향 그래프 예시


무방향 그래프

  • 무방향 그래프 예시


코드

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m; // 정점과 간선의 개수를 입력받음

    vector<int> graph[n+1];

    // Visual Studio의 경우
    /* 변수를 통해서 배열을 동적으로 생성할 때
    vector<int> * graph = new vector<int>[n+1];
    */

    for(int i=0; i<m; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        // 단방향의 경우 graph[u].push_back(v);만 작성
        // 가중치가 있는 경우 vector<pair<int,int>> graph[n+1];로 만들거나 구조체를 만들어서 가중치와 함께 저장
        // graph[u].push_back(make_pair(v,w)); u->v 가중치: w
    }
}


참고자료

TWpower Reading time ~1 minute

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);
}


참고자료

TWpower Reading time ~1 minute

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


환경 및 선수조건

  • 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;
		}
	}
}


참고자료

TWpower Reading time ~1 minute

업데이트(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);
}


참고자료

TWpower Reading time ~1 minute

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


환경 및 선수조건

  • 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


참고자료