코딩코딩

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

파이썬 list로 풀었을 때 보단 코드가 많이 길어졌지만,, 

이분 탐색 첫 도전 ~_~ 

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


int n;
int a[100005];

int func(int target, int len){
  int st =0;
  int en = len-1;
  while(st<=en){
    int mid = (st+en)/2;
    if(a[mid]<target)
      st = mid+1;
    else if(a[mid]>target)
      en = mid-1;
    else
    {
      return mid;
    }
  }
  return -1;
}

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

  int m;
  cin>>m;
  while(m--){
    int num;
    cin>>num;
    if(func(num,n)== -1) cout<<0<<"\n";
    else cout<<1<<"\n";
  }
  
}

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

그리디 문제

1. N이 우선 5로 나누어 떨어지는 경우 바로 출력

2. 그 외에는 N-3을 해주며 봉지 개수를 늘려주고 다시 N-3한 값이 5로 나누어 떨어지는지 확인

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

int n;
 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  int result = 0;
  
  while(1){
    if(n%5 == 0){
      result += n/5;
      cout<<result<<"\n";
      break;
    }
    else{
      n -=3;
      if(n<0){
        cout<<-1<<"\n";
        break;
      }
      else{
        result++;
      }
    }
  }
}

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

어제 한 에라토스테네스 의 체 방법에 영감을 받아서  2부터 시작하여 배수에 해당하는 값들을 방문하며

열려있으면 (0) -> (1) 닫아주고 , 닫혀 있으면 (1) -> (0) 열어주는 방식으로 구현하였다.

a[1] 경우에는 처음 열어줄 때 빼고는 더이상 방문하지 않기 때문에 시작을 2로 두었고,

마지막에 열려있는 (0) 개수를 세어 출력 

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


int a[101];
int t;
 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>t;
  
  while(t--){
    int n;
    cin>>n;

    for(int i= 1; i<=n; i++){
      a[i] = 0; 
    }

    for(int i=1; i<=n; i++){
      for(int j=i*2; j<=n; j+=i){
        if(a[j] == 0) a[j] =1;
        else a[j] = 0;
      }
    }

    int cnt = 0;
    for(int i = 1; i<=n; i++){
      if(a[i]==0) cnt++;
    }
    cout<<cnt<<"\n";   
  }
 
}

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

2가지 방법으로 풀어 보았다.

1.  1978 소수 찾기 문제에서 사용한 소수 판별 함수를 활용 ,  for문으로 n이상 m이하의 수를 넣어서

소수인 경우에만 벡터에 넣고 , 벡터의 요소들을 출력

2. 에라토스테네스의 체 방법을 이용 

[1번 방법]

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

int n,m;
vector<int> vec;

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


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=n; i<=m; i++){
    if(func(i)) vec.push_back(i);
  }

  for(auto&i:vec){
    cout<<i<<'\n';
  }
  
}

[2번 방법]

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

int n,m;
int d[1000001];

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

  for(int i=2; i<=m; i++){
    d[i] = 1;    
  }

  for(int i= 2; i*i <=m; i++){
      for(int j = i*i; j<=m; j+=i){
        if(d[j] == 0) continue;
        else d[j] = 0;
    }
  }

  for(int i=n; i<=m; i++){
    if(d[i]!=0) cout<<i<<"\n";
  }

}

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

입력 되는 숫자가 소수인지 아닌지 판별하고 소수일 경우 개수 증가 

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

int n;
vector<int> vec;

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


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    int num;
    cin>>num;
    vec.push_back(num);
  }
  int cnt =0;
  for(auto&i : vec){
    if(func(i)) cnt++; 
  }

  cout<<cnt;

}

www.acmicpc.net/problem/2501

1부터 N까지의 수 중에 N을 나눴을 때의 나머지가 0인 약수를 구하는 방법 대신

N이 제곱수 일때의 약수의 중복을 피할 수 있는 좋은 코드를 보게 되어서 

코드를 활용하여 문제를 풀었담  

약수끼리의 곱이 N이 되도록 짝을 짓는 방식을 활용 ! 

진짜 똑똑한 사람들 많은듯,, ㅇ<-<

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

void divisor(int n,int k){
  vector<int> ret;
  for(int i=1; i*i <=n; i++){
    if(n%i ==0) ret.push_back(i);
  }
  for(int i= ret.size()-1; i>=0 ; i--){
    if(ret[i]*ret[i]==n) continue;
    ret.push_back(n/ret[i]);
  }
  
  if(ret.size()<k){
    cout<<0;
  }
  else{
  cout<<ret[k-1]<<"\n";
  }
}

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

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

오늘은 머리가 잘 안돌아 가는 기분,,

문제 접근 :  불만도 총합 최소를 구해야 하기 때문에, 되도록이면 높은 등수를 예상한 사람에게 높은 실제 등수를 매겨서 불만도를 최소화 할 수 있도록 구성

1. 입력 된 예상 등수 정렬

2. 정렬된 순서대로 1 ~ n 까지의 등수  부여

      /  실제 등수와 예상등수 차이의 절대값을 누적하여 더한다

포인트는 불만도 합을 long long type으로 설정하기.

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

int n;
vector<int> vec;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    int num;
    cin>>num;
    vec.push_back(num);
  }

  sort(vec.begin(),vec.end());
  long long sum =0;
  
  for(int i = 1; i<=n; i++){
    sum += abs(vec[i-1]-i);
    
  }

  cout<<sum<<"\n";

}

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

ex) 1924 입력시

처음 1을 읽어옴  벡터에 넣음 -> 다음 9를 읽어올 때 while문 조건에 충족 ,  1을 빼고 9를 넣음

-> 2를 읽어옴 while문 조건 충족 x 벡터에 넣음 -> 4를 읽어옴 조건 충족 4보다 작은 2를 빼고 4를 넣음

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

int n,k;
string str;
vector<char> vec;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>k>>str;
  for(int i=0; i<str.length(); i++){
    while(k && !vec.empty() && vec.back() <str[i] ){
      vec.pop_back();
      k--;
    }
    vec.push_back(str[i]);
  }
  for(int i=0; i<vec.size()-k; i++){
    cout<<vec[i];
  }

}

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

오늘도 그리디 

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

int n;
int d[1001];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>d[i];
  }
  int target = 0;
  sort(d,d+n);
  for(int i=0; i<n; i++){
    if(d[i]>target) break;
    target += d[i];
  }

  cout<<target+1<<'\n';
  
}

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

stoi 는 최고의 기능,, ㅇ<-<

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

string s;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>s;
  int sum = 0;
  string temp =" ";
  bool minus = false;
  for(int i=0; i<=s.size(); i++){
      if(s[i] == '-' || s[i] == '+' || s[i]== '\0'){
       if(minus){
            sum -= stoi(temp);
        }
        else{
            sum += stoi(temp);
        }
        temp ="";
         if(s[i] == '-'){
            minus = true;
        }
        continue;
      }
      temp +=s[i];
  }
  cout<< sum; 
}