image.png

image.png

문제에서 노드는 국가이고 간선은 비행기의 종류이다. 모든 노드가 간선으로 연결되어 있음을 입력의 세번째 조건을 통해 알 수 있다. 가장 적은 종류의 비행기를 타야 한다고 했으므로 필요 없는 간선을 지우면 순환이 없는 연결 그래프가 된다. 이는 트리의 정의와 같다. 따라서 트리의 성질을 이용하면 출력은 (노드의 개수-1)이다.

문제풀이:

$N$개의 정점을 가진 그래프가 주어지고, $M$개의 간선을 가진 그래프가 주어집니다. 모든 정점을 연결하는 간선의 최소 개수를 출력해야 합니다. 문제의 입력 제한에서 해당 그래프가 항상 연결 그래프를 이룬다고 하였으므로, 이 그래프의 부분 그래프에는 반드시 트리가 존재합니다. 트리의 정의에 의해서 $N$개의 정점을 가지는 트리의 간선의 개수는 $N-1$개 이므로, $N-1$을 출력하면 정답입니다.

2025.01.20 (월요일)

9012번 “괄호” (실버IV)

image.png

#include <iostream> //c++
#include <stdio.h> //c
#include <vector> //c++ 배열
#include <algorithm> // 탐색, 정렬 등 알고리즘
#include <utility> // 
#include <string>
#include <cmath>
#include <set>
#include <map>

#define fio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // input, output 빠르게 하는 거
#define ll long long // long long이 너무 기니까 ll로 줄여요
#define pii pair<int,int> // pair<int,int>가 너무 길어요 그래서 pii로 줄여요
#define pll pair<ll,ll> // pair<long long, long long> 이 너어어어무 길어요. 그래서 pll로 줄여요
#define MOD 1e9+7 // 모듈러 계산할 때 쓰이는 값, 근데 문제마다 바뀌니까 알아서 바꾸세요

using namespace std;
int main()
{
    fio;
    int n;
    cin>>n;
    string a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        int op=0,cl=0;
        vector <int> v;
        for(int j=0;j<a.size();j++)
        {
            if(a[j]=='(')
            {
                op++;
                v.push_back(1);
            }
            else if(a[j]==')')
            {
                cl++;
                if(v.size()==0) continue;
                v.pop_back();
            }
            
        }
        //cout<<"vsize:"<<v.size()<<"\\n";
        if(op!=cl)
        {
            cout<<"NO"<<"\\n";
            continue;
        }
        if(v.size()!=0)
        {
            cout<<"NO"<<"\\n";
            continue;
        }
        //열린 괄호 닫힌 괄호 개수 같은지 여부확인+괄호가 열리면 닫는 행위를 했을때 열려있는게 있는지 여부확인
        cout<<"YES"<<"\\n";
    }
}

열린 괄호와 닫힌 괄호의 개수가 같은지 여부와 열린괄호를 만나면 벡터에 1을 넣고 닫힌 괄호를 만났을 땐 1을 pop했을 때 벡터에 아무것도 남지 않았는지의 여부를 모두 충족했을 때 YES를 출력하는 원리로 작동한다.

2025.01.21 (화요일)

1158번 “요세푸스 문제” (실버IV)

image.png

#include <iostream> //c++
#include <stdio.h> //c
#include <vector> //c++ 배열
#include <algorithm> // 탐색, 정렬 등 알고리즘
#include <utility> // 
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>

#define fio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // input, output 빠르게 하는 거
#define ll long long // long long이 너무 기니까 ll로 줄여요
#define pii pair<int,int> // pair<int,int>가 너무 길어요 그래서 pii로 줄여요
#define pll pair<ll,ll> // pair<long long, long long> 이 너어어어무 길어요. 그래서 pll로 줄여요
#define MOD 1e9+7 // 모듈러 계산할 때 쓰이는 값, 근데 문제마다 바뀌니까 알아서 바꾸세요

using namespace std;
int main()
{
    fio;
    int n,k;
    cin>>n>>k;
    queue <int> que;
    for(int i=1;i<=n;i++)
    {
        que.push(i);
    }

    int out;
    cout<<"<";
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k-1;j++)
        {
            out=que.front();
            que.pop();
            que.push(out);
        }
        if(i==n-1)
        {
            cout<<que.front()<<">";
            que.pop();
            continue;
        }
        cout<<que.front()<<", ";
        que.pop();
    }
}

순환하는 큐를 구현하기 위해서 front 값을 저장, pop, 저장 값을 push하여 구현하였고 이를 k번 실행하고 출력하면서 요구사항에 맞게 작동하도록 하였다.

2025.01.22 (수요일)

1021번 “회전하는 큐” (실버III)

image.png