코딩코딩

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

연결된 정점 1개만 자신의 부모 

따로 부모 배열을 생성하여 각 요소의 부모 (정점)을 저장 

탐색하며 nxt 가 부모인 경우 패스 아닌 경우 탐색 

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

int n;
vector<int> vec[100001];
int p[100001];

void dfs(int root){
  stack<int> s;
  s.push(root);
  while(!s.empty()){
    int cur = s.top();
    s.pop();
    for(int i= 0; i<vec[cur].size(); i++){
      int nxt = vec[cur][i];
      if(p[cur] == nxt) continue;
      s.push(nxt);
      p[nxt] = cur;
     } 
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n-1; i++){
    int a,b;
    cin>>a>>b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  dfs(1);
  for(int i=2; i<=n; i++){
    cout<<p[i]<<"\n";
  }
  
}

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

stl set 사용

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

int n;
set<string,greater<string>> s;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    string name,str;
    cin>> name>>str;
    if(str == "enter") s.insert(name);
    else{
      s.erase(name);
    }
  }
  for(auto&i : s){
    cout<<i<<"\n";
  } 
  
}

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

나도 코딩왕 되고 싶다,, 머리 안돌아가 ㅇ<-<

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

int n,m;
vector<int> vec[1001];
bool vis[1001];

int dfs(){
  int cnt =0;
  stack<int> s;
  for(int i=1; i<=n; i++){
    if(vis[i]) continue;
    cnt++;
    s.push(i);
    vis[i] = 1;
    while(!s.empty()){
      int cur = s.top();
      s.pop();
      for(int i= 0; i<vec[cur].size(); i++){
        int nxt = vec[cur][i];
        if(vis[nxt]) continue;
        s.push(nxt);
        vis[nxt] = 1;
      }
    }
  }
  return cnt;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<m; i++){
    int u,v;
    cin>>u>>v;
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  cout<<dfs();
}

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

BFS를 사용했다. 1번 부터 감염되는 컴퓨터의 수를 찾는 것 이기 때문에 1번을 시작으로  cnt++ 해주며 

시작점을 포함한 컴퓨터의 수 이기 때문에 마지막 -1를 해준다.

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

int n,m;

bool visited[101];
vector<int> vec[101];

int bfs(){
  int cnt = 0;
  queue<int> q;
  q.push(1);
  visited[1] = 1;
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    cnt++;
    for(int i=0; i<vec[cur].size(); i++){
      int nxt = vec[cur][i];
      if(visited[nxt]) continue;
      visited[nxt] = 1;
      q.push(nxt);
    }
  }
  return cnt; 
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<m; i++){
    int a,b;
    cin>>a>>b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  cout<<bfs()-1<<"\n";
}

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

그래프 공부하며 dfs구현시 재귀를 사용하는 아주 좋은 코드를 보게되어

공부용으로 기록 !

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

int n,m,v;
bool visited[1001];
vector<int> vec[1001];

void dfs(int cur){
  cout<<cur<<" ";
  for(int i=1; i<=n; i++){
    int nxt = vec[cur][i];
    if(visited[nxt]) continue;
    visited[nxt] = 1;
    dfs(nxt);
  }
}

void bfs(){
  queue<int> q;
  q.push(v);
  visited[v] = 1;
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    cout<<cur<<" ";
    for(int i=1; i<=n; i++){
      int nxt = vec[cur][i];
      if(visited[nxt]) continue;
      q.push(nxt);
      visited[nxt]= 1; 
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m>>v;
  for(int i=0; i<m; i++){
    int a,b;
    cin>>a>>b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  for(int i=0; i<m; i++){
    sort(vec[i].begin(), vec[i].end());
  }
  visited[v] = 1;
  dfs(v);
  cout<<"\n";
  fill(v,v+n+1,0);
  bfs();
}

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

1764 듣보잡 문제와 유사한 정렬 문제 

binary_search 이분탐색을 사용하여 정렬된 벡터 내에 찾는 번호가 있으면 1 출력 없으면 0 출력

binary_search는 사전에 정렬된 벡터/배열에만 사용가능하기 때문에 사전 정렬은 필수 #

매번 테스트케이스가 여러 개 라서 매번 초기화 해주는걸 깜빡한다.. 

정신차려 ~~~! 

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

int t;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    vector<int> vec;
    for(int i=0; i<n; i++){
      int num;
      cin>>num;
      vec.push_back(num);
    }
    sort(vec.begin(),vec.end());

    int m;
    cin>>m;
    for(int i=0; i<m; i++){
      int num; 
      cin>>num;
      if(binary_search(vec.begin(),vec.end(),num)){
        cout<<1<<"\n";
      }
      else{
        cout<<0<<"\n";
      }
    }
  }  
}

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

정렬 문제 풀기 

최고 점수와 선택된 문제의 번호를 모두 출력해야 하기 때문에 입력받을 때 차례대로 번호 부여

점수 기준으로 내림차순으로 정렬하여 상위 5개의 합을 구하고 

상위 5개에 대한 문제 번호를 따로 배열에 저장한 후 정렬하여 출력 

문제 번호를 0번부터 부여하였기 때문에 출력할 때 문제번호 +1을 해준다

항상 이런 쉬운문제만 나오면 얼마나 좋을까,, ㅇ<-<

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


bool compare(pair<int,int> a, pair<int,int> b){
  return a.first>b.first;
}


vector<pair<int,int>> vec;
int d[5];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  for(int i= 0; i<8; i++){
    int num;
    cin>>num;
    vec.push_back({num,i});
  }
  int sum = 0;
  sort(vec.begin(), vec.end(),compare);

  for(int i=0; i<5; i++){
    sum += vec[i].first;
  }
  cout<<sum<<"\n";

  for(int i =0; i<5; i++){
    d[i] = vec[i].second;
  }

  sort(d,d+5);
  for(int i=0; i<5; i++){
    cout<<d[i]+1<<" ";
  }

}

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

애초에 구조체에 국가번호/금/은/동/등수 를 넣어서 생성했다.

compare 함수를 만들 때 부호 방향을 자연스래 반대로 해서 한 번 틀렸지만

무난하게 풀 수 있었다.

문제 조건에 맞는 비교 함수를 만든 후, 이를 기준으로 정렬 

그리고 for문을 돌며 등수를 비교하고 금/은/동 개수가 같은 경우 등수를 동일하게 조정,

아닌 경우 등수에 +1을 해주며 각 나라에 등수를 부여하고 원하는 국가의 등수 출력해주면 끝

내일은 1-2문제만 풀고 스프링 공부해야징,,

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

struct medal{
  int num;
  int gold;
  int sliver;
  int bronze;
  int rank;
};

int n,m;
vector<medal> vec;

bool compare(medal a , medal b){
  if(a.gold == b.gold && a.sliver == b.sliver){
    return a.bronze > b.bronze;
  }
  else if(a.gold == b.gold){
    return a.sliver > b.sliver;
  }
  else{
    return a.gold > b.gold;
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<n; i++){
    int n,g,s,b;
    cin>>n>>g>>s>>b;
    vec.push_back({n,g,s,b,1});
  }

  sort(vec.begin(), vec.end(), compare);

  for(int i=1; i<n; i++){
    if(vec[i].gold == vec[i-1].gold &&
    vec[i].sliver == vec[i-1].sliver &&
    vec[i].bronze == vec[i-1].bronze){
      vec[i].rank = vec[i-1].rank;
    }
    else{
      vec[i].rank = i+1;
    }
  }
  for(int i =0; i<n; i++){
    if(vec[i].num == m){
      cout<<vec[i].rank;
      break;
    }
  } 
}

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

정렬 + 이분탐색 

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

int n,m;
vector<string> vec;
vector<string> res;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<n; i++){
    string s;
    cin>>s;
    vec.push_back(s);
  }
  sort(vec.begin(),vec.end());

  for(int i=0; i<m; i++){
    string s;
    cin>>s;
    if(binary_search(vec.begin(),vec.end(),s)){
      res.push_back(s);
    }
  }
  sort(res.begin(),res.end());
  cout<<res.size()<<"\n";
  for(auto&i:res)
    cout<<i<<"\n";  
  
}

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

머리 잘 안돌아갈 때는 역시 정렬 문제,, 

합이 작아야 하기 때문에,, A는 오름차순 Bㄴ는 내림차순으로 정렬해서 곱해주고 더하기 

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

int n;
int a[51];
int b[51];


bool compare(int a, int b){
  return a>b;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>a[i];
  }
  for(int i=0; i<n; i++){
    cin>>b[i];
  }
  sort(a,a+n);
  sort(b,b+n,compare);
  int sum = 0; 
  for(int i=0; i<n; i++){
    sum += a[i]*b[i];
  }

  cout<<sum;
}