코영방

4949번: 균형잡힌 세상 (acmicpc.net)

#include <bits/stdc++.h>
using namespace std;
//균형잡힌 세상
int main() {
    string str;

    getline(cin, str);
    while (str != ".") {
        stack<char> bracket;
        int len = str.size();
        for (int i=0; i<len; i++) {
            if (str[i] == '(' || str[i] == '[') {
                bracket.push(str[i]);
            }
            else if (str[i] == ')' && !bracket.empty() && bracket.top() == '(') {
                bracket.pop();
            }
            else if (str[i] == ']' && !bracket.empty() && bracket.top() == '[') {
                bracket.pop();
            }
            else if (str[i] == ')' || str[i] == ']') {
                bracket.push('a');
                break;
            }
        }
        if (bracket.empty()) {
            printf("yes\n");
        }
        else {
            printf("no\n");
        }
        getline(cin, str);
    }
}

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

#include <bits/stdc++.h>
using namespace std;
//최소공배수
int gcd(int a, int b) {
	while (b != 0) {
		int last = a % b;
		a = b;
		b = last;
	}
	return a;
}

int main() {
	int t, a, b;
	cin >> t;
	while (t--) {
		cin >> a >> b;
		int g = gcd(a, b);
		printf("%d\n", (a*b)/g);
	}
}

JW

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

int main() {
	queue<pair<int, int>> q;
	int n, m;
	int arr[1002][1002] = {0,}, visited[1002][1002] = {0,};
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		for (int j=1; j<=n; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i=1; i<=m; i++) {
		for (int j=1; j<=n; j++) {
			if (arr[i][j] == 1) {
				q.push({i, j});
				visited[i][j] = 1;
			}
			else if (arr[i][j] == -1) {
				visited[i][j] = 1;
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x-1 != 0 && arr[x-1][y] == 0 && visited[x-1][y] == 0) {
			q.push({x-1, y});
			arr[x-1][y] = arr[x][y] + 1;
			visited[x-1][y] = 1;
		}
		if (x+1 != m+1 && arr[x+1][y] == 0 && visited[x+1][y] == 0) {
			q.push({x+1, y});
			arr[x+1][y] = arr[x][y] + 1;
			visited[x+1][y] = 1;
		}
		if (y-1 != 0 && arr[x][y-1] == 0 && visited[x][y-1] == 0) {
			q.push({x, y-1});
			arr[x][y-1] = arr[x][y] + 1;
			visited[x][y-1] = 1;
		}
		if (y+1 != n+1 && arr[x][y+1] == 0 && visited[x][y+1] == 0) {
			q.push({x, y+1});
			arr[x][y+1] = arr[x][y] + 1;
			visited[x][y+1] = 1;
		}
	}
	for (int i=1; i<=m; i++) {
		for (int j=1; j<=n; j++) {
			if (visited[i][j] == 0) {
				printf("-1");
				return 0;
			}
		}
	}
	int maxi = 0;
	for (int i=1; i<=m; i++) {
		for (int j=1; j<=n; j++) {
			if (arr[i][j] > maxi) {
				maxi = arr[i][j];
			}
		}
	}
	printf("%d", maxi-1);
}

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

#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;
//집합의 표현 1717번

vector<int> v;  //(본인정보, 부모정보)

int my_find(int me)
{
    if(me == v[me])
    {
        return me;
    }
    return v[me] = my_find(v[me]);
}

void my_union(int a, int b)
{
    int A = my_find(a);
    int B = my_find(b);

    if(A == B)
    {
        return;
    }

    v[A] = B;
}

int main(void)
{
    int n,m;
    int q, from, to;
    scanf("%d %d", &n, &m);
    v.push_back(0);

    for(int i=1; i<=n; i++)
    {
        v.push_back(i);
    }

    for(int i=0; i<m; i++)
    {
        scanf("%d %d %d", &q, &from, &to);
        if(q == 0)
        {
            my_union(from, to);
        }

        else if(q==1)
        {
            if(my_find(from) == my_find(to))
            {
                printf("YES \n");
            }
            else
            {
                printf("NO \n");
            }
        }


    }

	return 0;
}

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

#include<stdio.h>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
//양념 반 후라이드 반
int main(void)
{
    int a,b,c,x,y;//양후반
    int res=0;

    scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);

    if(2*c<(a+b))
    {
        while((x>0) && (y>0))
        {
            x--;
            y--;
            res+=2*c;
        }
        if(x>0)
        {
            if(2*c<a)
            {
                res+=(x*2*c);
            }
            else
            {
                res+=a*x;
            }
        }
        else if(y>0)
        {
            if(2*c<b)
            {
                res+=(y*2*c);
            }
            else
            {
                res+=b*y;
            }
        }
    }
    else//a+b<2c    a or b >2c
    {
        res+= a*x + b*y;
    }

    printf("%d", res);

	return 0;
}

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
*/
int vi[100010],max1,tot;
vector <pair<int,int>> v[100010];

void dfs(int s, int e, int lmax, int l)
{
    if(s==e) {
        max1=lmax;
        tot=l;
    }
    else{
        vi[s]++;
        for(int i=0;i<v[s].size();i++)
        {
            if(vi[v[s][i].first]==0)
            {
                int last=lmax>v[s][i].second?lmax:v[s][i].second;
                dfs(v[s][i].first,e,last,l+v[s][i].second);
            }
        }
    }

}
int main()
{
    int r,r1,r2,i,s,e,d;

    scanf("%d %d %d",&r,&r1,&r2);
    for(i=1;i<r;i++)
    {
        scanf("%d %d %d",&s,&e,&d);
        v[s].push_back(make_pair(e,d));
        v[e].push_back(make_pair(s,d));
    }
    dfs(r1,r2,0,0);
    printf("%d",tot-max1);
    return 0;
}

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

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

int sum; 
void Div_sum(int num)
{
    if(num == 0)
    {
        return;
    }

    sum+=(num%10);
    Div_sum(num/10);
}

int main(void)
{
    int n;
    int cnt=0;
    scanf("%d", &n);

    for(int i=1; i<=n; i++)
    {
        Div_sum(i);
        if((i%sum) == 0)
        {
            cnt++;
        }
        sum = 0;
    }

    printf("%d", cnt);

    return 0;
}

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

int main() {
  int a;
  cin >> a;
  int cnt = 0;
  for(int i=1; i <=a; i ++)
  {
    int sum = 0;
    int temp = i;
    while(temp){
      sum = sum + temp%10;
      temp = temp / 10;
    }
    //cout << "== " << sum << "\n";
    if( i % sum == 0) cnt ++;
  }

  cout << cnt;
  
}

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//2019 정올 2차 2번 문제 (중등)
struct s{
    int a,b,pos;
};
bool compare(struct s x,struct s y)
{
    //return x.a<y.a;

    if(x.a<y.a)
        return true;
    return false;
}
int main()
{
    int m,n,i,j,y,r1[1000000]={0,},r2[1000000]={0,},max1,k=0,t=0,z=0,flag=0;
    int g2[1000000];
    struct s log[1000000];
    scanf("%d %d",&m,&n);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&log[i].a,&log[i].b,&y);
        log[i].pos=i+1;
        g2[log[i].pos] = log[i].pos;
    }

    for(i=0;i<n;i++)
        scanf("%d %d",&r1[i],&r2[i]);
    sort(log,log+m,compare);
    while(1)
    {
        max1=log[t].b;
        
        int group = g2[log[t].pos];
        for(i=t;i<m-1;i++)
        {
            if(log[i+1].a<=max1)
            {
                
                g2[log[i+1].pos] = group;
                if(log[i+1].b>max1)
                    max1=log[i+1].b;
            }
            else
                break;
        }
        t=i+1;
        k++;
        z=0;
        if(t>=m)
            break;
    }


    for(t=0;t<n;t++)
    {
        if(g2[r1[t]] == g2[r2[t]]) puts("1");
        else puts("0");
    }
    return 0;
}

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

#include 
#include <bits/stdc++.h>
using namespace std;
/*
부분수열의 합
*/
int a[10000]={0,};
int main()
{
    int n,s,i,k,sum=0,cnt=0;
    scanf("%d %d",&n,&s);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<(1<<n);i++){
        sum=0;
        for(k=0;k<n;k++)
        {
            if(i&(1<<k))
            {
                sum+=a[k+1];
            }
        }
        if(sum==s)
            cnt++;
    }
    printf("%d",cnt);
    return 0;
}

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

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

int main()
{
    long long int n,a[1000001]={0,},i;
    scanf("%lld",&n);

    for(i=2;i<=n;i++)
    {
        a[i]=a[i-1]+1;
        if(i%2==0 && a[i] > a[i/2] + 1)
            a[i] = a[i/2] + 1;
        if(i%3==0 && a[i] > a[i/3] + 1)
            a[i] = a[i/3] + 1;
    }

    /*
    for(i=1; i<=n; i++)
        printf("%lld : %lld  \n",i, a[i]);
        */
    printf("%d", a[n]);
    return 0;
}

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

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

int main()
{
    int n,a[1000000]={0,},max1=0,i,tmp=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    do
    {
        for(i=1;i<=n-1;i++)
        {
            tmp+=abs(a[i]-a[i+1]);
            if(max1<tmp)
            {
                max1=tmp;
            }
        }
        tmp=0;
    }while(next_permutation(a+1,a+n+1));
    printf("%d",max1);
    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;
}

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

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

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

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

N과 M(1)문제 풀이 참고바람. (https://coding-gongboo.tistory.com/9?category=829643)

N과 M(1) 과의 차이점은 "고른 수열은 오름차순이어야 한다"는 점이다.

이를 위해서 현재 선택된 수 보다 1개 높은 위치의 수를 부터 수열을 만들어 나가야 한다.

이를 위해서 NM2(재귀함수)에 start해야 할 위치를 인자로 넘겨주는 부분이 수정되었다.

그리고 항상 다음 수를 대상으로 수열을 만들어 나가기 때문에 중복체크를 위한 included배열은 필요없다.

#include <bits/stdc++.h>

using namespace std;
//bool included[10]; //중복 체크
vector <int> nm;
void NM2(int, int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM2(1, n, m);
    return 0;
}

void NM2(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++) {
        //if (!included[i]) {
            //included[i] = true;
            nm.push_back(i);
            NM2(i + 1, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
            nm.pop_back();
            //included[i] = false;
        //}
    }
}

두번째 풀이

각 수들을 포함 하거나 또는 포함 하지않으면서 다음수로 넘어가는 형태

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

int main() {
    int n, m;
    cin >> n >> m;
    NM2(1, n, m);
    return 0;
}

void NM2(int level, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    if (level > n) return;
    nm.push_back(level);
    NM2(level + 1, n, m);
    nm.pop_back();
    NM2(level + 1, n, m);
}

세번째 풀이

배열을 사용해서 결과값을 저장한 위치에 해당하는 index 인자를 관리해주고,

오름차순을 위해 다음 수를 지정해주는 start를 관리해 주는 형태

#include <bits/stdc++.h>
using namespace std;
int res[10];
void go(int index, int start, int n, int m);

int main() {
    int n, m;
    cin >> n >> m;
    go(0, 1, n, m);
    return 0;
}

void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i];
            if (i != m - 1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = start; i <= n; i++) {
        res[index] = i;
        go(index + 1, i + 1, n, m);
    }
}

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

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

N=4, M=4가 주어지면, 아래와 같이 12(4*3)개의 경우가 발생한다.

아래 1 4 와 4 1과 같이 순서가 다른 경우는 다른 것으로 판단해야 함.

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

"중복 없이"라는 조건이 있음으로 한번 수열에 포함된 수는 수열을 완성할때까지 다시 포함되면 안됨으로 포함 여부를 판단하기 위해 included라는 배열을 사용한다.

n = 4, m = 2를 입력하면, 아래와 같은 순서로 실행된다.

"1. go(4,2)" : nm에 1추가 (nm = 1)

"2. go(4,2)" : nm에 2추가 (nm = 1,2)

"3. go(4,2)" : nm.size()가 m임으로 nm의 내용 1,2 출력 후 return

"2. go(4,2)" 로 돌아감. nm에서 2를 pop_bakc하고, for문을 통해 i 증가시킨 후 nm에 3을 추가함.

#include <bits/stdc++.h>

using namespace std;
bool included[10]; //중복 체크
vector <int> nm;
void NM1(int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM1(n, m);
    return 0;
}

void NM1(int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!included[i]) {
            included[i] = true;
            nm.push_back(i);
            NM1(n, m);
            nm.pop_back();
            included[i] = false;
        }
    }
}

지난 몇개월 동안 백준 문제풀이 사이트에서 딱 204개의 문제를 풀어봤다. 

2020년도 안에 300문제정도를 더 풀어서 백준사이트 랭킹 1000등안에는 들어가볼 계획이다.

내가 직접푼 소스코드는 물론이고, 학생들과 공부하는 과정에서 얻은 주옥같은 코드들도 공유하려한다.

대한민국이 SW강국이 되는 그날을 기대하며.......

https://www.acmicpc.net/