코영방

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=224&sca=10d0

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 자가진단1
20 이하의 자연수 N을 입력받아 재귀함수를 이용해서 문자열 “recursive”를 N번 출력하는 프로그램을 작성하시오.
입력 예
3
출력 예
recursive
recursive
recursive
*/

void re(int p,int n)
{
    printf("recursive\n");
    if(p==n)return;
    p++;
    re(p,n);
}

int main()
{
    int n;
    scanf("%d",&n);
    re(1,n);
    return 0;
}

아래와 같이 수정했을때 , 출력 결과가 어떻게 나올지 생각해보면, 재귀함수 이해에 도움이 많이 될것 같네요.^^

#include <bits/stdc++.h>
using namespace std;
/*
함수3 - 자가진단1
20 이하의 자연수 N을 입력받아 재귀함수를 이용해서 문자열 “recursive”를 N번 출력하는 프로그램을 작성하시오.
입력 예
3
출력 예
recursive
recursive
recursive
*/

void re(int p,int n)
{
    printf("recursive %d   %d  \n", p, n);
    if(p==n)return;
    p++;
    re(p,n);
    printf("xxx %d   %d\n", p, n);
}

int main()
{
    int n;
    scanf("%d",&n);
    re(1,n);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=81&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가7
원주율을 3.141592로 매크로 상수로 정의하고 원의
넓이를 구하는 매크로 함수를 작성하여 반지름을 입력받아
원의 넓이를 출력하는 프로그램을 작성하시오. (소수 넷째자리에서 반올림)
입력 예
radius : 1.5
출력 예
area = 7.069
*/
#define PI 3.141592
#define AREA(r) r*r*PI
float f(float r)
{
    float s;
    //s=r*r*PI;
    s=AREA(r);
    return s;
}

int main()
{
    float r,k;
    printf("radius :");
    scanf("%f",&r);
    k=f(r);
    printf("area = %.3f",k);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=80&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가6
자료의 개수 7을 매크로 상수로 정의하여 자료의 개수만큼 정수를 입력받아 입력받은
순서대로 앞에서부터 마지막까지 가면서 바로 뒤의 숫자와 비교하여 크면 교환한다.
이러한 작업을 세 번 반복한 후 그 결과를 하나의 행에 공백으로 구분하여 출력하는 프로그램을 작성하시오.
입력 예
15 20 41 8 26 33 19
출력 예
8 15 20 19 26 33 41
*/
#define CNT 7
void f(int a[])
{
    int i,j;
    for(i=1; i<=3; i++){
        for(j=1; j<CNT; j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
            }
        }
    }
}

int main()
{
    int i,a[1004];
    for(i=1; i<=CNT; i++){
        scanf("%d",&a[i]);
    }
    f(a);
    for(i=1; i<=CNT; i++){
        printf("%d ",a[i]);
    }
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=79&sca=10c0

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 형성평가5
세 개의 실수를 입력받아 합계와 평균을 구하여 평균을 반올림한 정수를 출력하고,
다음은 입력받은 수를 각각 먼저 반올림한 후 합계와 평균을 구하여 평균을 반올림한
한 결과를 출력하는 프로그램을 작성하시오.
입력 예
153.74 34.59 109.5
출력 예
99
100
*/

int f(float a,float b,float c)
{
    float x;
    x=(a+b+c)/3;
    x=round(x);
    return x;
}
int f2(float a,float b,float c)
{
     float y;
     y=(round(a)+round(b)+round(c))/3;
     y=round;
     return y;
}
int main()
{
    int k,k2;
    float a,b,c;
    scanf("%f %f %f",&a,&b,&c);
    k=f(a,b,c);
    k2=f2(a,b,c);
    printf("%d %d",k,k2);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=78&sca=10c0

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가4
정수 n을 입력받아 2n의 값을 출력하는 프로그램을 작성하시오. (1 ≤ n ≤ 20)
입력 예
10
출력 예
1024
*/

int power(int a)
{
    int k=1,i;
    for(i=1; i<=a; i++){
        k=k*2;
    }
    return k;
}


int main()
{
    int a,f;
    scanf("%d",&a);
    f=power(a);
    printf("%d",f);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가4
정수 n을 입력받아 2n의 값을 출력하는 프로그램을 작성하시오. (1 ≤ n ≤ 20)
입력 예
10
출력 예
1024
*/

int main()
{
    int a,f;
    scanf("%d",&a);
    f=pow(2,a);
    printf("%d",f);
    return 0;
}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=77&sca=10c0

#include <bits/stdc++.h>
using namespace std;

/*
함수2 - 형성평가3
5개의 정수를 입력받아 각 정수의 절대값의 합을 출력하는 프로그램을 작성하시오.
입력 예
35 -20 10 0 55
출력 예
120
*/

void f(int a[])
{
    int i,c=0;
    for(i=1; i<=5; i++){
        c=c+abs(a[i]);
    }
    printf("%d",c);
}

int main()
{
    int i,a[1004];
    for(i=1; i<=5; i++){
        scanf("%d",&a[i]);
    }
    f(a);
    return 0;
}

https://www.acmicpc.net/problem/14002

아래 코드를 먼저 참고바랍니다.

https://coding-gongboo.tistory.com/38?category=829643

11053번 문제는 수열의 길이만 구하면 되지만, 14002문제는 수열을 표현해 주어야 한다.

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[1000]={0,},l[1000]={0,},j,ma=-1,k[1000]={0,},m;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        k[i]=i;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                //l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
                if(l[i] < l[j]+1)
                {
                    l[i] = l[j]+1;
                    k[i]=j;
                }
            }
        }
       // ma=ma>l[i]?ma:l[i];
        if(ma<l[i]){
            ma=l[i];
            m=i;
        }
    }
    printf("%d\n",ma);
    l[1] = a[m];
    for(i=2;i<=ma;i++)
    {
        l[i]=a[k[m]];
        m = k[m];
    }
    for(i=ma;i>0;i--)
        printf("%d ",l[i]);
    return 0;
}

https://www.acmicpc.net/problem/11053

이문제는 LIS(Longest Increasing Subsequence) 라는 유명한 문제입니다.

아래 코드는 다이내믹 방식으로 소스코드를 작성했습니다.

참고하시구요. 질문이나 수정할 부분있으면 알려주세요.^^

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[100000]={0,},l[100000]={0,},j,ma=-1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
                l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
        }
        ma=ma>l[i]?ma:l[i];
    }
    printf("%d",ma);
    return 0;
}

문제는 아래 첨부 파일 참고하세요.

등수의 범위를 알고자 하는 학생(x)을 기준으로, 

- 확실히 등수가 높은 학생 리스트 (아래 코드에서 up vector, x학생 포함)

- 확실히 등수가 낮은 학생 리스트 (아래 코드에서 down vector, x학생 포함)

아래 소스코드는 up/down vector에 학생 번호가 중복되어 있으면 삭제해서, unique(유일하게) 하는 코드 입니다.

    sort(up.begin(), up.end());
    up.erase(unique(up.begin(), up.end()), up.end());

    sort(down.begin(), down.end());
    down.erase(unique(down.begin(), down.end()), down.end());

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x;
    vector<int> up;
    vector<int> down;

    scanf_s("%d %d %d", &n, &m, &x);
    int input[1000000][2];

    for (int i = 0; i < m; i++) {
        scanf_s("%d %d", &input[i][0], &input[i][1]);
    }

    up.push_back(x);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < up.size(); j++) {
            if (input[i][1] == up[j]) {
                up.push_back(input[i][0]);
            }
        }
    }
    down.push_back(x);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < down.size(); j++) {
            if (input[i][0] == down[j]) {
                down.push_back(input[i][1]);
            }
        }
    }

    sort(up.begin(), up.end());
    up.erase(unique(up.begin(), up.end()), up.end());

    sort(down.begin(), down.end());
    down.erase(unique(down.begin(), down.end()), down.end());


    printf("%d %d", up.size(), n - down.size()+1);
    return 0;
}

문제는 아래 첨부 파일은 참고하세요.^^

2019년 정올 2차 - 초등 1번 문제

#include<bits/stdc++.h>
using namespace std;

int main() {
    int i,m,n,l,c1,k=0;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        m=i;
        for(l=1000000; l>=1; l/=10){
            c1=m/l;
            m=m-c1*l;
            if(c1==3 || c1==6 || c1==9){
                printf("%d\n", i);
                k++;
                c1=0;
            }

        }
    }
    printf("%d",k);
    return 0;
}

2019 정올 2차 초등 1번 - 풀이방법 2

#include<bits/stdc++.h>
using namespace std;

int main() {
    int i,m,n,l,c1,k=0;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        m=i;
        while(m != 0){
            int mod = m%10;
            if(mod==3 || mod==6 || mod==9)k++;
            m=m/10;
        }
    }
    printf("%d",k);
    return 0;
}

https://www.acmicpc.net/problem/2529

문제의 조건이 순서만 변경할 수 있을 때는 순열을 사용하면 됩니다.

부등호 앞에 그리고 뒤에 한 자리 숫자를 나와서 모든 부등호의 관계를 만족시키려고 합니다

하지만 이때 선택한 수가 같으면 안 됨.

문제의 가장 중요한 조건 중에 하나는 선택할 숫자는 한자리숫자 이고 선택한 숫자가 같은면 안된다.

즉, 순서 문제가 된다.

예를 들어, 0부터 9까지 소중해서 일정 4개를 골랐다고 해봅시다. 그럼 9,8,7,6 을 선택해서, 중복없이 순서대로 나열하고, 부등호가 성립되는지 확인하면된다.

<전체 경우의 수>

10개의 수중에 K+1개를 고른다 = 2^(k+1)  --> 필요없음.

이 K+1개의 수에 대해서 순서를 정한다. = !(K+1)

부등호가 성립하는 검사 = K+1

결론 : 2^10 * 10! * 10 = 1024 * 3628800*10 (OMG)

자~!! 시간복잡도를 줄여 봅시다.

가장큰수와 가장작은수를 찾는 것임으로, K+1이 4개라면,

큰수는 9,8,7,6 작은수는 0,1,2,3 을 선택하면 된다.

즉, 위 시간복잡도에서 2^(K+1)이 없어지게 된다.

#include <bits/stdc++.h>
using namespace std;
bool check(vector<int>& perm, vector<char>& a);

int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    vector<int> min(k + 1);
    vector<int> max(k + 1);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= k; i++) {
        min[i] = i;
        max[i] = 9 - i;
    }
    do {
        if (check(min, a)) {
            break;
        }
    } while (next_permutation(min.begin(), min.end()));
    do {
        if (check(max, a)) {
            break;
        }
    } while (prev_permutation(max.begin(), max.end()));
    for (int i = 0; i < max.size(); i++) {
        cout << max[i];
    }
    cout << '\n';
    for (int i = 0; i < min.size(); i++) {
        cout << min[i];
    }
    cout << '\n';
    return 0;
}

bool check(vector<int>& perm, vector<char>& a) {
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '<' && perm[i] > perm[i + 1]) {
            return false;
        }
        if (a[i] == '>' && perm[i] < perm[i + 1]) {
            return false;
        }
    }
    return true;
}

https://www.acmicpc.net/problem/1697

BFS를 사용해서 쉽게풀수 있는 문제다.

BFS는 아래그림과 같이 그래프 순회방법중의 하나이다.

특히, BFS는 간선의 가중치가 모두 동일한 경우, 최단거리와 같은 최소비용 문제를 해결하기에 적합합니다.

아래 그래는 Graph의 표현 방법과 순회에 대해서 대략적으로 요약한 것이니 참고하시기 바랍니다.

인접리스트의 경우 실제 리스트를 사용하기 보다는 보통 vector를 사용해서 해결하는 경우 많으니 참고하세요.

아래 BFS의 슈도코드라고 할까요? 대략적인 알고리즘을 확인 하실수 있겠습니다.

자~!! 이제 본 숨바꼭질 문제의 풀이 방법입니다. 아래 그림을 통해 찬찬히 고민해보시기 바랍니다.

수빈이의 위치 X에서 1초후에 이동할 수 있는 곳은 X-1, X+1, X*2 입니다. 어떤 이동방법을 선택하더라도 1초가 걸리니까, 이것은 모든 간선의 가중치가 1초라고 보면 되겠네요.^^

그리고X-1을 할때는 X-1이 0보다 작으면 중단하면 되겠죠.

X+1, X*2의 경우는 다음 위치가 200,000보다 작거나 같은때만 처리해주면 되겠네요.^^

많은 도움되셨길바라며, 아래 소스코드 참고하세요.^^

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,c[200005]={0,},v[200005]={0,},t;
    queue <int> q;
    scanf("%d %d",&n,&k);
    v[n]=1;
    c[n]=0;
    q.push(n);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t-1 >= 0 && v[t-1]==0){
            q.push(t-1);
            c[t-1]=c[t]+1;
            v[t-1] = 1;
        }
        if(t+1 < 200000 && v[t+1]==0){
            q.push(t+1);
            c[t+1]=c[t]+1;
            v[t+1] = 1;
        }
         if(t*2 < 200000 && v[t*2]==0){
            q.push(t*2);
            c[t*2]=c[t]+1;
             v[t*2]=1;
        }
        //v[t-1]=v[t+1]=v[t*2]=1;
    }
    printf("%d",c[k]);
    return 0;
}

https://www.acmicpc.net/problem/11727

전형적인 다이내믹 (동적계획법)문제다.

점화식은 아래 스케치를 참고하세요.^^

점화식 : K(n) = K(n-1) + 2*K(n-2)

<Top-Down - 재귀함수 사용 방법>

#include<bits/stdc++.h>
using namespace std;

int d[1001];

int tile(int n)
{
    if(n < 2) return 1;
    if(d[n] > 0) return d[n];
    
    d[n] = (tile(n-1) + tile(n-2) + tile(n-2))%10007;
    return d[n];
}
int main() {

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

    printf("%d\n",tile(n));
    return 0;
}

<Bottom-Up>

#include<stdio.h>
int k[1004];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=1; i<=1004; i++)k[i]=0;
	k[1]=1;
	k[2]=3;
	for(i=3; i<=n; i++){
        k[i]=k[i-1]+k[i-2]*2;
	}
	printf("%d",k[n]%10007);
	return 0;
}

https://www.acmicpc.net/problem/10818

최대값, 최솟값을 구할때는 해당 문제에서 입력가능한 범위를 확인해야 한다.

입력 범위보다 작은 값은 최대값에 해당하는 변수의 초기값으로 사용하고,

입렵 범위보다 큰값을 최솟값에 사용할 변수의 초기값으로 사용해야 한다.

#include<stdio.h>

int main()
{
    int max=-1000001,min=1000001,n,k;

    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&k);
        if(k>max)
        {
            max=k;
        }
        if(k<min)
        {
            min=k;
        }
    }
    printf("%d %d",min,max);
    return 0;

}

https://www.acmicpc.net/problem/11047

이번 문제의 조건 중에 가장 중요한 부분은 아래 내용이다.

아래 조건이 있기 때문에 그리디 알고리즘이 적용가능하다.

i ≥ 2인 경우에 Ai는 Ai-1의 배수

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    int n, k;
    int in[10];

    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> in[i];
    }

    int cnt = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        while (k / in[i])
        {
            cnt += k / in[i];
            k = k % in[i];
        }
    }

    printf("%d", cnt);

    return 0;
}

https://www.youtube.com/watch?v=f7KSfjv4Oq0

쥐, 개, 코끼리가 빌딩에서 떨어지면 어떻게 될까요?

먼저 쥐는 바닥에 떨어져서 살아요. 왜냐하면 쥐안에 피, 근육, 뼈가 많이 없어서 바람이 쥐를 떠받쳐주기 때문이예요.

그리고 개는 바닥에 떨어져서 뼈를 다 부러트리고 죽어요.

마지막으로 코끼리는 바닥에 떨어져서 폭탄처럼 터져서 죽어요.

왜냐하면 코끼리는 무거워서 바람이 떠받쳐주지 못해서, 쥐랑 개보다 더 빨리 떨어져요.

so first let`s start with

https://www.acmicpc.net/problem/3344

N-Queen문제 생각보다 어렵죠? 아마도 N-Queen문제에서 막혀서 찾아오셨다면, 아마도 백트랙킹 / 재귀함수에 대해서 아주 조금 이해가 힘드셔서 오셨을것 같네요.^^ 아래 코드보시면서 도움 되시기 바랍니다.

각 행을 한개씩 내려가면서 Queen을 놓을 곳을 찾아가면 될것 같다.

첫번째 행의 어느 열에 Queen을 위치시키면, 그 열과 대각선 방향을 더이상 Queen을 놓을수 없음을 표시해야 한다.

bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인
위 코드는 아래 그림을 보고 이해할 수 있길 바랍니다. 대각선의 각 cell의 행값 + 열값은 unique하다는 걸 이용해서,

그 unique한 값을 배열의 index로 사용해서, 그 대각선에 이미 Queen이 위치해 있음을 판단하면 됩니다.

bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인

아래 그림은 행-열을 한 값을 표시하고 있다. 음수가 발생하니, 모든 값들에 N을 더하면,

1,2,3,4,5,6,7 로 unique한 값을 만들수 있고, 이것을 배열의 index로 이용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
bool a[15][15];
int n;
bool check_col[15]; //이미 그 열에 queen이 있는지 확인
bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인
bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인

void check_onoff(int row, int col, bool onoff)
{
    check_right_up[row + col] = onoff;
    check_right_down[row - col + n] = onoff;
    check_col[col] = onoff;
    a[row][col] = onoff;
}
bool check(int row, int col) {
    // 같은 열 확인
    if (check_col[col]) {
        return false;
    }
    // 오른쪽 위방향 대각선 확인 (왼쪽 아래도^^)
    if (check_right_up[row + col]) {
        return false;
    }
    // 오른쪽 아래 방향 대각선 확인 (왼쪽 위도^^)
    if (check_right_down[row - col + n]) {
        return false;
    }
    return true;
}

int N_Queen(int row) {
    if (row == n) {
        return 1;
    }
    int cnt = 0;
    for (int col = 0; col < n; col++) {
        if (check(row, col)) { //이 row, col위치에 놓을수 있을지 확인
            check_onoff(row, col, true);  //놓을 수 있으니까, 그 위치 관련해서 놓았다는 표시를 함
            cnt += N_Queen(row + 1);  //다음 행에 queen을 놓으로 감.
            check_onoff(row, col, false); //row, col 기준으로 확인해보 후 임으로, 다시 해제함.
        }
    }
    return cnt;
}
int main() {
    cin >> n;
    cout << N_Queen(0) << '\n';
    return 0;
}

https://www.acmicpc.net/problem/1793

타일링 문제는 아래그림과 같이, N=1이면 1가지, N=2이면 2가지, N=3이면 3가지, N=4이면 5가지 경우가 있다.

아래 그림에 점선으로 표시된 부분을 자세히 보면,

점화식은 D(n)은 N*2 타일은 2*1, 1*2타일로 채울수 있는 방법의 수로 정의 할 수 있으며,

D(n) = D(n-1) + D(n-2) 가된다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int i,n;
    unsigned long x[1008];
    scanf("%d", &n);
    x[1] = 1;
    x[2] = 2;
    for(i=3;i<=n;i++)
    {
        x[i]=x[i-1]+x[i-2];
        x[i] =x[i]%10007;
    }
    printf("%d",x[n]);
    return 0;
}

https://www.acmicpc.net/problem/1260

1. 단계 : 시작 정점을 방문했다고 표시하고, Queue에 push

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.emplace()){
        
    }
}

2. 단계 
시작 정점을 방문했다고 표시하고, Queue에 push
Queue가 빌때까지 반복하면서, queue의 front값을 받고, pop함

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
    }
}

3. 단계
시작 정점을 방문했다고 표시하고, Queue에 push
Queue가 빌때까지 반복하면서, queue의 front값을 받고, pop함

queue의 front 정점(current)을 대상으로 연결된 정점(next)들을 찾음
next중에 방문하지 않은 정점이면, 방문 표시하고 queue에 push
이것을 queue가 빌때까지 반복

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for(int i=0; i<vxy[current].size(); i++){
            int next=vxy[current][i];
            if(checked[next] == 0){
                q.push(next);
                checked[next]=1;
            }
        }
    }
}

전체 소스코드

#include <bits/stdc++.h>
using namespace std;
int checked[10000];
vector<int>vxy[10000];

void dfs(int start)
{
    checked[start]=1;
    printf("%d ",start);
    for(int i=0; i<vxy[start].size(); i++){
        int next=vxy[start][i];
        if(checked[next] == 0){
            dfs(next);
        }
    }
}

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for(int i=0; i<vxy[current].size(); i++){
            int next=vxy[current][i];
            if(checked[next] == 0){
                q.push(next);
                checked[next]=1;
            }
        }
    }
}

int main() {
    int a,b,c,n,m,i;
    scanf("%d %d %d",&n,&m,&c);
    for(i=1; i<=m; i++){
        scanf("%d %d",&a,&b);
        vxy[a].push_back(b);
        vxy[b].push_back(a);
    }

    for(i=1; i<=n; i++){
        sort(vxy[i].begin(),vxy[i].end());
    }

    dfs(c);
    for(i=0; i<=n; i++)checked[i]=0;
    printf("\n");
    bfs(c);

    return 0;
}

오늘은 색상과 폰트 설정에 대해서 소개한다.

먼저, AppBar의 색상은 backgroundColor 속성을 이용해서 변경하면 된다.

아래 사이트에서 세부 색상 팔레트를 참고해서 값을 정하면 된다.

https://material.io/design/color/the-color-system.html#tools-for-picking-colors

또는 아래 그림과 같이, 빨간색 계열의 경우, "Colors.r"까지 입력하고, Ctrl + Q를 누르면 아래 그림과 같이 세부 색상 표를 제공해준다.

AppBar의 색상은 backgroundColor 속성 변경의 소스코드와 결과는 아래와 같다.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Scaffold(
    appBar: AppBar(
      title: Text('코딩 공부방'),
      centerTitle: true,
      backgroundColor: Colors.red[600],
    ),
    body: Center(
      child : Text("Hello 코딩 방"),
    ),
    floatingActionButton: FloatingActionButton(
      child : Text('click'),
    ),
  ),
));

이제 FloatingActionButton의 색상과 중간에 Text의 색상 및 폰트를 변경해보자.

Text의 색상 및 폰트는 style 속성에 TextStyle 위젯의 설정을 통해 변경할 수 있다.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Scaffold(
    appBar: AppBar(
      title: Text('코딩 공부방'),
      centerTitle: true,
      backgroundColor: Colors.red[600],
    ),
    body: Center(
      child : Text(
          "Hello 코딩 방",
          style: TextStyle(
            fontSize: 20.0,
            fontWeight: FontWeight.bold,
            letterSpacing: 4.0,
            color: Colors.grey[600],
        ),
      ),
    ),
    floatingActionButton: FloatingActionButton(
      child : Text('click'),
      backgroundColor: Colors.red[600],
    ),
  ),
));

위 소스코드를 보면, Text의 인자 중 첫 번째 인자는 "??" 형태로 직접 인자 값을 주고, 두 번째 인자의 경우 style : 후에 인자를 기입한 이유는 뭘까?

Text위에 마우스 커서를 위치시키고 Ctrl + q를 누르면 아래와 같이 설명 창이 뜬다. 

아래 그림의 노란색 노무의 경우 "{}"로 묶여 있지 않다. 이경우는 직접 인자 값을 주면 되고, 필수 매개변수이다.

하지만 "{}" 안에 있는 옵션 인자들의 경우 인자 전달을 해도 되고 안 해도 됨으로, 한다면 꼭 "style :" 과 같이 현재 어느 인자에 대해 설정한다는 것을 명확히 해주어야 한다.

그리고 새로운 폰트를 추가하고 싶다면, 아래 구글폰트에서 다운받아서 해당 flutter 프로젝트에 포함 시키면 된다.

https://fonts.google.com/

flutter 프로젝트에 font는 추가하는 과정은 아래와 같다.

1. 구글폰트에서 폰트 검색 및 다운로드

2. 프로젝트에 오른마우스 클릭 -> NEW -> Directory 선택

3. fonts 폴더 생성

4. 다운로드한 ttf파일을 fonts 폴더에 드래그 드롭한다.

5. 이제 폰트를 사용할 준비가 되었다. pubspec.yaml 파일을 연다.

그리고 아래 fonts 관련 코드를 찾는다. Ctrl + / 를 누르면 주석이 지워진다.

6. 아래와 같이 새로 추가한 폰트의 이름으로 수정한다.

7. pubspec.yaml을 저장하고, main.dart로 가면 아래 같이 pubspec.yaml이 변경되었다는 표시가 뜨고, "Get Dependencies"를 눌러서 반영해준다.

8. fontFamily 속성을 추가해주고, 다시 실행시켜보면 새로운 폰트가 반영된 것을 볼 수 있다.

https://www.youtube.com/watch?v=9P6rdqiybaw

이거 알아요? 블랙홀은 중력이 완전완전 쌔요. 그래서 누가 거기 안에 들어가면 거기 안에서 죽어요.그리고 밖으로 나갈 수도 없어요.

웜홀 중간에 블랙홀이 있어요. 만약에 어떤 생명체가 웜홀 안에 있는 블랙홀에 들어가면, 죽어서 블랙홀 밖으로 나와요. 그리고 다른 우주로 들어가요.

do you know that black holes have lots and lots of gravity.So if anything gets sucked in they would probly die and also they can never get out of the black hole.

chapter two: how to get out of a black hole. The only way to get out of a black hole is you have go in a black hole that is in a wormhole because remember wormholes has two sides so you first go in the black side of the worm hole and next you come out in the white side of the wormhole.So that is the end of my story so bye bye! 

https://www.acmicpc.net/problem/15652

이번문제는 N과 M (2)와 유사하다. 단, 중복 가능하다. 

아래 문제 조건과 같이 앞의 수가 다음수보다 작거나 같다은 조건을 만족하면 된다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

따라서 N과 M (2)에서 재귀함수의 첫번째 인자만, i+1이 아니랑 i를 주면 된다.

즉, i값을 포함해서 다음 수를 정해나가는 형태이다. 왜냐? 중복을 허용하기 때문이다.

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM4(int, int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM4(1, n, m);
    return 0;
}
void NM4(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = s; i <= n; i++) {
        nm.push_back(i);
        NM4(i, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
        nm.pop_back();
    }
}

https://www.acmicpc.net/problem/15651

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. (중복가능)

N = 4, M = 2인 경우 아래와 같이 16(4*4) 개의 경우가 발생한다.

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

내 생각에는 N과 M(1)보다 풀이에 접근하기 더 쉬운 문제라고 생각한다. 내기준으로는 "N과 M(0)" 이 맞을듯.^^

#include <bits/stdc++.h>
using namespace std;
vector <int> res;
void NM3(int n, int m) {
    if (res.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        res.push_back(i);
        NM3(n, m);
        res.pop_back();
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    NM3(n, m);
    return 0;
}

본글은 아래와 같이 Flutter SDK와 Android Studio / toolchain이 먼저 설치되야 한다.

그리고 Android Studio에 Flutter 와 Dart plugin을 설치하고,

AVD 를 추가하고, Flutter 프로젝트를 생성해서 아래와 같이 "Flutter Demo : Home Page"까지는 실행되었다는 전제고 글을 쓰고자 한다.

기본 예제 소스를 모두 삭제하고 아래와 같이 androi MaterialApp의 home property에 text 위젯을 추가해보자.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Text('hey guy!!')
));

Flutter에는 모든 위젯의 이름은 첫자와 각 단어를 대문자로 표기한다.

그리고 home같이 각 property는 "," 로 구분한다.

이제 Scaffold와 AppBar 위젯을 추가해보자.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Scaffold(
    appBar: AppBar(
      title: Text('코딩 공부방'),
    ),
  ),
));

다음은 AppBar 위젯의 centerTitle 속성을 이용해 Text는 중앙정렬 시켜보자.

또한 Scaffold의 두번째 속성으로 body에 Text위젯으로 글을 추가해보자.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Scaffold(
    appBar: AppBar(
      title: Text('코딩 공부방'),
      centerTitle: true,
    ),
    body: Text('Hellow Coding gongboobang')
  ),
));

Flutter 샘플프로젝트와 같이 Scaffold 의 body에 들어는 Text는 중앙에 위치시키도록 수정해보자.

이를 위해 Center 위젯을 아래와 같이 사용하면 된다.

그리고 샘플프로젝트에서 본 FloatingActionButton 위젯도 추가해보자.

import 'package:flutter/material.dart';

void main() => runApp(MaterialApp(
  home : Scaffold(
    appBar: AppBar(
      title: Text('코딩 공부방'),
      centerTitle: true,
    ),
    body: Center(
      child : Text("Hello 코딩 방"),
    ),
    floatingActionButton: FloatingActionButton(
      child : Text('click'),
    ),
  ),
));

Scaffold 위젯은 아주많이 사용됨으로 아래 링크에서 좀더 자세한 사항을 확인 하는것을 추천한다.

https://api.flutter.dev/flutter/material/Scaffold-class.html

오늘은 넘버 풋볼을 했다. 넘버 풋볼은 사람이 많이 있어야해. 사람이 짝수로 있어어야해.

이팀이랑 저팀은 선수 명수가 같아야 한다.

Today I did number football. we need a lot of people to play number football.

we have to have even number to play number football.

It is have to be equal to play this game.

먼저 일어났고, 옷 입고, 1층 내려가서 아침밥 먹고 그리고 볼트론 넷 프릭스를 봤다.

학교 가는 시간을 알려주는 알람이 울렸다. 그래서 나는 엄마 차를 타고 학교로 갔다.

오늘은 학교에서 나의 마음이 어떤지 친구들에게 설명하는 시간을 가졌다.

나는 그 시간에 행복한 마음에 대해서 친구들에게 이야기해주었다.

first I woke up and went downstair then I ate breakfast next I watched neflix voltron.

then suddenly the alarm went off it was the time to go to school.

At school I did a thing called check in. check in is a thing that you share your feelings.

Then at that time I choosed "happy" because in the last day of december i`m going to South korea!

https://www.acmicpc.net/problem/1008

float 형의 경우 대략 10^-7 정도의 오차를 갖으며,

double 형의 경우 대략 10^-15 정도의 오차를 갖습니다. 그래서 10-9 이하의 오차를 가지려면 doule형을 사용해야 한다.

https://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=329881326&qb=ZG91YmxlIGZsb2F0IOyYpOywqA==&enc=utf8§ion=kin&rank=1&search_sort=0&spq=0

#include <bits/stdc++.h>
using namespace std;

int main() {
	double A, B;
	scanf("%lf %lf", &A, &B);
	printf("%.9lf\n", A / B);
	return 0;
}

https://www.acmicpc.net/problem/10172

특수문자 출력 연습하기~!!!

#include <bits/stdc++.h>
using namespace std;

int main() {

	printf("|\\_/|\n");
	printf("|q p|   /}\n");
	printf("( 0 )\"\"\"\\\n");
	printf("|\"\^\"`    |\n");
	printf("||_/=\\\\__|\n");

	return 0;

}

https://www.acmicpc.net/problem/2667

플러드 필 문제중 한개이다.

연결요소 문제와 유사하게 방문하지 않은 정점을 찾아서 dfs / bfs 순회를 해주면 된다.

여기서 정점의 정보는 [행,열]이 된다. 즉, (x,y)값을 한개의 정점으로 생각하면 됨.

그리고 이런 문제에서는 인접 정점을 찾는 방법은 아래와 같이 한개 정점 (x,y)에서 위/아래/좌/우로 이동을 위해 변경되야할 좌표값을 아래 배열과 같이 넣어두고 for문을 돌리면 간단하게 구현 할 수 있다.

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

연속된 숫자중 1개 자리씩만 입력을 받고 싶을경우 아래 코드를 이용하면 된다.

scanf("%1d", &input[i][j]);

아래 소스코드는 bfs를 사용해서 해결하였다.

#include <bits/stdc++.h>
using namespace std;

int input[30][30];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n;
int res[25 * 25];
#define Dangi_Start_Num 2  //플러드 필에 사용되는 단지 시작 번호
void bfs(int x, int y, int cnt) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    input[x][y] = cnt;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {  //input 배열의 범위밖을 참조하지 않도록 하기 위해
                if (input[nx][ny] == 1) {
                    q.push(make_pair(nx, ny));
                    input[nx][ny] = cnt;
                }
            }
        }
    }
}
int main() {

    //지도 정보 입력 받기
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &input[i][j]);
        }
    }
    //플러드 필
    int cnt = Dangi_Start_Num;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == 1) {
                bfs(i, j, cnt++);
            }
        }
    }
    //단지 개수 출력
    printf("%d\n", cnt - Dangi_Start_Num);
    
    //플러드 필된 값(즉, 단지번호) 별로 몇개가 있는지 개수를 셈
    //그 개수를 res배열에 index는 단지배열이고, 그곳에 그 단지의 개수를 저장해둠.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] != 0)
                res[input[i][j] - Dangi_Start_Num] += 1;
        }
    }
    //res를 오른 차순으로 정렬함.
    sort(res, res + cnt - Dangi_Start_Num);
    //단지별 개수를 오름차순으로 출력함.
    for (int i = 0; i < cnt - Dangi_Start_Num; i++) {
        printf("%d\n", res[i]);
    }

    return 0;
}

https://www.acmicpc.net/problem/11724

연결 요소의 개수의 경우, DFS나 BFS를 공부를 공부한 후라면 간단하게 해결 가능하다.

모든 정점을 대상으로 방문한 적이 없는 정점이 있으면 그 정점을 기준으로 DFS 또는 BFS순회를 통해 방문했다는 체크를 해둔다. 그 후에도 아직 방문하지 않은 정점이 있다면 또 DFS나 BFS를 통해 순회하면서 방문했다는 체크를 하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, l;
vector <int> a[1005];
int visited[1005] = { 0, };

void dfs_l(int s) {
    int i;
    visited[s]++;
    for (i = 0; i < a[s].size(); i++){
        if (visited[a[s][i]] == 0){
            dfs_l(a[s][i]);
        }
    }

}

int main()
{
    int i, n1, n2, cnt = 0;
    scanf("%d %d", &n, &l);
    //간선 정보를 입력 받아 그래프 만들기
    for (i = 0; i < l; i++){
        scanf("%d %d", &n1, &n2);
        a[n1].push_back(n2);
        a[n2].push_back(n1);
    }
    
    //DFS 순회시에 인접 정점중에 정점번호가 작은 값부터 순회하기 위해 정렬
    //이번 문제에서는 굳이 없어도 됨.
    for (int i = 0; i < n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    //방문하지 않은 정점을 발견하면 DFS순회함.
    //DFS가 호출되는 횟수가 연결요소의 개수가 됨.
    for (int i = 1; i <= n; i++){
        if (visited[i] == 0){
            dfs_l(i);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}