복세편코

런타임 오류가 나지만 결과는 맞는거 같다 곧 수정할 예정

#include <iostream>

#include <list>

using namespace std;





list<int> josephus;



int main() {

    int c,n,k;  // c 테스트케이스  n 총 사람수  k k번째 사람

    

    scanf("%d",&c);

    for(int i=1; i<=c; i++){ // 테스트케이스 만큼 입력받기

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

        

        for(int j=1; j<=n ; j++)

            josephus.push_back(j);  // list 에 인원수만큼 추가

        list<int>::iterator kill =josephus.begin(); // list 맨처음 값 지정 즉 죽는 값

        josephus.erase(kill);  // 맨처음 삭제

        

        

        while (josephus.size() > 2) {  // 크기가 2일때 까지 즉 2명남을때까지

            



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

                kill++;

                if(kill == josephus.end()){

                    kill = josephus.begin();

                    

                }

                

            }

            josephus.erase(kill);

        }



//        값 출력

        josephus.sort();

        cout << josephus.front() << " " << josephus.back();



    }

}

이전글을 이어 이번에는 BFS에 대해 설명하도록 하겠다. 

이전글은 DFS에 대한 설명이며 http://free-from-anxiety.tistory.com/8 를 통해 볼 수있다. 

○ BFS(너비 우선 탐색)

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

  이것은 큐를 통해 구현을 하고 DFS보다 더 자주 쓰인다.

DFS보다 더 자주 쓰이는 이유가  모든 가중치가 1 이라면 최단거리를 탐색하는 방법을 찾는데 사용된다 라는 점이다.

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

더이상 정점 1에서 갈 곳이 없기에 큐의 앞의 값을 빼면서 정점을 이동한다.  큐의 맨 앞의 값이 정점이 된다.

큐가 비게 되면 DFS의 탐색이 끝난 것이다.

이를 코드를 통해 나타내면 다음과 같다.

bool check[1001];

vector<int>a[1001];

void bfs(int x){

queue<int> q;

//    시작점을 큐에 넣는데 체크값도 true로 넣어준다.

check[1] = true;

    q.push(1);

    while (!q.empty()) {

        int x = q.front();  //제일 앞에 있는 x 의 값을 빼 다음 정점을 구한다.

        q.pop();

        // 인접행렬

        for(int i=1;i<=n; i++){

            if(a[x][i] ==1 && check[i] ==false){

                check[i] = true;

                q.push(i);

            }

        }

        // 인접 리스트

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

            int y = a[x][i];

            if(check[y] ==false){

                check[y] = true;

                q.push(y);

            }

        }

    }

다음 포스트에는 [1206] 백준 연습문제를 풀어보도록 하겠다.

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

그래서 두가지 그래프 탐색방법이 존재하는데 하나는 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의 제곱근까지 숫자로 나누었을때 떨어지는지 검사한다.

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