훈감자 블로그

#include <bits/stdc++.h>
using namespace std;
#define INT long long int 

INT n,m,vf;
bool chk[1010];
queue<INT> q;
bool visited[1010];
INT dis[1010];

void dfs(vector<INT> adj[], INT x)
{
  if(chk[x])  return;
  chk[x] = true;
  cout << x << " ";
  for(auto u: adj[x])
    {
      dfs(adj, u);
    }
}

void bfs(vector<INT> adj[], INT x)
{
  visited[x] = true;
  q.push(x);

  while(!q.empty())
    {
      INT s = q.front();
      q.pop();
      cout << s << " ";
      
      for(auto u: adj[s])
        {
          if(!visited[u])  
          {
            visited[u] = true;
            q.push(u);
          }
        }
    }
  
}

int main()
{
  cin >> n >> m >> vf;

  vector<INT> adj[n+1];
  for(int i=0; i<m; i++)
    {
      INT u = 0, v = 0;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  for(int i=1; i<n+1; i++)
    {
      sort(adj[i].begin(), adj[i].end()); 
    }
  
  dfs(adj,vf);
  cout << endl;
  bfs(adj,vf);

  return 0;
}

#include <iostream>
#include <queue>
#include <functional>
#define INT long long int 
using namespace std;

INT n;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    priority_queue<INT, vector<INT>, greater<INT> > p;
    priority_queue<INT> q;

    cin >> n;

    for(int i=0; i<n; i++)
    {
        INT m = 0;
        cin >> m;

        if(q.empty())
        {
            q.push(m);
        }
        else{
            if(p.size() + 1 == q.size() || p.size() + 2 == q.size())
            {
                p.push(m);
                if(q.top() > p.top())
                {
                    INT qq = q.top();
                    INT pp = p.top();
                    q.pop();
                    p.pop();
                    q.push(pp);
                    p.push(qq);
                }
            }
            else{
                q.push(m);
                if(q.top() > p.top())
                {
                    INT qq = q.top();
                    INT pp = p.top();
                    q.pop();
                    p.pop();
                    q.push(pp);
                    p.push(qq);
                }
            }
        }
        cout << q.top() << "\n";
    }

    return 0;
}

-우선순위 큐 

#include <bits/stdc++.h>
#define INT long long int 
using namespace std;

INT n,k;
INT w[110], v[110];
INT dp[110][100010];

int main()
{
  cin >> n >> k;
  
  for(int i=1; i<n+1; i++)
    {
      cin >> w[i] >> v[i];
    }

  for(int i=1; i<k+1; i++)
    {
      for(int j=1; j<n+1; j++)
        {
          if(w[j] > i)
          {
            dp[j][i] = dp[j-1][i];
          }
          else{
            dp[j][i] = max(dp[j-1][i-w[j]] + v[j], dp[j-1][i]);
          }
        }
    }

  cout << dp[n][k];


  return 0;
}

- dp(반복문)