BEEZI life

한글로 써도 영어가 너무 많이들어가길래 영어로 썼다.

c++11부터는 erase의 매개변수로 const_iterator이 들어간다.
정확히 뭔지는 모르겠으나.
set.erase(set.begin());을 하면 잘 되는데
set.erase(set.rbegin());을 하면 오류가 난다.

똑같은 iterator인데 왜 안되는지는 잘 모르겠으나 해결방법을 발견했다.

int main()
{
    std::set<int> set;

    set.insert(15);

    std::cout << set.size() << " ";

    auto ri = set.rbegin();

    auto i1 = --ri.base();

    auto i2 = --set.end();

    assert(i1 == i2);

    set.erase(i1);

    std::cout << set.size() << std::endl;
}

이런식으로 하면 된다고 하는데
나는 그냥 가볍게 아래와 같이 작성했다.

auto it=set.rbegin();
set.erase((--it.base()));

1. 배열을 반복해서 뒤집어야 하는 경우에는 포인터의 개념을 사용하면 시간복잡도를 상당히 줄일 수 있다.

vector<int> arr={1,2,3,4,5};
reverse(arr.begin(), arr.end());

for(auto it=arr.begin(); it!=arr.end(); ++it) { printf("%d ", *it); }

위 코드에서 뒤집기를 m번 할때, 시간복잡도가 \\( O(m\*N^2) \\)이지만

vector<int> arr={1,2,3,4,5};
bool rev=true;
if(rev){
    for(auto it=arr.rbegin(); it!=arr.rend(); ++it) { printf("%d ", *it); }
}else{
    for(auto it=arr.begin(); it!=arr.end(); ++it) { printf("%d", *it); }
}

위 코드는 뒤집기를 m번 할 때, 시간복잡도가 \\( O(N^2) \\)이다.

2. 문자열에 숫자를 추가할 때, 10을 넘어간다면 다른 방법을 사용해야한다.

vector<int> arr={1,2,3,4,5};
string answer="";
for(auto it=arr.begin(); it!=arr.end(); =+it){
    answer+=(*it+'0");
    answer+=",";
}

위 코드대로 한다면 answer="1,2,3,4,5"가 제대로 저장된다고 생각할 수 있다. 하지만 10을 넘어가게 된다면 전혀 예상치 못한 답이 출력될 수 있다.

vector<int> arr={1,2,3,10,15} 라고 한다면

answer="1,2,3,:,?" 가 저장될 것이다.

그 이유는 0의 ASCII코드가 48, :은 58, ?은 63이기 때문이다.

14889번: 스타트와 링크

위의 문제로 예를 들어서,

n명의 선수가 있고, 0번팀과 1번팀으로 선수들을 나눠서, 0번팀의 능력치합과 1번팀의 능력치합을 계산해야 하는 상황이다.
이 때, permutation을 사용하기 위해서 team=[0,1,1,0,...,1]이라고 하고,

n*n의 반복문을 돌면서 i와 j가 같은 팀일 때 각 팀의 능력치에 더해준다고 하면
\(O(n^2)\)의 시간복잡도를 가지게 된다.

int calcgap(){
  int team0=0, team1=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i==j) continue;
      // mask[i]에는 i의 팀 번호가 저장되어있다.
      if(mask[i]==0 && mask[j]==0) {team0+=stat[i][j]; continue;} 
      if(mask[i]==1 && mask[j]==1) {team1+=stat[i][j]; continue;}
    }
  }
  return abs(team0-team1);
}

이번에는 0번팀과 1번팀을 각각의 vector<int>에 담은다음 각 팀에서 반복문을 돌면서 능력치를 구한다면

\( O((\frac{n}{2})^{2}*2)=O(\frac{n^2}{2}) \) 의 시간복잡도를 가지게 된다.

그 이유는 수식에서 찾아볼 수 있다.

int calcgap(){
  vector<int> team0, team1;
  for(int i=0; i<n; i++){
    if(mask[i]==0) team0.push_back(i);
    else team1.push_back(i);
  }
  int gap=0;
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team0[i], b=team0[j];
      gap+=stat[a][b];
      gap+=stat[b][a];
    }
  }
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team1[i], b=team1[j];
      gap-=stat[a][b];
      gap-=stat[b][a];
    }
  }
  return abs(gap);
}

실제로 시간이 절반정도로 줄어든 것을 확인할 수 있다.

http://blog.naver.com/PostView.nhn?blogId=jinhan814&logNo=222202200887&parentCategoryNo=6&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

ps에서 c++을 사용하는 사람들 중 입력을 받을 때, 'cin'으로 입력을 받는 사람들은 대부분 시간을 단축하기 위해서

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
}

이런 trick을 사용한다.

하지만 문제를 푸는 도중에 문제의 입력을 색다른 방법으로 받아야 할 때가 있다.

위와 같은 경우들인데, 각 cell의 숫자들이 연속해서 입력되고 있다.

이것을 입력받기 위해서는 여러 가지 방법을 사용할 수 있는데,

내가 간단하게 사용하는 방법은 한자리씩 int형으로 입력받는 방법이다.

scanf("%1d", &a[x][y]);

이렇게 scanf를 사용하면서도 위의 trick을 지우지 않고 cin을 사용한다면 입력을 받을 때 오류가 발생한다.

이것 때문에 틀리지 않아도 되는 문제를 여러 번 틀렸다.

결론은, scanf를 사용할 때에

ios_base::sync_with_stdio(false);

이것은 꼭 주석처리 해 주어야 한다.

test-case가 주어지는 문제를 풀 때 가끔씩 전역변수로 선언된 vector을 케이스마다 새롭게 사용해야 하는 경우가 있다.

#include<bits/stdc++.h>
vector<int> a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
  }
  ...
}
    

위의 경우와 같이 전역변수 vector<int> a에 test-case마다 새로 값을 입력받아야 할 때에는,

test-case가 끝날 때 마다 전역변수 a의 값들을 초기화해주어야 한다.

이럴 때 자주 사용하는것은 

a.clear()

이것일 것이다.

하지만 

codingdog.tistory.com/entry/c-vector-clear-size를-0으로-만들어-준다

이 블로그의 글에 따르면 완벽하게 초기화 되지 않는다.

이것을 보완하여 완벽한 초기화를 하기 위해서

swap trick을 사용해주면 된다. 위의 예시를 활용해보자면

#include<bits/stdc++.h>
vector<int> a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
    vector<int>(20001).swap(a);
  }
  ...
}
    

만약 이차원 vector라도 동일하게 사용해주면 된다.

#include<bits/stdc++.h>
vector< vector<int> > a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
  }
  ...
  vector< vector<int> >(20001).swap(a);
}
    

int main(){
    int arr[1025][1025]={0,};
    int d[1025][1025]={0,};
    
    ...
    
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
      	d[i][j]=10 // 상수대입
        d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+arr[i][j]; // dp연산
      }
    }
    
    ...
}

main함수에서 arr배열과 d배열을 모두 1025*1025*sizeof(int)의 크기로 선언을 한 뒤

두 배열에 모두 값을 할당할 때, 

d[i][j]=10과 같이 상수를 대입했을 때에는 오류가 없었지만

d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+arr[i][j]; 와 같이 dp연산을 했을 때에는 segmentation fault가 발생하였다.

d배열을 전역변수에 선언하고 dp연산을 했을 때에는 오류가 발생하지 않는것으로 보아서

이 상황에서 오류가 발생한 원인은 매우 큰 두개의 지역변수로 인해서 스택메모리가 초과하여 발생한 오류로 보인다.

앞으로는 매우 큰 배열변수를 선언할 때에는 전역변수에 선언하는게 나을 것 같다.

선언과 동시에 초기화 ( 0 만 가능 )

오늘 백준 11053번 가장 긴 증가하는 부분수열4를 해결할 때, 배열 초기화를 잘못하는 실수를 했다.

앞서 l[1001]배열을 {-1,-1,-1,...,-1}로 초기화 하려고 시도했다.

int a[1001], d[1001], l[1001]={-1,}

하지만 디버깅을 하며 살펴보니 왼쪽과 같이 {-1, 0, 0, ... 0} 으로 초기화가 되어있었다.

왜그런가 찾아보니, c++에서 {n, } 형태로 배열을 초기화 할 때는 n==0인 경우에만 가능하다는 것이였다.

추가) 2차원배열도 똑같은 방법으로 초기화 할 수 있다.

int d[201][201]={0,}

Memset함수 ( 0, -1 만 가능)

-1로 초기화 하기 위해서는

memset(l,-1,sizeof(l));

이렇게 memset을 활용해서 초기화 해야하고, memset함수도 주의해야 할 점이 있는데

초기화할 수 있는 값은 0과 -1만 가능하다는 것이다.

For문 ( 모든 경우 )

그 외의 숫자로 초기화 하기 위해서는 마음 편하게 for문으로 초기화 하는게 나을 것 같다.

for(int i=0; i<n; i++){
	l[i]=3;
}