복세편코

알고리즘을 풀때 그래프를 탐색하는 목적은  모든 정점을 한번씩 탐색한다는 것이다. 

그래서 두가지 그래프 탐색방법이 존재하는데 하나는 DFS (깊이 우선 탐색) 이고 나머지는 BFS(너비 우선 탐색)이다. 

이번포스트는 두가지에 대해 하나씩 설명하고 백준에 있는 간단한 문제를 한번 풀어보려 한다.

○ DFS(깊이 우선 탐색)

깊이 우선 탐색이란 최대한 깊게 나가 그래프를 탐색하는 방법을 말한다.

 다시말해 스택을 이용해 최대한 많이 가고, 더이상 갈 수 없으면 이전 정점으로 돌아가는 방법이다.

이해가 쉽도록 그림을 이용해 설명하겠다.

다음과 같은 그래프가 존재한다고 가정하자  만약 다음 스택에 갈 수 있는 방향이 여러가지라면 가장 작은 값부터 가는것을 원칙으로 하고 설명을 하겠다.

다음과 같이 방문을 하면 check의 값에 1을 넣어 중복해서 방문하지 않게 하기위한 조치를 취해둔다.

이렇게 보기 좋게 정리를 하고 순서대로 정점과 체크 값의 변화를 정리해 보겠다. 

i

1

2

3

4

5

6

Chec

1

1

1

0

0

0

여기까진 순서대로 진행하는데  5 다음에 지나갈 모든 정점이 다 이미 지났던 곳이다. 이럴땐 스택을 pop 해 한칸 뒤로 가고 다른 정점으로 이동한다.

또한 그냥 뒤로 가는 것이기 때문에 check의 값의 변화는 없다. 

새로 갈수 있는 정점이 나왔기에 다시 6번으로 가면된다.

더이상 갈 곳이 없기 때문에 pop을 하면서 새로 갈 수 있는 곳을 찾는다.

스택이 비게 되면 DFS의 탐색은 종료가 된다.

위에 대해 코드를 통해 나타내면 다음과 같다.

void dfs(int x){

    check[x] = true;

//// 인접행렬로 구현

    for(int i=0; i<=n; i++){ // 다음 정점을 찾는 과정

        if a[x][i] == 1 & check[i] == false; // x->i로 가는 간선이 있고 체크 값이 0일때 간선으로 간다는 것이다.

        dfs(i);

    }

// 인접 리스트로 구현

//    a[x] 에는 x 와 연결된 정점의 개수

//    그래서 size를 통해 정점이 있는것만 파악이 가능하다.

    for(int i=0; i<a[x].size(); i++){

        int y = a[x][i];

        if (check[y] == false){

            dfs(y);

        }

    }

}

그래프를 저장하는 방법에는 3가지 방법이 있다.

바로 인접행렬, 인접리스트, 간선리스트이다.

순서대로 각각 비교해 보도록 하겠다.

i) 인접 행렬

V*V 의 2차원 행렬을 만들어 처리하는 방법이다.

A[i][j] 에 대해 설명하면 i 에서 j로 가는 간선이 있으면 w(가중치) 의 값을 대입하고 없으면 0 을 대입한다.

그래프에서 가중치가 따로 나와있지 않는다면 1로 가정하고 처리하면 된다.

양방향 그래프라면 A[i][j]와 A[j][i]의 값이 같은값을 넣어야한다. 따라서 공간을 많이, 중복된 값을 차지한다는 점에서 자주 사용하는 방법은 아니다.

코트를 통해 간단하게 나타내면 아래와 같다.

#include <iostream>

#include <vector>

int a[10][10];

int main(){

    int n, m;

    scanf("%d %d", &n,&m);

    for (int i=0;i<m;i++){

        int u,v;

        scanf("%d %d", &u,&v);

        a[u][v] = a[v][u] = 1;

    }

    return 0;

}

ii) 인접 리스트

#include <iostream>

※ 벡터를 사용할 때 주의해야 할 점

vector<int> a(10)  과 vector<int> a[10] 은 다르다는 것이다. 

vector<int> a(10) 은 1차원 벡터를 의미하고  vector<int> a[10] 은 2차원 백터를 의미한다. 즉  a백터가 10개를 가지고 있다 라는 것이다. 

따라서 헷갈리지 않게 작성하고 싶다면  1차원 벡터는 그대로 vector<int> a(10)  으로 작성하고

                                                          2차원 벡터는vector<vector<int> >a(10)  으로 작성하는것이 좋다.

iii) 간선 리스트

간선리스트에 대해서는 따로 설명하지 않겠다. 그 이유는 세가지 방법중 가장 잘 안쓰는 방법이기 때문이다. 이 간선 리스트를 사용할 때에는 아마 STL을 이용하지 못하는 상황에서만 사용한다. 

문제 

배열에 10개의 값을 입력 받았을 때 최대값, 최소값을 구하고 그 두개를 뺀 평균을 구하라

접근방법

배열을 입력하고 배열처음부터 순서대로 비교하면서 가장 큰값과 가장 작은 값을 구하면 된다.

그리고 10개를 비교하면서 모든 값을 한 변수에 더하고 위에서 구한 최대, 최소값을 각 각 뺀다음  8로 나누면 평균이 나온다.

구현

#include <iostream>

#include <string>

using namespace std;

int i;

int a[10];

int j = 0;

int maxx = 0;

int minn = 110;

int hap = 0;

int main(){

    while(j<10){

        cin >> a[j];

        j++;

    }

    for(i=0; i< 10 ; i++){

        if( a[i] > maxx ){

            maxx = a[i];

        }

        if( a[i] < minn){

            minn = a[i];

        }

        hap +=a[i];

    }

    hap = hap - maxx - minn;

    cout << hap / (i-1) << endl;

    cout << maxx;

    cout << minn;

    return 0;

}

정의

우선 생각이 잘 안날 수도 있으니 약수의 개념부터 설명하겠습니다.

약수 - 어떤 수를 나누어 나머지가 없게 할 수 있는 수를 말한다.

ex) 10의 약수는 1,2,5,10 이다.

알고리즘 문제 분석

1부터 입력받은 수 까지 1씩 증가하면서 입력받은 수로 나눈다. 나누었을때 나머지가 0 이면 그 수가 약수인 것이다.

구현

#include <iostream>

#include <string>

using namespace std;

int main() {

    int a[100];

    int x, mok, nmg, i;

    cin >> x;

    int c = 0 , d = -1;

    while(1) {

        c++;

        if (c<=x){

            mok = x/c;

            nmg = x%c;

            if(nmg ==0) {

                d++;

                a[d] = c;

            }

        }

        else{

            cout << x << " \n";

            for(i = 0; i<=d; i++){

                cout << " " << a[i];

            }

            break;

        }

    }

    return 0;

}

 정의

우선 생각이 잘 안날 수도 있으니 최대공약수와 최소공배수의 개념부터 설명하겠습니다.

최대공약수 - 공통으로 가지고 있는 약수 중 가장 큰수

최대공배수 - 두 수의 공통인 배수 중 가장 작은 수

알고리즘 문제 분석

◎ 최대공약수 구하기

두 수를 입력받고 둘중 큰 수를 작은 수로 나누었을때 나머지가 0이면 큰 수가 바로 최대공약수이다. 

만약 나머지가 0이 아니라면 작은수를 큰수라고 하고 나머지를 작은수라고 두어 나누었을때 0 이 나올때까지 반복해 최대공약수를 구하면 된다.

◎ 최소공배수 구하기

최소공배수는 두 수를 곱하고 최대공약수로 나누면 된다.

구현

#include <iostream>

#include <string>

using namespace std;

int main() {

    int a,b;

    int big, small, mok, nmg;

    int gcm, lcm;

    cin >> a >> b;

    if( a>=b) {

        big = a;

        small = b;

    }else{

        big = b;

        small = a;

    }

    while(1) {

        mok = big / small;

        nmg = big % small;

        if ( nmg == 0 ){

            gcm = small;

            lcm = a * b / gcm;

            cout << "gcm : "<<gcm <<" lcm: " << lcm;

            break;

        }

        big = small;

        small = nmg;

    }

    return 0;

}

소수를 판별하는 방법은 다양하게 존재하고 있습니다. 여기서는 크게 3가지 방법으로 소수를 구하는 방법을 찾아보겠습니다.

i) 임의의 정수를 입력했을때 나누어 떨어지지 않는 경우

임의의수 X에 대해 X를 2부터 X-1로 순서대로 나누어 떨어지는지 검사하면 알 수 있다.

나누어 떨어지는 경우가 나타나면 소수가 아닌 것이다.

#include <iostream>

#include <string>

using namespace std;

int main() {

    int x,i,j;

    cin >> x;  // 판별하기 위한 숫자 입력

    i = x-1;

    j = 2;

    while (1) {

        if (j <= i) {

            if( x % j == 0){

                cout <<" 소수 아니다" << endl;

                break;

            }else {

                j +=1;

            }

        }else {

            cout << "소수이다" << endl;

            break;

        }

    }

    return 0;

}

ii) 임의의 정수를 입력했을때 나누어 떨어지는 경우

임의의수 X에 대해 X를 2부터 X-1로 순서대로 나누어 떨어지는지 검사하면 알 수 있다.

나누어서 처음으로 나누어 떨어졌을 때 X와 같은 값이면 소수이다. 

#include <iostream>

#include <string>

using namespace std;

int main() {

    int x, y;

    cin >> x;

    y = 2;

    while (x % y != 0) {

        y++ ;

    }

    if ( x == y)

    {

        cout << "소수이다\n";

    }else{

        cout << "소수가 아니다.\n";

    }

}

iii) 제곱근을 이용하기

임의의수 X에 대해 X를 2부터 X의 제곱근까지 숫자로 나누었을때 떨어지는지 검사한다.

한번도 나누어 떨어지지 않으면 소수이고, 한번이라도 나누어 떨어지는 경우가 나타나면 소수가 아니다.

버블정렬이란?

버블 정렬은 첫 번째 자료와 두번째 자료를, 두번째 자료와 세 번째 자료를 ... 이런 식으로 마지막-1 번째 자료와 마지막 자료를 비교하면서 교환하여 자료를 정렬하는 것이다.

1회전 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하게되고, 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 끝에서 두번째 자료가 두번째로 큰 값이 된다.

#include <iostream>

using namespace std;

int main() {

    int n, i, j ,tmp;

    int data[10];

    for ( n=0; n<=9; n++ ){

        cin >> data[n];

    }

    for ( i = 1; i <= 9; i++) {

        for ( j = 0; j <= 9-i; j ++) {

            if ( data[j]> data[j+1]) {

                tmp = data[j];

                data[j] = data[j+1];

                data[j+1] = tmp;

            }

        }

    }

    for (int x =0; x<=9;x++) {

        cout << data[x] << " ";

    }

    return 0;

}

심화 -> 중간에 종료하기

특정 회전에서의 자료 교환 여부를 검사하고 더이상 교환이 없을때 완료된 것으로 파악하고 출력하기

#include <iostream>

using namespace std;

int main() {

    int n, i, j ,tmp , sw, cnt;

    int data[10];

    for ( n=0; n<=9; n++ ){

        cin >> data[n];

    }

    cnt = 0;

    for ( i = 1; i <= 9; i++) {

        sw = 0;

        for ( j = 0; j <= 9-i; j ++) {

            if ( data[j]> data[j+1]) {

                tmp = data[j];

                data[j] = data[j+1];

                data[j+1] = tmp;

                cnt++;

                sw = 1;

            }

        }

        if ( sw ==0) {

            break;

        }

    }

    for (int x =0; x<=9;x++) {

        cout << data[x] << " ";

    }

    return 0;

}

선택정렬이란?

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번재에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행하는 것이다.

#include <iostream>

using namespace std;

int main() {

    int m, i, j, k, tmp;

    int data[10];

    for (m = 0; m < 10; m++){

        cin >> data[m];

    }

    for (i = 0; i <= 8; i++){

        for(j = i+1; j <= 9; j++){

            if(data[i]> data[j]){

                tmp = data[i];

                data[i] = data[j];

                data[j] = tmp;

            }

        }

    }

    for( k = 0; k < 10; k++){

        cout << data[k]<< " ";

    }

    return 0;

}