코딩코딩

www.acmicpc.net/problem/2206

이동한 거리를 출력해야하기 때문에 BFS 사용

3차원 배열 사용 block[x][y][벽 부셨는지]     0: 벽을 안부숨 / 1: 벽을 부숨 

두 가지로 판단

1. 다음 이동하는 위치에 벽이 없는 경우 -> 그대로 탐색 진행

2. 다음 위치에 벽이 있고 , 벽을 아직 한 번도 부시지 않은 경우 -> 벽을 부셨다고 표시 

while문을 돌면서 x,y좌표가 n-1, m-1에 도달한 경우 그 때의 이동거리를 리턴해준다. 

=> 시작을 0,0으로 진행했기 때문에 n-1, m-1에 도달한 것을 조건으로 세웠다.

#include <bits/stdc++.h>

using namespace std;
int n,m;

string board[1001];
int block[1001][1001][2];
struct asda
{
  int x,y,z;
};

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

int bfs(){
  queue<asda> que;
  block[0][0][0]=1;
  que.push({0,0,0});

  while(!que.empty()){
    int x = que.front().x;
    int y = que.front().y;
    int z = que.front().z;
    
    que.pop();
    
    if(x == n-1 && y == m-1) return block[x][y][z];
    for(int i=0; i<4; i++){
      int nx = x+dx[i];
      int ny = y+dy[i];  
      if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
      if(block[nx][ny][z]) continue;

      if(board[nx][ny]=='1' && z == 0 ){    
        que.push({nx,ny,z+1});
        block[nx][ny][z+1] = block[x][y][z]+1;
      }
      else if(board[nx][ny]=='0'){
        que.push({nx,ny,z});
        block[nx][ny][z] = block[x][y][z] +1;
      }      
   
    }
  }
  return -1;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0); 
  cin>>n>>m;
  for(int i=0; i<n; i++){
    cin>>board[i];
  }
  cout<<bfs()<<"\n";
}

www.acmicpc.net/problem/13023

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

A->B->C->D->E  탐색하는 그래프의 깊이가 4라면 1 아니면 0을 출력하는 것이 문제 풀이 포인트

DFS 사용 

종료 조건 : 탐색 깊이가 4일 때, 깊이 체크 변수를 true로 변경 후 리턴

사람들은 0번부터 N-1번으로 번호가 매겨져 있기 때문에 0부터 N-1까지 for문을 돌며 dfs 탐색을 진행한다. 

dfs 탐색이 끝난 후 check 변수를 출력해주면 끝....

#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<int> vec[2002];
bool visited[2002];
bool check = false;

void dfs(int num, int depth){
  if(depth == 4){
    check = true;
    return;
  }
  for(int i=0; i<vec[num].size(); i++){
    int nxt = vec[num][i];
    if(visited[nxt]) continue;
    visited[nxt] = 1;
    dfs(nxt,depth+1);
    visited[nxt] =0;
  }
}

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

  for(int i=0; i<n; i++){
    visited[i] = 1;
    dfs(i,0);
    visited[i] = 0;
    if(check) break;
  }
  cout<<check<<"\n";
}

www.acmicpc.net/problem/1463

dp

1. 초기값 설정  d[1] = 0

2. 점화식 찾기 

i %2 == 0 일때, d[i] = min(d[i],d[i/2]+1);

i %3 == 0 일때, d[i] = min(d[i],d[i/3]+1);

d[i] = d[i-1]+1;

3. 테이블 : d[i] = i를  1로 만들 때 필요한 연산의 최소 횟수 , 

#include <bits/stdc++.h>

using namespace std;

int d[1000001];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;

  d[1] = 0;
  for(int i=2; i<=n; i++){
    d[i] = d[i-1]+1;
    if(i%2==0) d[i] = min(d[i],d[i/2]+1);
    if(i%3==0) d[i] = min(d[i],d[i/3]+1);
  }
  cout<<d[n]<<"\n";
 
}

www.acmicpc.net/problem/2583

풀이는 BFS 사용

포인트는 주어진 좌표의 넓이 만큼은 접근하지 못하도록 해야함 -> 그 좌표 영역만 2중 for문으로 탐색하며 1로 채워줌

다른 bfs 문제처럼 좌표가 0이며 접근하지 않은 곳만 상하좌우 모두 탐색을 해주며 영역과 개수를 세어준다.

무난무난,,,한 문제,,,,,

#include <bits/stdc++.h>

using namespace std;

int m,n,k;
int dist[101][101];
int board[101][101];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>m>>n>>k;
  queue<pair<int,int>> q;
  vector<int> vec;
  int cnt = 0;
  int area = 0;
  for(int i=0; i<k; i++){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    for(int j=x1; j<x2; j++){
      for(int k=y1; k<y2; k++){
        board[j][k] = 1;
      }
    }
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(board[i][j]==0 && dist[i][j] ==0){
        q.push({i,j});
        dist[i][j] = 1;
        cnt++;

        while(!q.empty()){
          auto cur = q.front();
          q.pop();
          area++;

          for(int i=0; i<4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if(nx<0|| nx>=n || ny<0 || ny>=m) continue;
            if(board[nx][ny] !=0 || dist[nx][ny] !=0) continue;
            q.push({nx,ny});
            dist[nx][ny] = 1;
          }
        }
        if(area!=0) {
          vec.push_back(area);
          area =0;}
      }
      
    }
  }
  cout<<cnt<<"\n";
  sort(vec.begin(),vec.end());
  for(auto&i : vec){
    cout<<i<<" ";
  }
  cout<<"\n";

}

www.acmicpc.net/problem/1874

숫자 입력되는 순서대로 스택의 top과 각 숫자와 같은 경우 스택에서 pop하고 따로 벡터에 '-'를 넣어주고  다음 인덱스로 이동시킨다. 예전엔 틀려서 그냥 넘겼는데 이렇게 쉬운 문제였다니,,,,ㅇ<-<

#include <bits/stdc++.h>

using namespace std;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  vector<int> vec;
  stack<int> st;
  vector<char> ans;

  cin>>n;
  for(int i=0; i<n; i++){
    int num;
    cin>>num;
    vec.push_back(num);
  }
  auto cur = vec.begin();
  for(int i=1; i<=n; i++){
    st.push(i);
    ans.push_back('+');
    while(!st.empty()){
      if(*cur != st.top()) break;
      else{
        st.pop();
        ans.push_back('-');
        cur++;
      }
    }
  }
  if(!st.empty()) cout<<"NO"<<"\n";
  else {
    for(auto& i:ans){
      cout<<i<<"\n";
    }
  }

}

www.acmicpc.net/problem/10816

upper_bound , lower_bound 함수 사용

개수를 셀 때 자주 사용하는 함수니까 익혀두는 것이 좋다 !!!!

upper_bound(시작, 끝 , 값)  / lower_bound(시작, 끝, 값)

upper_bound = 값을 초과하는 숫자가 먼저 등장하는 인덱스 위치

lower_bound = 값을 포함하는 숫자가 먼저 등장하는 인덱스 위치 

#include <bits/stdc++.h>

using namespace std;



int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  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());
  cin>>m;
  for(int i=0; i<m; i++){
    int num;
    cin>>num;
    cout<<upper_bound(vec.begin(),vec.end(),num)-lower_bound(vec.begin(),vec.end(),num)<<" ";
  }
  cout<<"\n";

}

www.acmicpc.net/problem/10819

next_permutation 함수를 사용하여 모든 요소에 대해 순열(자리를 바꿔주며) 각 인접한 요소의 뺄셈을 해주며 구한 합의 최댓값을 출력한다.  

6개 중에 2개를 고르며 합의 최대값을 리턴 받음

  -> 순열 next_permutation 사용 

아아ㅏ가가가가ㅏㅈㅈ 집중력 0 ㅠㅠ

#include <bits/stdc++.h>

using namespace std;



int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  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 ans = 0;

  do
  {
      int sum = 0;
      for(int i=0; i<vec.size()-1; i++){
          sum+= abs(vec[i]-vec[i+1]);
      }
      ans = max(ans,sum);
      /* code */
  } while (next_permutation(vec.begin(),vec.end()));
  
  cout<<ans<<"\n";
 
}

www.acmicpc.net/problem/10972

next_permutation 함수 사용 하여 정렬해서 넣지 않고, 입력된 순열 뒤에 올 값이 있다면 출력 아니면 -1 출력

#include <bits/stdc++.h>

using namespace std;
int arr[10001];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=0; i<n; i++){
      cin>>arr[i];
  }
  if(next_permutation(arr,arr+n)==true){
     for(int i=0; i<n; i++){
         cout<<arr[i]<<" ";
     }
     cout<<"\n";
  }
  else{
      cout<<-1<<"\n";
  }
  
}

www.acmicpc.net/problem/10973

prev_permutation 함수 사용 입력된 요소 앞에 오는 순열이 있다면 출력, 아니면 -1 출력 

#include <bits/stdc++.h>

using namespace std;
int arr[10001];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=0; i<n; i++){
      cin>>arr[i];
  }
  if(prev_permutation(arr,arr+n)==true){
     for(int i=0; i<n; i++){
         cout<<arr[i]<<" ";
     }
     cout<<"\n";
  }
  else{
      cout<<-1<<"\n";
  }
  
}

www.acmicpc.net/problem/10974

next_permutation 함수를 사용하여 1-n까지의 모든 순열을 차례대로 출력한다. 

#include <bits/stdc++.h>

using namespace std;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  vector<int> vec;
  for(int i=1; i<=n; i++){
      vec.push_back(i);
  }
  do
  {
      for(int i=0; i<n; i++){
          cout<<vec[i]<<" ";
      }
      cout<<"\n";
  
  } while (next_permutation(vec.begin(),vec.end()));
  
 
}

www.acmicpc.net/problem/3671

next_permutation 이용하여 모든 경우의 수를 벡터에 따로 저장 해두고 unique 함수로 중복 요소를 제거해준다.

각 요소에 대해 소수판별을 하고 참인 경우에 대한 개수만 세어 준다. 

#include <bits/stdc++.h>

using namespace std;

bool chk(int n){
    if(n<2) return false;
    for(int i=2; i*i<=n; i++){
        if(n%i ==0) return false;
    }
    return true;
}

int main(void){
    int t;
    cin>>t;
    while(t--){
        int answer = 0;
        string str = "";
        cin>>str;
        vector<int> vec;
        for(int i=0; i<str.size(); i++){
            vec.push_back(str[i]-'0');
        }
        sort(vec.begin(),vec.end());
        vector<int> ans;
        do
        {
            for(int i=0; i<=vec.size(); i++){
                int tmp =0;
                for(int j=0; j<i; j++){
                    tmp = (tmp*10)+vec[j];
                    ans.push_back(tmp);
                }
            }
        } while (next_permutation(vec.begin(),vec.end()));
        
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        for(int i=0; i<ans.size();i++){
            if(chk(ans[i])) answer++;
        }
        cout<<answer<<"\n";
        fill(vec.begin(),vec.end(),0);
        fill(ans.begin(),ans.end(),0);
        
    }
}