Grace

multiset을 이용했다.

iterator를 통해 begin(최소값) end(최대값)에 접근하였다.

#include <iostream>
#include <set>

using namespace std;

int main(){
    int T = 0;
    cin >> T;
    for (int t = 0; t < T; t++){
        int n;
        cin >> n;
        multiset<int> ms;
        for (int i = 0; i < n; i++){
            char type;
            int input;
            cin >> type >> input;
            if(type == 'I'){ // 삽입
                ms.insert(input);
            }
            else{ // 샥제
                if(input == 1 && !ms.empty()){ // 최대값 삭제
                    ms.erase(ms.find(*(ms.rbegin())));
                }
                if(input == -1 && !ms.empty()){ // 최소값 삭제
                    ms.erase(ms.find(*(ms.begin())));
                }
            }
        }
        if(ms.empty())
            cout << "EMPTY\n";
        else
            cout << *ms.rbegin() << " " << *ms.begin() << "\n";
     }
}

배운 점

1. find를 이용한 중복된값 단일제거
erase은 인자값으로 iter와 value 모두 받는다.
인자로 value를 넣게되면 해당 value과 같은 값을 가지는 요소들을 모두 삭제하기 때문에 itr로 접근해야 한다.
따라서 find를 통해 특정값의 itr를 구하고 이것을 erase에 인자로 전달하여 하나의 요소만 삭제하도록 한다.

2. rbegin end 차이
end는 past-the-end의 iterator 즉, 마지막 원소의 다음 주소를 가리킨다.
past-the-end를 사용함으로써 컨테이너의 탐색을 용이하게 하고 (itr가 end()를 가리킬때까지 반복)
컨테이너 내부가 비었을때 begin과 end가 같은 값을 가리키도록 하기 때문이다.
따라서 마지막 원소를 삭제할때는 end()보다 한칸 앞에 있는 값을 지정해야하므로 --end()로 접근하거나 rbegin()을 사용해야 한다.

재귀로 접근한다.

basic step

1. n==1 인 경우, 즉 한칸까지 탐색범위가 좁아졌을 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

2. 모든 색종이가 같은 색일 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

Recursive step

basic step에 해당하지 않아서 탐색범위를 좁어야 하는 경우,

해당 시점을 기준으로 4등분한 solve()를 각각 콜한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int a[128][128]={0,};
int white = 0;
int blue = 0;

void solve(int x, int y, int n){

    if (n == 1){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }

    bool res = true;
    for (int i = x; i < x+n; i++)
    {
        for (int j = y; j < y+n;  j++){
            if(a[i][j] != a[x][y]){
                res = false;
            }
        }
    }

    if(res){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }else{
        solve(x, y, n / 2);
        solve(x, y + n / 2, n / 2);
        solve(x + n / 2, y, n / 2);
        solve(x + n / 2, y + n / 2, n / 2);
        return;
    }
    return;
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    solve(0, 0, n);

    cout << white << endl;
    cout << blue << endl;
}

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

풀이

unordered_map을 이용한다. unordered_map은 hash_map c++ lib이다. 내부적으로 hash로 구현되어 있어 탐색하는데 O(1)의 복잡도를 가진다. 데이터가 최대 10만개를 가지고 최대 10만개의 문제가 주어지기 때문에 unordered_map을 사용해야 한다.

key를 통해 value로 접근하기 때문에

name으로 number를 접근하기 위한 unordered_map과

number으로 name를 접근하기 위한 unordered_map을 각각 만들어 접근한다.

주어진 문제에 대해서 isdigit을 통해 숫자인지 이름인지를 판단하고

숫자인 경우 stoi를 통해 숫자변환 후 find를 진행한다.

이름인 경우에는 key를 이름으로 하는 unordered_map에 바로 접근할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cctype>

using namespace std;

unordered_map<string, int> list_name;
unordered_map<int, string> list_number;
vector<string> quiz;
int n, m;

int main(){
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    string str;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> str;
        list_name.insert({str, i});
        list_number.insert({i, str});
    }

    for (int i = 1; i <= m; i++){
        cin >> str;
        quiz.push_back(str);
    }

    for (int i = 0; i < m; i++){
        if(isdigit(quiz[i][0]) != 0){
            int num = stoi(quiz[i]);
            cout << list_number[num] << "\n";
        }else{
            cout << list_name[quiz[i]] << "\n";
        }
    }
}

배운 점

unordered_map : hash 기반의 map. crud O(1)를 가짐. 많은 데이터를 저장할때 사용.
stoi(string to integer) : string에 문자가 있으면 오류 발생. 문자열로된 순수 숫자로 이루어져있어야함.
atio() : c에서의 stoi. string타입을 지원하지 않기 때문에 str.c_str()로 변환하여 사용할 수 있음.
isdigit : string 전체가 아니라 인덱스 하나만 받아서 판별해준다.

<요약>

자본주의 정신에 있어서 가장 큰 영향을 미친 것은 청도교 정신이다. 자본주의 정신은 자본주의를 발달시켰다. 자본주의가 발달한 곳에 자본주의 정신이 있었다. 자본주의 정신은 금욕주의적이고 삶을 체계적으로 조직하여 살아가는 그들의 삶의 방식이다. 존재론적인 불안감을 떨처내고 싶어했던 당시의 개신교들은 구원의 확실성에 대한 많은 고민이 있었다. 청교도들은 금욕주의적 삶을 살아가는 것 많은 절제와 인내가 요구되기 때문에 구원받은 이가 아니라면 할 수 없다는 논리로서 금욕주의적 삶을 살아가는 것을 삶의 목표로 하였다. 그것이 그들에게 구원의 확실성을 증명하고 불안에서 자유하게 만들어 주었기 때문이다.

❗ 루터의 직업정신

루터의 직업 개념

세속적인 노동을 중요시해야 한다는 생각은 오래전부터 꾸준히 있어왔다. 하지만 종교개혁을 통해 새로운 의미의 직업 개념이 등장했다. 루터는 세속적인 노동을 종교적인 가치와 연관시켰다. 노동이 그 자체로 도덕적인 의무라고 생각했다. 루터에게 도덕적 의무를 다한다는 것은 직업 자체가 하나님께서 인간에게 주신 특별한 사명이기 때문이라기 보다는 자신이 처한 상황에서의 직업의 의무와 사명에 최선을 다하는 운명, 섭리론적인 의미를 갖는 전통주의적 개념이다.

→ 근대 자본주의적 직업 개념의 기원으로 보기 어렵다.

칼빈주의와 개신교 분파의 영향

자본주의 발달사에서 칼빈주의와 개신교 분파가 주목할만한 영향을 끼쳤다. 하지만 종교개혁이 직접적으로 근대 자본주의 정신이나 자본주의 체계를 탄생시켰다는 것은 아니다. 다수의 종교개혁자들은 그 누구도 윤리개혁을 목표로 삼지 않았다. 종교개혁자들의 관심자는 오로지 영혼의 구원이었다. 하지만 그들이 원했든 원하지 않았든 종교개혁의 종교적 동기가 근대 문화에 영향을 끼치게 되었다. 즉, 종교개혁이 근대 자본주의 문화에 직접적으로 영향을 미친것이 아니라 부수적인 영향을 끼쳤다는 것이다. 따라서 저자가 밝히고자 하는 것은 종교개혁의 종교적인 동기가 근대 자본주의 문화의 어떠한 요소들을 역사적으로 발전시켜왔는지에 대한 것이다.

 ❗ 금욕주의적 개신교의 직업윤리

저자가 관심갖는 것은 윤리적 지침이 아니라 금욕주의적인 생활양식을 이끌었던 심리학적 동력이다. 종교적 신앙과 삶의 양식 그리고 그러한 삶을 유지하게 하는 심리학적 동력에 주목한다.

칼빈주의

칼빈주의의 핵심교리는 예정론이다. 예정론은 문화사에 대단히 큰 영향을 미쳤다. 이 예정론이 어떠한 역사적인 인과적 중요성을 갖는지를 알아본다. 먼저 예정론 교리에 대해 간략히 설명한다.

- 예정론 교리

인간은 전적으로 타락하여 스스로 구원할 수 없는 무능력한 존재이다. 하나님은 영원전부터 모든 계획을 하시고 주관하신다. 또한 이 세상에 대한 절대주권을 갖는다. 본질적으로 소망없는 인간에게 하나님은 영원전부터 예정하신 개개인에 대한 예정에 따라 전적인 은혜를 통해 구원의 길로 부르신다. 구원은 전적으로 하나님의 주권과 예정에 있다. 예정된 인간을 그것을 거부할 수 없으며 은혜를 주지 않기로 작정된 인간은 절대로 구원받을 수 없다.. 루터교는 인간의 신앙심에 따라 구원을 여부가 결정된다는 입장이지만 칼빈주의는 영원전부터 모든것을 계획하신 하나님의 절대주권에 인간이 영향을 끼칠 수 없다고 본다.

- 세상, 타인 혐오와 불안

예정론은 극단적인 신앙의 형태이다. 칼빈주의자들로 하여금 세상을 거대한 시간의 흐름속에 잠깐 존재하는 무가치한 것으로 인식하도록 하였다. 문화에 대한 혐오를 낳았고 세상이 악하기 때문에 타인에 대한 신뢰를 약화하는 경향을 낳았다. 칼빈주의는 영혼을 구원하는 것은 하나님의 사역이라고 보았기 때문에 주어진 상황을 묵묵히 살아내는 것이 하나님의 영광을 드높이는 것이라 생각하였고 이는 인간성의 상실로 이어졌다.

- 구원의 확실성과 금욕주의

영혼 구원 에 대한 본질적인 불안은 하나님과의 직접적인 교통을 추구하게 만들었다. 그렇다면 어떻게 구원을 확신할 수 있는가? 첫째로 구원 받았음을 믿는 것이다. 구원에 대한 의심은 마귀의 역사이며 견고한 믿음은 은혜로부터 오는 것이다. 둘째로 성실하고 부지런한 직업적 노동이다. 이를 곧 택함의 증거로 보았다. 내적 체험을 강조하고 신비주의적인 태도를 갖는 루터교와는 달리, 칼빈주의는 믿음의 작용에 의한 행위적인 특질을 구원의 증거로 보았다. 하나님의 영광을 위한 생활양식을 성실히 영위하는 것이다. 따라서 조직적인 자기통제가 구원이 확실성을 만들어 낸다고 본다.

칼빈주의의 관심은 오로지 구원에 있었고 자신이 구원받았음을 확증하기 위한 동기로 하나님의 영광을 위한 세속에서의 자기통제, 자기주도적 삶이 중시되었다. 따라서 일시적인 감정을 따르는 것이 아닌 이성에 의한 규범을 추구하는 삶을 사는 금욕주의적 생활양식을 띄게 되었다. 악한 감정 뿐 아니라 무의미하고 무절제한 감정도 악으로 치부하였는데, 이는 이성을 냉철을 약화시키기 때문이었다. 또한 발전과정에서 세속적 직업활동을 통해 구원의 유무를 증명해야한다는 요소가 더해지면서 금욕주의적이지만 다른 한편으로 적극적이고 세속적인 삶의 기반을 마련했다. 그리고 체계적인 노동을 통해 세상을 윤택하게 하는 것이 타인에게 유익을 끼치는 행위 즉 이웃사랑을 실천하는 것이라고 보았다.

경건주의

경건주의는 개혁교회의 금욕주의적인 전통이 강화된 형태이다. 이들은 교리나 신학적인 지식보다 경건한 행위와 삶에 대해 관심을 가졌다. 신학적 학식이 뛰어나다고 해서 분명한 열매를 맺는 것은 아니며, 지식이 없다고 해서 열매를 맺지 못하는 것이 아니기 때문이다. 경건한 행위 추구라는 가치에 공감하는 이들이 모여 작은 집단을 이루는 것이 특징이다.

구원의 확신을 위해서 실천적 성화를 강조했던 칼빈주의와는 달리 경건주의는 죄사함을 중시하여 세속에서의 하나님과 함께함을 느끼는 내적 체험과 감성을 강조한다. 은혜의 상태에 있음을 삶 속에서 확증해야 한다는 칼빈주의 사상이 경건주의에서는 감성적이고 정서적인 방향으로 전환된다. 이로 인해 칼빈주의에 비해 세속적인 삶의 조직화 정도가 약화되었지만 루터교에 비해서는 종교적 삶의 체계적인 조직화는 강화된 모습을 띈다.

감리교

존 웨슬리로 유명한 감리교의 핵심은 회심과 성화이다. 감성적인 회심은 성화로 들어가게 한다. 감성적인 회심을 강조하지만 삶을 체계적이고 조직적으로 살아가는 합리주의 기반의 금욕주의를 말한다.

웨슬리는 행위구원을 비판한다. 주객이 전도되어있기 때문에다. 행위가 구원의 조건이 아니라 구원의 확실성을 확인하는 근거이다. 그리고 그 행위로 하나님의 영광을 위한 마음의 동기를 가질 때 참되다.

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

높이를 구하는 문제이기에 처음에는 이분탐색으로 풀수 있을거라고 생각했다.

하지만 여러케이스를 상성하고 고려해 보았을때 특정 높이로 땅을 고를수 있다고 했을때 어떠한 기준으로 범위를 좁혀나갈지를 정하는 것이 불가능했다.

지금까지 나온 시간중 최소시간이라고 하더라도 더 높은 곳에 최소시간을 갖는 높이가 존재할 수도 있고 더 낮은 곳에 최소시간을 갖는 높이가 존재할 수 있기 때문이다.

고민끝에 brute force방식으로 구현하였다.

0~256의 모든 높이에 대해 땅 고르는 시간을 구하고 그 중에서 최소값과 그 높이를 찾아 출력한다.

고려해야할 점이 한가지 있는데, 이는 해당높으로 땅을 고를 수 있느냐 하는 것이다. 인벤토리안에 주어진 B와 땅을 고르기 위해 파낸 땅의 개수가 target 높이를 맞추기 위해 놓은 땅의 개수보다 작으면 안된다.

#include <iostream>

using namespace std;

int main(){
    int n, m, b;
    int input[500][500]={0,};
    int sum = 0, min=987654321, h_index=0;
    int in_ground = 0, out_ground = 0;

    //input
    scanf("%d %d %d", &n, &m, &b);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            scanf("%d", &input[i][j]);
        }
    }

    //solved
    for (int h = 0; h <= 256; h++){
        sum = 0, in_ground = 0, out_ground = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(h - input[i][j] > 0){
                    sum += (h - input[i][j]); // 땅을 심어야하는 경우
                    in_ground += h - input[i][j];
                }
                if (h - input[i][j] < 0)
                {
                    sum += (input[i][j] - h)*2; // 땅을 파야하는 경우
                    out_ground += input[i][j] - h;
                }
            }
        }
        if(in_ground<=out_ground+b && min >= sum){
            min = sum;
            h_index = h;
        }
    }
    printf("%d %d", min, h_index);
    return 0;
}

❗ Congestion control의 필요성

TCP 통신시에 sender는 네트워크 환경과 receiver의 역량, 2가지를 고려하여 자신의 flow를 조정해야 한다.

두가지 변수 중에 상황에 따라 상대적으로 더 좋지 않은 변수에 맞춰야한다.

congestion control은 네트워크 환경을 고려하여 통신하는 TCP의 원리이다.

network 환경은 기본적으로 public이다. 누구나 인터넷을 사용할 수 있다. 그래서 아무런 제약없이 인터넷을 사용하도록 해두면 네트워크가 막힐 수 밖에 없다. TCP의 reliable을 보장하는 특성상, 패킷이 유실될 경우 재전송을 하기 때문에 네트워크가 제약없는 상태에서 막히면 막힐 수록 상황은 더욱 악화되기 마련이다. 내가 양보를 해야지 나도 살고 너도 살고 우리가 살게 되는 것이다. 네트워크는 아주 소중한 자원이기 때문에 서로 적절히 양보하며 자원을 사용해야 한다.

그렇다면 congestion control은 어떻게 네트워크 환경을 고려하여 통신을 진행할 수 있을까?

접근할 수 있는 방법은 크게 보면 2가지가 존재한다. 네크워크에서 직접적으로 정보를 받는 방식과 통신하는 노드를 통해 정보를 받는 방식이다. 라우터를 할일이 굉장히 많기 때문에 현실적인 제약으로 네크워크에서 직접적으로 정보를 받는 방식은 구현되지 않고 있다. congestion control은 후자, 그중에서도 노드간의 통신에서 간접적 정보를 통해 판단을 내리는 방식을 채택한다. 간단히 말하면 조금씩 조금씩 보내보다가 괜찮으면 좀 더 보내고 그러다가 유실이 발생하면 window size를 줄이는 방식이다.

❗ congestion control의 원칙과 작동원리

1. slow start

통신의 초기에는 네트워크의 상황이 어떠한지 판단이 불가능하기 때문에 세그먼트 1개 즉 1MMS크기의 window size를 갖고 통신을 시작한다. 1MSS로 시작하여 threshold 값 까지 exponential 하게 증가한다. threshold를 모르는 초기에는 유실이 발생할 때 까지 exponential하게 window size를 늘린다.

MSS(Maximun Segment Size : 세트먼트가 갖을 수 있는 최대크기, 500byte)

2. addtive increase

window size가 threshold를 지나간 시점부터는 linear하게 증가한다.

3. multiplicative decrease

유실이 발생했을 경우 threshold를 window size의 절반으로 떨어뜨린다. 그리고 window size는 유실판단 기준에 따라 달라지게 된다. 유실은 timeout과 3 duplication ack를 받은 경우로 나뉜다. 1) timeout의 경우 정말로 패킷이 유실되어 오지 않은 경우이기 때문에 네트워크 상황이 좋지 않다고 판단하여 window size가 1MSS로 설정된다. 2) 3 duplication ack의 경우는 네트워크 상황이 나쁘지는 않지만 하나의 패킷이 유실된 경우이기 때문에 window size를 threshold값으로 설정하여 바로 linear한 통신을 진행하게 된다.

최적의 threshold값을 찾아 그 언저리 값으로 통신하면 되는거 아니야? 하고 생각할 수 있지만 threshold는 네트워크 상황과 리시버의 환경에 따라 계속해서 변화하기 때문에 congestion control은 변화하는 threshold값을 계속해서 찾아나가는 과정이라고 보는 것이 맞는것 같다.

❗ Is Tcp fair?

TCP는 독립적인 노드들이 자신의 Flow를 조정하는 방식으로 작동하는데, 이것이 과연 모두에게 공평한가에 대한 의문을 가질 수 있다. 만약 네트워크 사용량이 R이라면 n명의 사용자가 있을때 모두 R/n 만큼 사용가능한가 라는 것이다. 직관적인 이해를 조금 힘들 수 있지만 결국 R/n으로 수렴한다고 한다.

TCP 통신을 진행하기 위해서는 각 노드가 4가지를 선제적으로 알고 있어야 한다.

바로 send buffer size, receive buffer size , 자신의 seq#, 상대의 seq# 이다.

이것은 그 유명한 3way-handshake 과정에서 세팅된다.

3way-handshake 과정

tcp header 중 syn bit값을 넣는 필드가 있다. syn은 tcp handshake과정에서만 1bit로 설정되는 필드이다.

1. client는 server에게 syn bit = 1, 자신의 seq#=x를 담은 빈 세그먼트를 보낸다.
2. server는 client에게 syn bit = 1, 자신의 seq#=y, ack=1, acknum=x+1을 담은 빈 세그먼트를 보낸다.
3. client는 server에게 ack=1, acknum=y+1을 담은 세그먼트를 보낸다.

3번 과정에서의 패킷 안에는 http request가 함께 포함되어서 갈 수 있다.

연결 끊는 과정

1. client는 server에게 FIN을 보낸다. 이때 client는 더이상 데이터를 보내지 않는다. (client close)
2. server는 client에게 ACK를 보낸 후 자신이 미처 보내지 못한 데이터들을 모두 보낸다.
3. 그 후 server는 client에게 FIN을 보낸다.
4. client는 server에게 FIN에 대한 ACK을 보낸다.

timed wait

4번 과정 이후 client는 timed wait을 가지면서 자신이 통신과정에서 사용했던 데이터들을 버리지 않고 기다린다. 이는 만약 4번의 ACK가 유실되었을 경우 ACK를 받지 못한 server가 client를 향해 무한 FIN을 보낼 수 있기 때문이다. 데이터를 일정시간(timeout value와 유사한)동안 갖고 있어야지 FIN에 대한 대처가 가능하다.

flow control이란?

tcp 통신시 각 노드에게는 send buffer / receive buffer가 존재한다. cumulative ack를 사용하는 특성으로 인해 패킷유실, 네트워크환경 등에 의해서 순서대로 오지 못한 패킷들을 임시로 저장해놓기 위해서이다.

process가 소켓에서 read를 하게 되면 갖고 있는 receive buffer에서 데이터를 올려받게 된다. 따라서 컴퓨터의 성능이나 다른 해야할 작업들이 많은 상황에서 receive buffer의 데이터들이 올라가는것이 딜레이가 될 수 있다. 이런 다양한 이유로 receiver가 데이터를 받을 수 있는 역량, 즉 receiver buffer의 남은 용량을 고려하여 통신이 진행될 수 있도록 하는 것이 flow control이다. flow는 하천, 강물과 같은 느낌이 있다. flow control는 이 flow를 조절하면서 통신하는 것이라고 기억하면 편할 것 같다.

구현방식

구현 방식은 생각보다 매우 간단한다. tcp segment의 header에 receiver buffer라는 필드가 있다. receiver는 ack를 보낼때 receiver buffer 필드의 수용가능한 데이터 용량을 기입하게 된다.

issue

A와 B가 tcp 통신 중이라고 가정해보자. 통신이 진행되는 중간에 B의 receive buffer가 가득차게 되어서 B는 receive buffer필드에 0을 넣은 ACK를 A에게 보내게 된다. 이것을 받은 A의 반응은 무엇일까? B의 버퍼가 가득차서 B에게 데이터를 보낼 수 없으니 아무것도 할 수 있는게 없다.

=> 실제 TCP구현에서는 A가 데이터가 들어있지 않는 세그먼트를 주기적으로 B에게 보내는 방식으로 처리된다.