BEEZI life

Class 3의 문제를 모두 풀었다.

여기에서 기초적인 지식들을 많이 얻고 부족한 점들을 많이 보완할 수 있었다.

배운것 : map, set, 기초적인 문자열 다루기, Floyd-Warshall
보완한 점 : 재귀, 분할정복, 그래프문제

추가로 최근에 풀어본 프로그래머스 실력체크 Level 2도 첨부한다.

다음목표 : Class 4, Level 3

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

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

https://jacking75.github.io/C-_array_ref/

이 문제를 풀 때 쉽게 생각할 수 있는 풀이는

음수*음수->양수
양수*양수->양수

이렇게 묶어서 합을 최대로 만드는것이다.

조금 더 생각하면,
음수의 개수가 홀수개일 때,
-3, -2, -1 을 (-3 * -2) + -1로 묶을 수 있다.
여기서 0이 1개이상일경우
-3, -2, -1, 0을 (-3 * -2) + (-1 * 0)로 묶어서 -1을 없애줄 수 있다.

여기까지는 생각하기 쉽지만 한가지 간과한 것이 있다.

1은 무엇과 곱해도 손해이다. 무조건 더하는것이 낫다.
4, 3, 2, 1-> (4 * 3) + (2 * 1) = 14
                 -> (4 * 3) + 2 + 1 = 15

0과 함께 있는 경우에도 마찬가지이다.
4, 3, 1, 0-> (4 * 3) + (1 * 0) = 12
                 -> (4 * 3) + 1 + 0 = 13